leetcode系列
文章目录
- 一、核心操作
- 二、外层配合操作
- 三、核心模式代码
- 总结
一、核心操作
- 判断字段是否有效函数：首先start不能大于end
当到最后一个收获层的时候，start已经是s.size了，但是end还是只能是s.size-1其次当字段不止一位时，start不能是0，然后再循环判断每一位是不是处于字符‘0’和‘9’之间，以及通过num*10+当前数字的操作求出值，判断是不是大于255 - 回溯函数：传参中多了一个pointNum，用于判断有几个点，如果到了3个点，就把剩下的字段传入 是否有效函数 如果有效就可以收获结果了，并且不管有没有收获，到了3个点就要返回。在每一层的循环中，对于字段的有效性做出判断，如果有效则在i的后面位置加点，并将pointNum++，
注意由于加了点，输入下一层的startIndex是i+2，并进行回溯；如果无效的话直接break
提示：小白个人理解，如有错误敬请谅解！
二、外层配合操作
- 调用回溯函数
三、核心模式代码
代码如下：
class Solution {
public:vector<string> res;bool isValid(string s, int start, int end){if(start>end)return false;if(s[start]=='0' && start!=end)return false;if((end-start+1)>3)return false;int num=0;for(int i=start;i<=end;i++){if(s[i]>'9' || s[i]<'0')return false;num=num*10+(s[i]-'0');if(num>255)return false;}return true;}void backtracking(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++;backtracking(s,i+2,pointNum);s.erase(s.begin()+i+1);pointNum--;}else break;}}vector<string> restoreIpAddresses(string s) {if(!s.size())return res;backtracking(s,0,0);return res;}
};
总结
- 需要多注意字段有效性的判断
