前言
今日文案：
看到这条信息你必须认真地按照我的要求去做，第一，对着镜子向自己微笑，第二，对着亲友向他们微笑
一、复原IP地址
要命的切割
题目来源：
子集
class Solution { public: vector<string> ans; void backtracking(string s,int startindex,int point_sum) { if(point_sum==3) //打入了三个点就可以收割了 { if(mypi(s,startindex,s.size()-1)) //判断是否符合条件，是的话就收入 { ans.push_back(s); } return; } for(int i=startindex;i<s.size();i++) { if(mypi(s,startindex,i)) //判断一组字符串是否符合条件 { s.insert(s.begin()+i+1,'.'); //符合就插入点 point_sum++; //记录+1 backtracking(s,i+2,point_sum); //i+2是因为打入了一个点，i+1+1 point_sum--; //回溯 s.erase(s.begin()+i+1); } else { break; 如果不符合条件了，这层再继续下去也没有意义，剪枝 } } } bool mypi(string s,int begin,int end) { if(begin>end) { return false; } if(s[begin]=='0'&&end!=begin) //开头不为0 { return false; } int sum=0; for(int i=begin;i<=end;i++) { if(s[i]>'9'&&s[i]<'0') //不能是非正整数 { return false; } sum=sum*10+(s[i]-'0'); //不能超过255 if(sum>255) { return false; } } return true; } vector<string> restoreIpAddresses(string s) { if(s.size()==0) { return ans; } backtracking(s,0,0); return ans; } };
二、子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution { public: vector<int> path; vector<vector<int>> ans; void backtracking(vector<int> nums,int startindex) { ans.push_back(path); //有就直接插入 for(int i=startindex;i<nums.size();i++) //广度遍历 { path.push_back(nums[i]); //插入 backtracking(nums,i+1); //下一层，i+1，从下一个开始，不会重复 path.pop_back(); //回溯 } } vector<vector<int>> subsets(vector<int>& nums) { if(nums.size()==0) { return ans; } backtracking(nums,0); return ans; } };
三、子集||
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
class Solution { public: vector<int> path; vector<vector<int>> ans; void backtracking(vector<int> nums,vector<bool>use,int startindex) { ans.push_back(path); for(int i=startindex;i<nums.size();i++) { if(i>0&&use[i-1]==false&&nums[i]==nums[i-1]) //判断同树层是否用过 { continue; } path.push_back(nums[i]); use[i]=true; //同树枝用，让他可以深度下去 backtracking(nums,use,i+1); path.pop_back(); use[i]=false; //置回false，因为出去就是下一个树层，不是树枝了 } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { if(nums.size()==0) { return ans; } sort(nums.begin(),nums.end()); //排序，让一样的元素挨着 vector<bool>use(nums.size(),false); backtracking(nums,use,0); return ans; } };
总结
数层和树枝问题更加清晰了，分割还要继续熟悉，加油加油
