day 24|
93. 复原IP地址
93.复原IP地址 | 代码随想录
笔记
本题和上一个分割回文串很像，先复习一下为什么分割问题和组合问题很像：
组合问题：在“abcd”中选择a，然后继续在剩余的“bcd”中选择b......
分割问题：在“abcd”中先分割一个a出来，然后在“bcd”中分割b......
分割问题可以抽象为一个树形结构，所以可以使用回溯算法解决。
树形结构中，第一层表示第一次切割，第二层表示第二次切割......
实操出现问题
1.string的一些常用操作还不熟悉
2.和上一个题目进行比较，这个题目中如果不合法，直接break，但是上一个题目如果不是回文串，应该continue，原因就在于一旦不合法，后边更长的子串一定不合法；而对于上一个题目，小一点的子串可能不合法，但是长一点的子串就有可能合法了。
for循环是横向的搜索，迭代是纵向的搜索，continue就代表了本题的横向剪枝了
代码/比较
class Solution {
private:
vector<string> result;//判断是否合法
bool isIP(string s,int startindex,int i)
{if(i<startindex)return false;//startindex是起始位置，i是终止位置，//如果起始位置是0，则子串非法//在上个的基础下，如果子串转换为int后大于255，非法//如果出现字母，返回falsestring str=s.substr(startindex,i-startindex+1);char first=str[0];if(first=='0'&&startindex!=i)return false;int num=0;//用于转换for(int j=0;j<str.size();j++){if(str[j]>'9'||str[j]<'0')return false;num=num*10+(str[j]-'0');if(num>255)return false;}return true;
}
void backtracking(int startindex,string s,int num)
{//截止条件:如果分割为四个子串(即分割了三次)，则存储结果if(num==3){if(isIP(s,startindex,s.size()-1))result.push_back(s);return;}//单层搜索逻辑：判断当前分割出来的子串是否合法，如果合法则放入path中，不合法则返回，for(int i=startindex;i<s.size();i++){if(isIP(s,startindex,i))//如果合法，则插入逗点，并继续递归{s.insert(s.begin()+i+1,'.');backtracking(i+2,s,num+1);s.erase(s.begin()+i+1);}else break;}return ;
}public:vector<string> restoreIpAddresses(string s) {result.clear();backtracking(0,s,0);return result;}
};
78.子集
笔记：
和之前唯一区别就是这个题目是在每一个树结点处就应该放进result中（之前是在叶子节点才放入）；要注意的是每一次都要放进去。
代码：
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int> nums,int stratIndex){//终止条件：如果到了叶子节点返回；但是在每次循环前都要收集结果result.push_back(path);if(stratIndex>=nums.size())return;//单层搜索逻辑：for(int i=stratIndex;i<nums.size();i++){path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}return;}
public:vector<vector<int>> subsets(vector<int>& nums) {path.clear();result.clear();backtracking(nums,0);return result;}
};
90.子集 II
笔记：
和之前的去重问题一摸一样，不用多注意什么了，再加上了上个问题中的提前收集结果，没什么其他知识点。
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(int stratIndex,vector<int> nums,vector<bool> used){result.push_back(path);//截止条件：如果startIndex超过界限，退出if(stratIndex>=nums.size())return;//单层搜索逻辑：for(int i=stratIndex;i<nums.size();i++){//去重,树层去重if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)continue;else{path.push_back(nums[i]);used[i]=true;backtracking(i+1,nums,used);used[i]=false;path.pop_back();}}return;}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {//首先要排序sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);backtracking(0,nums,used);return result;}
};
1