代码随想录算法训练营第二十七天 93.复原IP地址、78.子集、90.子集II

代码随想录算法训练营第二十七天 93.复原IP地址、78.子集、90.子集II

93.复原IP地址

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址

状态：AC

思路

因为IP地址有一定的局限性（在0~255范围内），这道题我采用了两种方法，一种直接暴力算法，三重循环。另一种使用回溯。题目中给定字符串s为潜在的IP地址，其长度在[1, 20]。那么他的合法长度在[4, 12]之间，可以先做一些判定。无论是暴力算法还是回溯算法，查找的均为字符串的分割处。

1. 暴力算法

数学的范围都为闭区间，字符串的范围均为左闭右开！！！

数学的范围都为闭区间，字符串的范围均为左闭右开！！！

数学的范围都为闭区间，字符串的范围均为左闭右开！！！

  • 第一层范围[1, 3]，使用指针i
    • 分割出字符串s1 = s[0: i]，判断是否有前导0，判断转换成数字n1后是否在[0, 255]之间
  • 第二层范围[i+1, 6]，使用指针j
    • 分割出字符串s2 = s[i: j]，判断是否有前导0，判断长度是否大于3，判断转换成数字n2后是否在[0, 255]之间
  • 第三层范围[j+1, 9]，使用指针k
    • 分割出字符串s3 = s[j: k]，判断是否有前导0，判断长度是否大于3，判断转换成数字n3后是否在[0, 255]之间
    • 分割出字符串s4 = s[k:]，判断是否有前导0，判断长度是否大于3，判断转换成数字n4后是否在[0, 255]之间

均合法，则拼接IP地址n1 + "." + n2 + "." + n3 + "." + n4

代码

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
56
57
58
59
60
61
62
63
64
65
66

class Solution {
private:
    vector<string> result;
    string path;

    void backTracking(string s, int index, int count) {
        if (count > 3) {
            return;
        }
    }

    int getNum(string s) {
        int num = 0;
        if (s == "0") {
            return 0;
        }
        if (s[0] - '0' == 0 && s.size() > 1 || s.size() == 0) {
            return -1;
        }
        for (char i : s) {
            num *= 10;
            num += (i - '0');
        }

        return num;
    }

public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4) {
            return result;
        }
        int n1, n2, n3, n4;
        for (int i = 1; i <= 3; ++i) {
            n1 = getNum(s.substr(0, i));
            if (0 <= n1 && n1 <= 255) {
                for (int j = i + 1; j <= 6 || j < s.size() - 1; ++j) {
                    if (j - i > 3) {
                        break;
                    }
                    n2 = getNum(s.substr(i, j - i));
                    if (0 <= n2 && n2 <= 255) {
                        for (int k = j + 1; k <= 9 || k < s.size(); ++k) {
                            if (k - j > 3) {
                                break;
                            }
                            if (s.size() - k > 3) {
                                continue;
                            }
                            n3 = getNum(s.substr(j, k - j));
                            if (0 <= n3 && n3 <= 255) {
                                n4 = getNum(s.substr(k));
                                if (0 <= n4 && n4 <= 255) {
                                    result.push_back(to_string(n1) + "." + to_string(n2) + "." + to_string(n3) + "." +
                                                     to_string(n4));
                                }
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
};

这代码真是又臭又长啊。

2. 回溯算法

递归三部曲

vector<string> result存放最终结果

vector<int> path存放待切割的位置

  1. 确立函数和返回值：
    • 字符串s
    • 当前位置index
  2. 递归终止条件：
    • 当path长度为3，意味着可以切割四块，开始切割操作，切割后判断合法性，均合法加入result中
    • 当path长度大于3，return
  3. 单次递归：
    • 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

class Solution {
private:
    vector<string> result;
    vector<int> path;

    void backTracking(string s, int index) {
        if (path.size() == 3) {
            string s1 = s.substr(0, path[0]);
            if (s1.size() > 3) {
                return;
            }
            string s2 = s.substr(path[0], path[1] - path[0]);
            if (s2.size() > 3) {
                return;
            }
            string s3 = s.substr(path[1], path[2] - path[1]);
            if (s3.size() > 3) {
                return;
            }
            string s4 = s.substr(path[2]);
            if (s4.size() > 3) {
                return;
            }
            int n1 = getNum(s1);
            int n2 = getNum(s2);
            int n3 = getNum(s3);
            int n4 = getNum(s4);
            if (0 <= n1 && n1 <= 255 &&
                0 <= n2 && n2 <= 255 &&
                0 <= n3 && n3 <= 255 &&
                0 <= n4 && n4 <= 255) {
                result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
            }
            return;
        }
        for (int i = index; i <= s.size(); ++i) {
            path.push_back(i);
            backTracking(s, i + 1);
            path.pop_back();
        }
    }

    int getNum(string s) {
        int num = 0;
        if (s == "0") {
            return 0;
        }
        if (s[0] - '0' == 0 && s.size() > 1 || s.size() == 0) {
            return -1;
        }
        for (char i: s) {
            num *= 10;
            num += (i - '0');
        }

        return num;
    }

public:

    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4) {
            return result;
        }
        backTracking(s, 1);
        return result;
    }
};

结构清晰了很多，可读性很好。

78. 子集

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集

状态：AC

思路

组合问题，这道题的每个元素不重复，做起来很简单，求出所有情况。

递归三部曲

vector<vector<int>> result存放最终结果

vector<int> path存放单次集合

  1. 确定函数和参数：
    • 数组nums
    • 当前位置index
  2. 确定终止条件：第一层的递归结束（或无）
  3. 单次递归：
    • 单次集合加入到最终结果中
    • 单次集合加入新的元素
    • 下一层递归
    • 反向操作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backTracking(vector<int> &nums, int index) {
        result.push_back(path);
        for (int i = index; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backTracking(nums, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsets(vector<int> &nums) {
        backTracking(nums, 0);
        return result;
    }
};

90. 子集II

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：回溯算法解决子集问题，如何去重？| LeetCode：90.子集II

状态：AC

思路

基本同上一题，但是增加了可重复元素，需要去重。去重在我的博客40. 组合总和II

这道题做之前要先排序

vector<vector<int>> result：存放最终结果

vector<int> path：存放单次集合

递归三部曲

  1. 确定函数和参数
    • 数组nums
    • 当前索引index
    • 判断元素是否使用过的used
  2. 递归终止条件：无
  3. 单次递归：
    • 单次集合加入最终结果
    • 当i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false说明之前已经遍历过，continue
    • path加入下个元素
    • used[i] == true下个元素标记被使用过
    • 下一层递归
    • 反向操作

代码

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
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backTracking(vector<int> &nums, int index, vector<bool> &used) {
        result.push_back(path);
        for (int i = index; i < nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backTracking(nums, i + 1, used);
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backTracking(nums, 0, used);
        return result;
    }
};
刷题
#LeetCode #算法 #代码随想录 #回溯算法
代码随想录算法训练营第二十七天 93.复原IP地址、78.子集、90.子集II
https://promisewang.github.io/post/ff1e328.html
作者
Promise
发布于
2023年10月20日
许可协议