代码训练营 Day24 | 93.复原IP地址 |78.子集

93.复原IP地址

1. 怎么模拟切割线，如何固定切割线

   1. startindex就是我们分割线，它控制着下一层递归里面从哪里开始

   2. 从那里开始分割线就在那里

2. 如何去判断子串

伪代码

``` c++ 
vector<string>result;// 递归函数的参数和返回值
void backtracking(s,startindex,pointSum){// 递归终止条件，ip地址一共有三个点，如果已经有三个点了说明已经完成了可以返回答案if(pointSum == 3){// 对ip地址最后一段进行合法判断，isvalid传递的区间是[]左闭右闭区间if(isvalid(s,startindex,s.size()-1)){// 合法的添加到数组result.push_back(s);}return;}// 单层搜索逻辑for(i=startindex,i<s.size(); i++){// 检查切割的子串，是否合法; [startindex,i]是切割的子串if(isvalid(s,startindex,s.size())){s.insert(s.begin()+i+1,'.')// 点的数量加1pointSum += 1;// 递归; 这里是i+2是因为有个点，所以想要找到下一个区间开始的字母要+2backtracking(s,i+2,pointSum)// 回溯s.erase(s.begin()+i+1);pointSum -= 1;}}
}

运行代码

class Solution(object):def isvalid(self,s,start,end):# is invalid intervalif start > end:return False# make sure first number is not zeroif s[start] == '0' and start != end:# if there is only one 0, it's ok; but more than one number is ilegalreturn False        num = 0for i in range(start,end+1):# if it's not number if not s[i].isdigit():return False# every time num *10, to make to 255num = num * 10 + int(s[i])# make sure our number is less than 255if num > 255:return False# otherwise return Truereturn Truedef backtracking(self,s,startindex,current,pointSum,result):# recursion stop conditionif pointSum == 3:# make sure our string is validif self.isvalid(s,startindex,len(s)-1):# add our final ip address to currentcurrent += s[startindex:]# append to final result setresult.append(current)return# recursion logic for each levelfor i in range(startindex,len(s)):# check the string is validif self.isvalid(s,startindex,i):sub = s[startindex:i+1]# recursionself.backtracking(s,i+1,current+sub+'.',pointSum+1,result)else:breakdef restoreIpAddresses(self, s):""":type s: str:rtype: List[str]"""result = []self.backtracking(s,0,"",0,result)return result

78.子集

1. 这题并不是到叶子节点收获结果

2.  因为是组合[1,2]和[2,1]是一样的

3.  在子集问题里面每个节点里面就是我们要收集的结果

class Solution(object):def backtracking(self,nums,strartindex,path,result):# collect our result setresult.append(path[:])# recursion end conditionif strartindex >= len(nums):# we finished all the saerchreturn# recursion for each levelfor i in range(strartindex,len(nums)):# add our number into arraypath.append(nums[i])# recursionself.backtracking(nums,i+1,path,result)# backtrackingpath.pop()def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""result = []self.backtracking(nums,0,[],result)return result