代码随想录训练营第二十八天打卡| 93.复原IP地址 78.子集 90.子集II

93.复原IP地址

1.本题即使有了之前切割的例子，但其实仍然是比较困难的。因为之前的模板并不完全适用，甚至可以说只有回溯与切割的思路是适用的，其它的具体实现与之前有较大差异。比如之前的路径是个数组，递归时发现此时路径不满足结果，只需要回溯数组的最后一个元素就行。而本题的结果集的字符串数组，意味着你的路径是字符串，而字符串是不好回溯的。例：本题路径先收集了255.，之后又收集了192.变成255.192.。此时发现之后切割的字符串不再满足要求对路径进行回溯操作，这时候你会觉得如何把192.进行回溯是一件困难的事，因为字符串是连在一起的！这就要求我们转变思路，把字符串本身作为路径，合法切割在后面+'.',不合法把'.'删除重新切割，这种思路的转换对于字符串不熟悉的同学来说并不简单。其次，终止条件的选取以及切割的字符串是否合法的判断都有许多细节，在此不多赘述详情见注释。

class Solution {
private:
vector<string> result;
void backtracking(string& s,int startIndex,int pointNum){
    if(pointNum==3){//逗号数量
       if(isIp(s,startIndex,s.size()-1)){//判断第4段字符串是否合法
            result.push_back(s);
       }
        return;
    }
    for(int i=startIndex;i<s.size();i++){
        if(isIp(s,startIndex,i)){
            s.insert(s.begin()+i+1,'.');//合法字符串后面+'.'
            pointNum++;
            backtracking(s,i+2,pointNum);//因为多了个'.'，所以i+2
            pointNum--;
            s.erase(s.begin()+i+1);//在字符串本身操作，回溯只需要去'.'
        }
        else break;//不合法，结束本层循环
    }
}
bool isIp(string s,int start,int end){//判断分割的字符串是否合法
    if(start>end) return false;
    if(s[start]=='0'&&start!=end) return false;//0开头的非零数字不合法
    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;
}
public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return result; // 剪枝
        backtracking(s,0,0);
        return result;
    }
};

78.子集

1.一开始我选择了一个笨办法，即把数组大小从0到题目数组大小的数组用一个for循环收集一遍。回溯就是之前的模板，提交后时间开销意外的不错。

class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums,int startIndex,int size){
    if(path.size()==size){//收集大小为size的所有数组
        result.push_back(path);
        return;
    }
    for(int i=startIndex;i<nums.size();i++){
        path.push_back(nums[i]);//加入路径数组
        backtracking(nums,i+1,size);//递归之后的元素
        path.pop_back();//回溯
    }
}
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        for(int i=0;i<=nums.size();i++){
            backtracking(nums,0,i);//把所有的组合都收集一遍
        }
        return result;
    }
};

2.看了题解之后才发现自己是多此一举了，遇到数组直接收集就行了。而题目数组元素各不相同以及递归位置从下一位开始则保证了数组不会重复。

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        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) {
        backtracking(nums, 0);
        return result;
    }
};

90.子集II

本题是子集问题的进阶，数组中出现了重复元素，要求我们进行去重操作。那是树枝去重还是树层去重呢？像[1,1,2,2,2]这样的数组显然可以收集，所以是树层去重。去重要先进行排序，去重意味着在for循环中，之前某个元素开头的数组已经全部收集完了，之后再有相同元素开头直接跳过。

1.startIndex去重版本

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            if (i > startIndex && nums[i] == nums[i - 1]) //去重
                continue;
            path.push_back(nums[i]);   //加入路径数组
            backtracking(nums, i + 1); //递归之后的元素
            path.pop_back();           //回溯
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); //去重需要先排序
        backtracking(nums, 0);
        return result;
    }
};

2.set去重版

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) //去重
                continue;
            uset.insert(nums[i]);
            path.push_back(nums[i]);   //加入路径数组
            backtracking(nums, i + 1); //递归之后的元素
            path.pop_back();           //回溯
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); //去重需要先排序
        backtracking(nums, 0);
        return result;
    }
};

3.used数组去重

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 而我们要对同一树层使用过的元素进行跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return result;
    }
};

今日总结：IP啊，你复原真困难！