兰州做高端网站的公司,四川网站建设平台,荆州松滋网站建设,网站优化的学习216.组合总和|||
思路#xff1a;和上题一样#xff0c;差别在于多了总和#xff0c;但是数字局限在1-9
17.电话号码的字母组合
思路#xff1a;先纵向遍历第i位电话号码对于的字符串#xff0c;再横向递归遍历下一位电话号码
93.复原IP地址
画图分析#xff1a; 思…216.组合总和|||
思路和上题一样差别在于多了总和但是数字局限在1-9
17.电话号码的字母组合
思路先纵向遍历第i位电话号码对于的字符串再横向递归遍历下一位电话号码
93.复原IP地址
画图分析 思路一
先横向遍历限制遍历数最大为3因为IP值最多为三位并且起始位3要小于字符串长度
判断当前切的字符串是否满足IP值不满足的话下一个
然后纵向递归判断当前切的第几刀
如果当前切的第四刀以1开始相当于分成四份则进行判断添加作为终止条件如果当前还没切到第四刀则继续横向遍历
最后回溯直接用resize覆盖掉当前遍历添加字符串的长度
class Solution {
public:vectorstringres;string mid;void backtrace(const string s,int start,int curb){//start是开始的位置 curb是切割的次数if(curb4){//cout123;if(s.size()-start3) return;string midss.substr(start,s.size()-1);if(judge(mids)){midmids;res.push_back(mid);mid.resize(mid.size()-mids.size());//回溯覆盖当前添加的字符串} return; }for(int i1;i3;i){//横向遍历//couti;if(startis.size())//剩下的大于需要分配的break;string s1s.substr(start,i);//第if(!judge(s1)) continue;mids1;mid.;backtrace(s,starti,curb1);//纵向递归//coutmid;//回溯覆盖mid.resize(mid.size()-s1.size()-1);}}bool judge(string s){if(s.empty()) return false;if(s.size()1 s[0]0) return false;//排除0开头的字符串int numstoi(s);return num0 num255;}vectorstring restoreIpAddresses(string s) {backtrace(s,0,1);return res;}
};
