刷题分享
1.(力扣131)这是一道分割子串的问题,其核心在于理解清除startindex即为当前切割线,而每一层对应的startindex-I这个区间,其实就是当前分割出来的子串
class Solution {
public:
vector<vector<string>>res;
vector<string>path;
bool judge(string s,int l,int r){
while(l<r){
if(s[l]==s[r]){
l++;
r--;
}else{
return false;
}
}
return true;
}
void backtracking(string s,int startindex){
if(startindex>=s.size()){
res.push_back(path);
return ;
}
for(int i=startindex;i<s.size();i++){
if(judge(s,startindex,i)){
string tem;
tem=s.substr(startindex,i-startindex+1);
//substr的第二个参数是截取元素的个数,而非结束位置
path.push_back(tem);
backtracking(s,i+1);
}else{
continue;
}
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
backtracking(s,0);
return res;
}
};
2.(力扣93)这道题的核心是掌握在递归调用里,引用的特殊性,每一层递归里的s在逻辑上可以看作是独立的个体,虽然名字相同,但它们有着各自独立的 “生命周期” 和状态管理,res里存储的是之前各层递归结束那一刻对应的s的状态,后续递归中对当前层s的改动不会传导过去
class Solution {
public:
vector<string>res;
bool judge(string s,int l,int r){
if(l>r){
return false;
}
if(s[l]=='0'&&l!=r){
return false;
}
int num=0;
for(int i=l;i<=r;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(judge(s,startindex,s.size()-1)){
res.push_back(s);
}
return ;
}
for(int i=startindex;i<s.size();i++){
if(judge(s,startindex,i)){
s.insert(s.begin()+i+1,'.');
pointnum++;
backtracking(s,i+2,pointnum);
}else{
break;
}
s.erase(s.begin()+i+1);
pointnum--;
}
}
vector<string> restoreIpAddresses(string s) {
backtracking(s,0,0);
return res;
}
};
标签:12,return,string,int,res,startindex,分享,backtracking,刷题
From: https://blog.csdn.net/2401_86941858/article/details/144197007