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

前言之前就有刷代码随想录但奈何总是三天打鱼两天晒网而且刷的也很囫囵吞枣于是乎决定参加代码随想录训练营准备精刷一遍希望自己能坚持下去结营后自己的算法水平能更上一个level冲ingleetcode93.复原IP地址题目链接leetcode93.复原IP地址思路本题和上一题分割回文子串的思路类似区别主要在于如下:1、递归函数参数需要增加一个pointNum用于记录添加的分隔符’.’数量2、终止条件题目要求将字符串分割成固定的四段也就是需要三个’.‘所以终止条件是当piontNum 3 时分割结束并且判断第四段的字符是否合法如果合法就加入到result中3、单层搜索逻辑中递归调用函数自己时startIndex不再是i1而是要从i2开始因为多加入了’.。代码classSolution{private:vectorstringresult;// 记录结果// startIndex: 搜索的起始位置pointNum:添加逗点的数量voidbacktracking(strings,intstartIndex,intpointNum){if(pointNum3){// 逗点数量为3时分隔结束// 判断第四段子字符串是否合法如果合法就放进result中if(isValid(s,startIndex,s.size()-1)){result.push_back(s);}return;}for(intistartIndex;is.size();i){if(isValid(s,startIndex,i)){// 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin()i1,.);// 在i的后面插入一个逗点pointNum;backtracking(s,i2,pointNum);// 插入逗点之后下一个子串的起始位置为i2pointNum--;// 回溯s.erase(s.begin()i1);// 回溯删掉逗点}elsebreak;// 不合法直接结束本层循环}}// 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法boolisValid(conststrings,intstart,intend){if(startend){returnfalse;}if(s[start]0start!end){// 0开头的数字不合法returnfalse;}intnum0;for(intistart;iend;i){if(s[i]9||s[i]0){// 遇到非数字字符不合法returnfalse;}numnum*10(s[i]-0);if(num255){// 如果大于255了不合法returnfalse;}}returntrue;}public:vectorstringrestoreIpAddresses(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); // 注意从i1开始元素不重复取然后回溯把刚加入path中的元素弹出。注意什么时候for可以从0开始呢——求排列问题的时候就要从0开始因为集合是有序的{1, 2} 和{2, 1}是两个集合即回溯算法中的排列问题大类。注意result.push_back(path);本题收集子的位置是有说法的要放在终止添加的上面否则会漏掉自己。例如要是放到if终止条件判断之后for循环之前那么当startIndex遍历到集合中最后一个位置时这个“满的”集合会被丢弃代码classSolution{private:vectorvectorintresult;vectorintpath;voidbacktracking(vectorintnums,intstartIndex){result.push_back(path);// 收集子集要放在终止添加的上面否则会漏掉自己if(startIndexnums.size()){// 终止条件可以不加return;}for(intistartIndex;inums.size();i){path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}public:vectorvectorintsubsets(vectorintnums){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:vectorvectorintresult;vectorintpath;voidbacktracking(vectorintnums,intstartIndex,vectorboolused){result.push_back(path);for(intistartIndex;inums.size();i){// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 而我们要对同一树层使用过的元素进行跳过if(i0nums[i]nums[i-1]used[i-1]false){continue;}path.push_back(nums[i]);used[i]true;backtracking(nums,i1,used);used[i]false;path.pop_back();}}public:vectorvectorintsubsetsWithDup(vectorintnums){result.clear();path.clear();vectorboolused(nums.size(),false);sort(nums.begin(),nums.end());// 去重需要排序backtracking(nums,0,used);returnresult;}};