代码随想录Day24_回溯_复原IP.md
复原IP地址题目理解
1.给出的是字符串，IP地址在【0，255】之间，字符串转数字；
2.0可以单独出现，但是不能跟数字出现；
3.字符串中要插入'.';
4.字符串的大小范围在4~12之间；
5.不能有除数字外的字母；
思路
首先确定答案类型：vector res，一个用来存单个有效IP地址的字符串str；
1.函数返回值：void，函数参数，传进来的string s;
2.确定终止条件：插入4个'.'后；
3.单层回溯：
for循环遍历树的宽度:每次startIndex后移一位；
树的深度：每次.后移一位。后移两位。
问题
1.怎么在字符串中插入.? s.insert(pos,'neirong')
https://www.cxy5.com/image-3.png
if(start>end){return false;}该条件是在处理空的字符串！很难想到这个边界条件。
class Solution {
public:
vector<string> res;
void backtrack(string& s, int startIndex, int pointNum) {
if (pointNum == 3) {
if (isValid(s, startIndex, s.size() - 1)) {
res.push_back(s);
}
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isValid(s, startIndex, i)) {
s.insert(s.begin() + i + 1, '.');
pointNum++;
backtrack(s, i + 2, pointNum);
s.erase(s.begin() + i + 1);
pointNum--;
} else {
break;
}
}
return;
}
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
} // 输入：s=101023 输出：10.102.3.
if (s == '0' && start != end) {
return false;
}
int sum = 0;
for (int i = start; i <= end; i++) {
if (s < '0' || s > '9') {
return false;
}
// 255逻辑
sum = sum * 10 + (s - '0');
if (sum > 255) {
return false;
}
}
return true;
}
vector<string> restoreIpAddresses(string s) {
backtrack(s, 0, 0);
return res;
}
};求整数数组的所有子集
开始的时候在想每个整数数组都包含一个空的子集如何处理？写出来了但是不知道在哪里处理到了？
class Solution {public: vectorpath; vectorres; void backtrack(vector&nums, int startIndex){ res.push_back(path); if(startIndex>=nums.size()){ return; } for(int i=startIndex;i=nums.size()){ return; } for(int i=startIndex;i 热心回复！ 感谢，下载保存了
页:
[1]