93.复原IP地址
思路
本题也是分割问题，与分割回文串相仿，但是细节要求更多！下面说一下容易踩的坑：
- 收集条件判断： 以为和回文串一样，
s为空（或者start下标到末尾）就结束了，实则有逗号数量的要求，这里着重了解s为空的判断方法，使用empty而不是迭代器；对于逗号的计数使用count，语法为：count(ip.begin(),ip.end(),'.') - 收集中的回溯： 在收集时需要去掉末尾的最后一个逗号，但是记得返回时要加回来！因为当前的答案仅仅是一个小树的终止，还要返回父节点继续寻找答案，必须要正确返回。
- for循环边界： 在树层遍历时只考虑
3个没毛病，但是要基于不越界的前提下。
题解
class Solution {
public:
vector<string> res;
string ip;
bool isip(string s)
{
if(s.size()!=1 && s[0] == '0')return false;
else
{
int num = stoi(s);
if(num>=0 && num<=255)return true;
else return false;
}
}
void backtracking(string s)
{
if(count(ip.begin(),ip.end(),'.')>4)return;
if(s.empty() && count(ip.begin(),ip.end(),'.') == 4)
{
ip.pop_back();
res.push_back(ip);
ip += ".";
return;
}
for(int i = 1;i<=3 && i<=s.size();i++)
{
string temp1(s.begin(),s.begin()+i);
if(isip(temp1))
{
ip = ip+temp1+".";
string temp2(s.begin()+i,s.end());
backtracking(temp2);
for(int j = 0;j<=temp1.size();j++)ip.pop_back();
}
}
}
vector<string> restoreIpAddresses(string s) {
backtracking(s);
return res;
}
};
78.子集
思路
子集问题比组合问题还TM的简单！
因为子集问题递归到的情况都要收集，没有判断条件。
渗透子集思想，以及与组合的不同
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums,int start)
{
res.push_back(path);
for(int i = start;i<nums.size();i++)
{
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums,0);
return res;
}
};
90.子集II
思路
与之前组合的去重逻辑一模一样，不多解释。
但是，做该题时对于while该放置的地方疑惑，在宏观上总体思考，要这个子树全部完成后，后面重复跳过，就知道了要放在回溯函数的后面。
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int start)
{
res.push_back(path);
for(int i = start;i<nums.size();i++)
{
path.push_back(nums[i]);
backtracking(nums, i+1);
while(i<nums.size()-1 && nums[i+1] == nums[i])i++;
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
backtracking(nums, 0);
return res;
}
};
马上补完进度了——康宁湖游记