淘宝上做网站怎么样,pc端网站开发工具,世界搜索引擎公司排名,网站商城运营模式第24天#xff0c;回溯算法part03#xff0c;牢记回溯三部曲#xff0c;掌握树形结构结题方法#x1f4aa;
目录
93.复原IP地址
78.子集
90.子集II
总结 93.复原IP地址 文档讲解#xff1a;代码随想录复原IP地址 视频讲解#xff1a;手撕复原IP地址 题目#xff1…第24天回溯算法part03牢记回溯三部曲掌握树形结构结题方法
目录
93.复原IP地址
78.子集
90.子集II
总结 93.复原IP地址 文档讲解代码随想录复原IP地址 视频讲解手撕复原IP地址 题目 学习本题属于切割类问题不同的是本题需要使用 · ’ 来切割并且本题对切割的数字大小和多少切割多少次都有要求。但本质都是两步1.切割2.判断切割是否正确。
依据以上两点本题和131.分割回文串不同的地方就在于对分割部分的判断和终止条件的选择。回溯逻辑用树形结构来表示为 注意判断分割部分是否合法主要从三个部分出发1.段位以0为开头且不止有0的数字不合法。2.段位里有非正整数字符不合法。3.段位如果大于255了不合法。
代码确定回溯三部曲注意本题要在字符串中加入 . 因此回溯的时候要删掉该点。
//时间复杂度O(3^4)
//空间复杂度O(n)
class Solution {
public://直接在字符串上进行操作因此不设置路径数组vectorstring result; //返回数组//确定返回值和参数列表直接在答案数组中插入因此不需要返回值参数中需要原字符串s分割点startindex//本题还需要一个int型变量point表示当前逗号的数量void backtracking(string s, int startindex, int point) {//确定终止条件当逗号数量为3个时说明当前分割已经完成了if(point 3) {//最后一部分字符串还需要进行判断if(ipvaild(s, startindex, s.size() - 1)) {result.push_back(s);}return;}//确定单层递归逻辑for(int i startindex; i s.size(); i) {//startindex作为切割线切割的字符串区间为[startindex, i]左闭右闭//判断切割下来的字符串是否合理if(ipvaild(s, startindex, i)){//如果合理的话在字符串下标i后插入逗号并进行下一轮递归s.insert(s.begin() i 1, .);point;//注意这里需要传入的是i2因为加了一个逗号切割的位置需要往后移两位backtracking(s, i 2, point);point--; //回溯s.erase(s.begin() i 1);}else { //假如不满足后续的切割方法也难以满足直接跳出本层循环break;}}}bool ipvaild(string s, int start, int end) {if (start end) {return false;}//如果存在前置0的话返回falseif(start ! end s[start] 0) {return false;}int num 0; //对切割字符串进行求和for(int i start; i end; i) {if(s[i] - 0 0 || s[i] - 0 9) {return false;}num num * 10 (s[i] - 0);if(num 255) {return false;}}return true;}vectorstring restoreIpAddresses(string s) {backtracking(s, 0, 0);return result;}
};
本题可以进行剪枝自认为本题可以从三个部分进行剪枝分别是1.剪枝1给的字符串不满足切割有效的IP地址2.剪枝2分割实际只需要分割3个字符就行缩小循环范围3.每次切割后可以判断一下是否后面的字符还能够满足切割要求。
代码
class Solution {
public://切割问题主要需要两点切割判断//直接在字符串上进行操作因此不设置路径数组vectorstring result; //返回数组//确定返回值和参数列表直接在答案数组中插入因此不需要返回值参数中需要原字符串s分割点startindex//本题还需要一个int型变量point表示当前逗号的数量void backtracking(string s, int startindex, int point) {//确定终止条件当逗号数量为3个时说明当前分割已经完成了if(point 3) {//最后一部分字符串还需要进行判断if(ipvaild(s, startindex, s.size() - 1)) {result.push_back(s);}return;}//确定单层递归逻辑//剪枝2分割只需要分割3个数字就够了for(int i startindex; i startindex 3; i) {//剪枝3后续剩余的节点数不满足切割要求if(s.size() - startindex (4 - point) * 3 || s.size() - startindex (4 - point)) {break;}//startindex作为切割线切割的字符串区间为[startindex, i]左闭右闭//判断切割下来的字符串是否合理if(ipvaild(s, startindex, i)){//如果合理的话在字符串下标i后插入逗号并进行下一轮递归s.insert(s.begin() i 1, .);point;//注意这里需要传入的是i2因为加了一个逗号切割的位置需要往后移两位backtracking(s, i 2, point);point--; //回溯s.erase(s.begin() i 1);}else { //假如不满足后续的切割方法也难以满足直接跳出本层循环break;}}}bool ipvaild(string s, int start, int end) {if (start end) {return false;}//如果存在前置0的话返回falseif(start ! end s[start] 0) {return false;}int num 0; //对切割字符串进行求和for(int i start; i end; i) {if(s[i] - 0 0 || s[i] - 0 9) {return false;}num num * 10 (s[i] - 0);if(num 255) {return false;}}return true;}vectorstring restoreIpAddresses(string s) {//剪枝1给的字符串不满足切割有效的ip地址if(s.size() 4 || s.size() 12) return result;backtracking(s, 0, 0);return result;}
}; 78.子集 文档讲解代码随想录子集 视频讲解手撕子集问题 题目 学习回溯算法能够解决的第三类问题子集问题。子集问题与切割问题和组合问题的本质不同在于切割问题和组合问题都是在叶子节点收获结果但是子集问题需要在每个节点都收获结果这也导致了子集问题对result数组push_back的位置不同但其他部分其实几乎是一致的。子集问题其实也能看作是一个组合问题因此也需要注意去重。回溯逻辑转化为树形结构为 代码确定回溯三部曲
//时间复杂度O(n*2^n)
//空间复杂度O(n)
class Solution {
public:vectorvectorint result; //返回数组vectorint path; //保存路径//确定返回值和参数列表在数组中直接进行操作所以不需要返回值参数列表需要遍历的数组和当前遍历的下标void backtracking(vectorint nums, int startindex) {//子集问题的不同在于子集收获答案是在每个节点均收货一次//在终止条件前先进行收获其中也包含了空集result.push_back(path);//确定终止条件(其实等于就可以了)遍历到最后//该终止条件也可以不写因为当startindex nums.size()时下面的for循环也不会进入但要注意for循环后加return。if(startindex nums.size()) {return;}//确定单层递归逻辑for(int i startindex; i nums.size(); i) {path.push_back(nums[i]);//传入i1防止出现重复backtracking(nums, i 1);path.pop_back();}return;}vectorvectorint subsets(vectorint nums) {backtracking(nums, 0);return result;}
}; 90.子集II 文档讲解代码随想录子集II 视频讲解手撕子集II 题目 学习本题和上一题不同点在于本题存在重复元素需要对后续的相同元素进行去重事实上本题和组合总和II的去重是相同的本质都是如果后面出现了与前面相同的元素就可以跳过该元素的遍历因为前面的元素一定把后面的元素还有的组合都包括的。基于此本题可以采取和40.组合总和II相同的去重方式都是在树层进行去重。
代码确定回溯三部曲
//时间复杂度O(n*2^n)
//空间复杂度O(n)
class Solution {
public: vectorvectorint result; //返回答案数组vectorint path; //保存路径//确定参数和返回值void backtracking(vectorint nums, int startindex) {//收集每一个节点result.push_back(path);//确定终止条件if(startindex nums.size()) {return;}//确定单层递归逻辑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();}return;}vectorvectorint subsetsWithDup(vectorint nums) {//进行排序便于去重sort(nums.begin(), nums.end());backtracking(nums, 0);return result;}
}; 总结
切割问题首尾子集问题开始牢记子集问题和切割问题和组合问题的不同。
