【代码随想录算法训练Day28】LeetCode 93. 复原 IP 地址、LeetCode 78.子集、LeetCode 90.子集II

93.复原IP地址

使用和分割回文串同样的思路，以 ' . ' 分割字符串，以 start 作为截取的子串的开始位置，i 作为子串的结束位置，单层递归的逻辑就是判断这个子串是否符合ip地址的要求。

正常应采取检验，排除所有非法情况，比如下面这段代码。

// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
    if (start > end) {
        return false;
    }
    if (s[start] == '0' && start != end) { // 0开头的数字不合法
            return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return false;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return false;
        }
    }
    return true;
}

但我这里碰巧了，题目说了是纯数字，但我确实没有考虑到异常输入；并且力扣的测试样例里应该是没有负数的情况，我默认是大于等于0的值，所以这里判断只要小于256就是符合条件的。

对于前导0，我是通过先将字符串转换成整型，这样就得到一个没有前导0的子串对应的值了，再将整型转换回字符串，如果字符串转换前后不一致，则说明有前导0，这种情况要去除。

比较繁琐，正常操作应该是将我这思路用上面的判断是否合法的函数替换掉。

class Solution {
public:
    vector<string> result;
    string path;
    void backtracking(string s, int start, int dot){
        if(dot == 4 && start >= s.size()){
            result.push_back(path.substr(0, path.size()-1));
            return;
        }
        if(dot >= 4){
            return;
        }

        for(int i = start; i < s.size(); i++){
            //采用和分割回文串相同的思路，截取两个'.'之间的字符串进行判断
            //start是上一个'.'的位置，i是下一个'.'的位置，随着i向后移动，改变当前子串的选择
            string str = s.substr(start, i-start+1);
            string tmpstr = path;

            int tmp = atoi(str.c_str());//先转成数字
            string copy = to_string(tmp);//再转回字符串，如果转换前后相等则说明没有前导0
            if(tmp <= 255 && !str.compare(copy)){
                path = path + to_string(tmp) + ".";
                dot++;
            }
            else continue;

            backtracking(s, i+1, dot);

            dot--;
            path = tmpstr;
        }
    }

    vector<string> restoreIpAddresses(string s) {
        backtracking(s, 0, 0);
        return result;
    }
};

78.子集

这题我想记录的思路是从当前输入的元素角度出发的，即选还是不选将当前输入元素加入结果集中。

这种思路的写法如下所示。

首先是进入递归函数种，先将当前元素加入到结果集中，表示选择了当前元素，再进行递归，进到下一层递归，走下一个元素选和不选的分支。有点像二叉树的左右孩子，左是选，右是不选，这种写法就更像是二叉树的遍历了。先一直走选的分支，再回溯到上一层，这时选的元素在结果集中，我们将它pop出来，这样就是不选了，然后再进一次backtracking，走不选这个元素的分支。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int start) {
        if(start >= nums.size()){
            result.push_back(path);
            return;
        }

        path.push_back(nums[start]);
        backtracking(nums, start+1);
        path.pop_back();
        
        backtracking(nums, start+1);
    }

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

上面写法比较便于理解，但和模板不一致，不方便记忆。

按照模板的写法，模板将一部分的递归使用 for 循环迭代实现了，所以看着其实不直观，感受不到这其实像是二叉树的搜索，但思路也是一样的。先选，放进path结果集，走选的分支，然后回溯回来，pop出去当前的元素，走 for 循环，进到下一个元素，这时也是没选当前元素，走到下一个元素了。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        if (startIndex >= nums.size()) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

90.子集II

这题其实就没什么好记录的了，和 组合总和Ⅱ 这题的思路是一样的，都是在有重复元素的数据中，找出不重复的组合。思路就是对树层的去重。详细可以回顾 组合总和Ⅱ 的博客。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int start) {
        result.push_back(path);
        if(start >= nums.size()){
            return;
        }

        for(int i = start; i < nums.size(); i++){
            if(i > start && nums[i-1] == nums[i])
                continue;
            path.push_back(nums[i]);
            backtracking(nums, i+1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return result;
    }
};