Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (15) 全排列 下一个排序 括号生成 复原IP地址

发表于 更新于 分类于

全排列

全排列

解题思路

利用回溯算法。path记录当前已经选择的数字，used记录已经选择的数字。当len(path) == len(nums)时，找到一种情况，将path加入结果集中

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func permute(nums []int) [][]int {
    n := len(nums)   // 数组长度
    res := make([][]int, 0)     // 结果集
    path := make([]int, 0)    // 当前已经选择的数字
    used := make([]bool, n)     // 记录已经选择的数字
    var backtrack func()

    backtrack = func() {   // 回溯函数
        if len(path) == n {     // 找到一种情况
            p := make([]int, n)
            copy(p, path)
            res = append(res, p) // 加入到结果集
            return
        }
        for i := 0; i < n; i++ {
            if used[i] == true {
                // 已经选择过该数字，跳过
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            backtrack()     // 递归
            // 恢复状态
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    backtrack()     // 执行回溯

    return res
}

下一个排列

下一个排列

解题思路

我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，才能得到一个更大的数。还希望下一个数增加的幅度尽可能的小，所以必须满足要求：

  1. 在尽可能靠右的低位进行交换，需要从后向前查找
  2. 将一个 尽可能小的「大数」 与前面的「小数」交换
  3. 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列

所以算法过程为：

  1. 从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
  2. 在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
  3. 将 A[i] 与 A[k] 交换
  4. 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
  5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func nextPermutation(nums []int)  {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        // 从后向前扫描，找到第一个相邻升序对(nums[i], nums[i+1])
        i--
    }
    // 如果存在这样的升序对，[i+1, len(nums))为降序的
    if i >= 0 {
        k := len(nums)-1
        for k > i && nums[k] <= nums[i] {
            // 在[i+1, len(nums))上，找到第一个nums[k]，使得nums[k] > nums[i]
            k--
        }
        nums[i], nums[k] = nums[k], nums[i]     // 交换值
    }
    // 对[i+1, len(nums))部分逆置
    for i, j := i+1, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

括号生成

括号生成

解题思路

把添加左右括号看作是二叉树的左右子树，那么添加一个左括号就是进入左子树，添加一个右括号就是进入右子树。所以，n对括号可以生成一颗深度为2n的满二叉树。但是并不是所有的叶子节点都是合法的，以下条件需要剪枝：

  • 当左/右括号数量小于n时，才能继续添加左/右括号
  • 当右括号数量大于左括号数量时，该括号组合一定不合法

括号生成相当于对这颗二叉树进行深度优先遍历

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func generateParenthesis(n int) []string {
    res := []string{}     // 结果集
    var dfs func(curStr string, left int, right int)
    dfs = func(curStr string, left int, right int) {    // curStr为当前生成的字符串，left为左括号的数量，right为右括号的数量
        if left == n && right == n {
            // 左右括号数量足够，加入结果集
            res = append(res, curStr)
        }
        if right > left {
            // 右括号数目多于左括号数目，减枝
            return
        }
        if left < n {
            dfs(curStr+"(", left+1, right)
        }
        if right < n {
            dfs(curStr+")", left, right+1)
        }
    }

    dfs("", 0, 0)	// 进行深度优先遍历

    return res
}

复原 IP 地址

复原 IP 地址

解题思路

利用回溯算法的思想，因为IP地址的每一个部分的长度都是1~3，所以这是一棵三叉树，每一部分划分的长度对应三叉树的三个子树。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
func restoreIpAddresses(s string) []string {
    res := make([]string, 0)    // 记录结果
    if len(s) < 4 || len(s) > 12 {
        // 肯定不合法，直接返回
        return res
    }
    path := make([]string, 0)   // 记录当前的选择
    var backtrack func(startIndex int, segmentNum int)
    backtrack = func(startIndex int, segmentNum int) {
        // s为待划分的字符串，startIndex为当前开始划分的位置，segmentNum为已经划分的片段的数量
        if startIndex == len(s) && segmentNum == 4 {
            // 得到合法IP地址，加入结果集
            res = append(res, strings.Join(path, "."))
        }
        if len(s) - startIndex < 4 - segmentNum || len(s) - startIndex > 3 * (4-segmentNum) {
            // 待划分的字符串不合法
            // len(s) - startIndex 为待划分字符串的长度
            return
        } 
        for length := 1; length <= 3; length++ {
            if startIndex + length > len(s) {
                break
            }
            // 新的划分
            segment := s[startIndex: startIndex+length]
            if isValid(segment) {
                path = append(path, segment)
                segmentNum++
                backtrack(startIndex+length, segmentNum)
                // 恢复状态
                path = path[:len(path)-1]
                segmentNum--
            }
        }
    }

    backtrack(0, 0)     // 执行回溯算法

    return res
}

func isValid(segment string) bool {    // 判断segment是否可以是ip地址的一部分
    if len(segment) > 1 && segment[0] == '0' {
        // 位数大于1时，第一位不可以为0
        return false
    }

    // 将字符串转化为数字
    var num int
    for i := 0; i < len(segment); i++ {
        num = num*10 + int(segment[i]-'0')
    }
    // 判断范围是否合法
    return 0 <= num && num <= 255
}