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

代码随想录一刷记录Day24——leetcode93.复原IP地址 78.子集 90.子集II

news 2026/6/12 4:33:47

前言

之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！

leetcode93.复原IP地址

题目链接leetcode93.复原IP地址

思路

本题和上一题分割回文子串的思路类似，区别主要在于如下:
1、递归函数参数：需要增加一个pointNum用于记录添加的分隔符’.’
数量
2、终止条件：题目要求将字符串分割成固定的四段，也就是需要三个’.‘，所以终止条件是当piontNum == 3 时分割结束，并且判断第四段的字符是否合法，如果合法就加入到result中
3、单层搜索逻辑中递归调用函数自己时，startIndex不再是i+1，而是要从i+2开始，因为多加入了’.'。

代码

classSolution{private:vector<string>result;// 记录结果// startIndex: 搜索的起始位置，pointNum:添加逗点的数量voidbacktracking(string&s,intstartIndex,intpointNum){if(pointNum==3){// 逗点数量为3时，分隔结束// 判断第四段子字符串是否合法，如果合法就放进result中if(isValid(s,startIndex,s.size()-1)){result.push_back(s);}return;}for(inti=startIndex;i<s.size();i++){if(isValid(s,startIndex,i)){// 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin()+i+1,'.');// 在i的后面插入一个逗点pointNum++;backtracking(s,i+2,pointNum);// 插入逗点之后下一个子串的起始位置为i+2pointNum--;// 回溯s.erase(s.begin()+i+1);// 回溯删掉逗点}elsebreak;// 不合法，直接结束本层循环}}// 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法boolisValid(conststring&s,intstart,intend){if(start>end){returnfalse;}if(s[start]=='0'&&start!=end){// 0开头的数字不合法returnfalse;}intnum=0;for(inti=start;i<=end;i++){if(s[i]>'9'||s[i]<'0'){// 遇到非数字字符不合法returnfalse;}num=num*10+(s[i]-'0');if(num>255){// 如果大于255了不合法returnfalse;}}returntrue;}public:vector<string>restoreIpAddresses(string s){result.clear();if(s.size()<4||s.size()>12)returnresult;// 算是剪枝了backtracking(s,0,0);returnresult;}};

leetcode78.子集

题目链接leetcode78.子集

思路

本题属于回溯问题的另一大类，即子集问题，和之前的组合问题、分割问题最大的区别是：收集结果的时机不同。前两类问题都是递归到最深层（相当于到叶子节点）才满足条件并收集结果，而子集问题每一个节点都是要收集的。
回溯三部曲解题：

递归参数
依旧全局变量path收集元素和result存放子集组合，递归函数的参数未传入的nums数组和startIndex
递归终止条件
当剩余的集合为空时就是叶子节点，也就是startIndex已经大于数组的长度了，就终止，因为后面已经没有元素可取
单层搜索逻辑
依旧for循环起手，for (inti = startIndex; i < nums.size(); i++)，将num[i]放入path，然后调用自己递归backtracking(nums, i + 1); // 注意从i+1开始，元素不重复取，然后回溯（把刚加入path中的元素弹出）。
注意：什么时候for可以从0开始呢？——>求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，即回溯算法中的排列问题大类。

注意：result.push_back(path);本题收集子的位置是有说法的，要放在终止添加的上面，否则会漏掉自己。例如要是放到if终止条件判断之后，for循环之前，那么当startIndex遍历到集合中最后一个位置时，这个“满的”集合会被丢弃！

代码

classSolution{private:vector<vector<int>>result;vector<int>path;voidbacktracking(vector<int>&nums,intstartIndex){result.push_back(path);// 收集子集，要放在终止添加的上面，否则会漏掉自己if(startIndex>=nums.size()){// 终止条件可以不加return;}for(inti=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);returnresult;}};

leetcode90.子集II

题目链接leetcode90.子集II

思路

本题和上一道78.子集的主要区别在于本题给的nums中含重复元素，并且求取的子集中要去重。去重的思路和之前的40.组合综合Ⅱ一个套路（注意树层去重和树枝去重的区别），同时别忘了去重要先排序！
例如nums = { 1， 2 ，2}同一树层上重复取2 就要过滤掉（通过used数组中的0/1标记是否取过），同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

代码

classSolution{private:vector<vector<int>>result;vector<int>path;voidbacktracking(vector<int>&nums,intstartIndex,vector<bool>&used){result.push_back(path);for(inti=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);returnresult;}};