当前位置：首页 > article >正文

【代码随想录回溯算法|子集问题】

article 2024/11/17 23:00:26

93.复原ID地址

题目链接：https://leetcode.cn/problems/restore-ip-addresses

这里是先加点再从加了点之后的数进行递归，因为我如果先递归，就不方便找到原来字符串末尾，也就不好加点了，所以你只要是正确的串我就赶紧在你背后加个点。再继续往下递归，注意这里往下递归因为加了点要从i+2开始。

backtracing(s, startindex, i+2);

笑死，最开始我的递归代码长这样，还老奇怪呢，为啥老是超时hhh。这里中间把i+2当做startindex继续往下遍历了，第三个参数按道理应该是点的个数

class Solution {
public:
    vector<string> result;
    bool isvalue(string &s,int start,int end){
        if(start>end)return false;
        if(s[start]=='0'&&end!=start)return false;
         int num=0;
        for(int i=start;i<=end;i++){
            if(s[i]<'0'||s[i]>'9'){
                return false;
            }
            num=num*10+(s[i]-'0');
            if(num<0||num>255){
                return false;
            }
        }
        return true;
    }
    void backtracing(string& s, int startindex, int pointnum) {
        if (pointnum == 3) {
            if (isvalue(s, startindex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startindex;i<s.size();i++){
            if(isvalue(s,startindex,i)){
            s.insert(s.begin()+i+1,'.');
            pointnum++;
            backtracing(s, i+2, pointnum);
            s.erase(s.begin()+i+1);
            pointnum--;}
            else break;
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.size()<=3||s.size()>12)return result;
        backtracing(s, 0, 0);
        return result;
    }
};

78.子集

题目链接https://leetcode.cn/problems/subsets

这道题收集结果的条件跟之前的就不一样了，因为之前的题我们在叶子结点中发现满足条件就进行收集，这道题题目要求是要把求子集，所以要把每一次遍历，就是每一个结点进行收集，所以只要我的startindex指向的集合是空集，我已经没有可以继续选择的元素了，那就进行回溯。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, int startindex) {
        result.push_back(path);//把第一个元素（空集）放进来
        if (startindex >= nums.size())//超过startindex指向的集合已经没有元素了就回溯
            return;
        for (int i = startindex; i < nums.size(); i++) {
            path.push_back(nums[i]);//每遍历到一个节点就收集
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

90.子集||

题目链接https://leetcode.cn/problems/subsets-ii

思路我觉得跟组合去重是一样的，就是我要进行去重，就先引入和nums大小一致的used数组进行判断我每个数是否使用过，我把nums进行排序，因为我进行去重的时候要判断两个数是否相同，如果他们挨在一起，直接比较nums[i]==nums[i-1]，代码更方便一些。然后进入递归里面，在宽度为nums.size()的宽度下进行递归（因为我要从每个节点开始来进行选择），这个时候我们就可以进行树层去重了

树层去重：两个数一样（且前一个数之前没用过used[i-1]==0），那我选择之后的数的时候就必然会和前一个用过的数重复，这是我们要舍弃的，所以直接continue我们进行下一次选择。

树枝去重：两个数一样（且前一个数之前用过used[i-1]==1），说明我前一个数也放进了我们的集合里面，那就说明我们同一个path选择里面的数，只是恰好相等罢了，那没关系直接加入到path里面

class Solution {
public:
    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++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){
                    continue;//树层去重，拜拜了您嘞
            }
            path.push_back(nums[i]);//加入数要在判断之后加，否则起不到去重的作用
            used[i]=true;
            backtracking(nums,i+1,used);
            used[i]=false;//used也要重置为false
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool>used(nums.size(),false);//要在主函数定义used的值
                                       //因为在外面不知道nums的大小也定义不了hhhh
        sort(nums.begin(),nums.end());//对nums进行排序
        backtracking(nums,0,used);
        return result;
    }
};

查看全文

http://www.kler.cn/a/397877.html