93.复原IP地址
一个合法的IP地址是什么样的：
有3个’.'分割得到4个数，每个数第一个数不能是0，不能含有非法字符，不能大于255。
这个是否属于合法IP相当于一个分割问题，把一串字符串分割成4部分，分别判断每个部分是否合法，如果全部合法就保存结果，否则就return;
回溯三部曲：
- 确定参数和返回值：参数要处理的字符串s,startIndex来防止我们重复分割和pointNum存储当前加的’.‘的个数。我们把path（存储当前的字符串）和result(存储加了’.'符合合法IP条件的字符串的结果列表）定义为了全局变量所以不需要返回值。
- 递归终止条件：if(pointNum==3)说明我们已经加了三个’.'，然后直接判断最后一个数字是否合法，如果合法就保存结果，如果不合法就return。
- 单层递归逻辑：我们就是把整体字符串分段，分别判断每一段分割结果是否合法，如果合法就往字符串中加’.'，并且递归调用backtracking进行下一次分割如果不合法就直接return不操作。
当前分割的结果：startIndex指明当前循环中开始位置在这个循环过程中是不变的，i不断地向右循环，[startIndex, i]就是当前处理的字符串（就是IP地址中的一段，那段数字，我们只需要判断这段数字是否合法就可以）。
分割标志：startIndex就是相当于分割标志，指明了前一次分割的位置。
下面是C++、JAVA、Python的代码。
class Solution {
private:vector<string> result;bool isValid(const string& s, int start, int end){if(start>end){return false;}if(s[start]=='0' && start != end){//0开头的数字不合法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){//数字大于255不合法return false;}}return true;}void backtracking(string& s, int startIndex, int pointSum){if(pointSum == 3){//对最后一段的合法性进行判断if(isValid(s, startIndex, s.size()-1)){//result.push_back(s);}return;}//递归终止条件for(int i = startIndex; i < s.size(); i++){//单层递归if(isValid(s, startIndex, i)){s.insert(s.begin()+i+1, '.');pointSum += 1;backtracking(s, i+2, pointSum);s.erase(s.begin()+i+1);pointSum-=1;}}}
public:vector<string> restoreIpAddresses(string s) {if (s.size() < 4 || s.size() > 12) return result;backtracking(s, 0, 0);return result;}
};
class Solution {List<String> result = new ArrayList<>();//建立一个列表存储最终结果public List<String> restoreIpAddresses(String s) {backtracking(s, 0, 0);return result;}private void backtracking(String s, int startIndex, int pointNum){if(pointNum == 3){//如果逗号数量为3停止向下递归if(isValid(s, startIndex, s.length()-1)){result.add(s);}return;}for(int i = startIndex; i < s.length(); i++){//单层递归逻辑if(isValid(s, startIndex, i)){//如果合法s = s.substring(0, i+1) + "." + s.substring(i + 1);//在str的后面插入"."pointNum++;backtracking(s, i+2, pointNum);//pointNum--;//回溯s = s.substring(0, i+1) + s.substring(i+2);//回溯删掉逗点，substring一个参数是从beginIndex开始到末尾，有两个参数从 beginIndex 开始到 endIndex 结束前（不包括 endIndex）提取子字符串}else{break;}}}//判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法private Boolean isValid(String s, int start, int end){if(start > end){return false;}//start和end本身就不合法if(s.charAt(start) == '0' && start != end){//0开头的数字不合法return false;}int num = 0;//这个是存储从字符串变成数字的数字for(int i = start; i <= end; i++){//判断每个字符的合法性if(s.charAt(i) > '9' || s.charAt(i)<'0'){return false;}num = num*10 + (s.charAt(i)-'0');//这个就是计算当前的数字if(num > 255){//如果大于255了不合法return false;}}return true;}
}
class Solution(object):def __init__(self):self.result = []def restoreIpAddresses(self, s):""":type s: str:rtype: List[str]"""if(len(s)<4 or len(s)>12):return self.resultself.backtracking(s, 0, 0)return self.resultdef backtracking(self, s, startIndex, pointNum):#递归终止条件if(pointNum == 3):if(self.isValid(s, startIndex, len(s)-1)):self.result.append(s)#如果合法就存入for i in range(startIndex, len(s)):if(self.isValid(s, startIndex, i)):s = s[:i+1]+'.'+s[i+1:]pointNum+=1#往字符串中加入一个点self.backtracking(s, i+2, pointNum)s = s[:i+1] + s[i+2:]pointNum -= 1#回溯def isValid(self, s, start, end):#判断所给字符的合法性，左闭右闭区间#首先判断传入的参数是否合法if(start > end):return False#判断是否开头有0if s[start] == '0' and start!=end:return Falsenum = 0#这个是存储当前这个子串对应的数值的for i in range(start, end+1):if s[i]>'9' or s[i]<'0':return False #判断每个字符是否合法num = num*10 + int(s[i])if(num > 255):return False#超出255非法return True参考文章
- https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
78.子集
遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
注意：这个题目时每个节点的结果都要保存，不是只保存叶子节点。其他的和组合差不多。
回溯三部曲：
1. 确定参数和返回值：参数就是数组nums和startIndex指示之前使用了那些元素，防止重复取数。我们把path金额result定义为全局变量，所以不需要返回值。
2. 遍历终止条件：startIndex>= nums.size() return;就是如果startIndex超出了数组的范围就停止递归。
单层递归的逻辑：i从startIndex到nums.size()遍历，每次遍历都把nums[i]当前元素加入到path当前结果中，然后backtracking()继续下层递归，然后path.pop_back()回溯。
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startIndex){result.push_back(path);if(startIndex>= nums.size()) return;//递归终止条件for(int i = startIndex; i < nums.size(); i++){path.push_back(nums[i]);backtracking(nums, i+1);path.pop_back();}return;}
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};
class Solution {List<Integer> path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();public void backtracking(int[] nums, int startIndex){result.add(new ArrayList<>(path));if(startIndex>=nums.length){return;//递归终止条件}for(int i=startIndex; i < nums.length; i++){path.add(nums[i]);backtracking(nums, i+1);path.removeLast();}}public List<List<Integer>> subsets(int[] nums) {backtracking(nums, 0);return result;}
}
class Solution(object):def __init__(self):self.result = []self.path = []def backtracking(self, nums, startIndex):self.result.append(list(self.path))#别忘了这个加list为了就是不指向同一个地址if(startIndex>=len(nums)):returnfor i in range(startIndex, len(nums)):self.path.append(nums[i])#存入元素self.backtracking(nums, i+1)self.path.pop()def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""self.backtracking(nums, 0)return self.result参考文章
- https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
90.子集II
这个就是子集和组合Ⅱ的应用。
秒了。
注意：
- 对于有重复元素的题目，要去重，先排序。
- 设置used数组来判断时树枝还是树层。每个语言怎么定义要清楚。
- 保存结果的时候要根据每个语言，JAVA和Python都是需要处理一下path再加入到result中，不然result中的元素都指向同一个位置，最后结果都[]
- 去重的两行代码要记住。
回溯三部曲：
- 确定参数和返回值：参数时数组nums和startIndex，返回值为None。
- 递归终止条件：看startIndex是否越界，如果越界就直接返回。没有也可以，因为后面for循环也会因为startIndex越界不运行直接return。
- 单层递归逻辑：加入去重的两行代码if(i>0 && nums[i]==nums[i-1] && used[i-1]==0)continue;（直接跳过，到不是重复的数，不是break，break会漏掉重复数字之后的所有的数字）然后把当前数字放到path中，更新used使当前索引的位置used[i]=true，然后backtracking()递归处理下一个数，path.pop(),used[i]=false回溯一下。
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startIndex, vector<bool> used){result.push_back(path);//想一下递归的终止条件// if(startIndex >= nums.size()) return;for(int i = startIndex; i < nums.size(); i++){if(i>startIndex && nums[i]==nums[i-1] && used[i-1]==0){continue;//跳过重复元素}path.push_back(nums[i]);used[i] = true;backtracking(nums, i+1, used);used[i] = false;path.pop_back();}}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return result;}
};
class Solution {List<Integer> path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();public void backtracking(int[] nums, int startIndex, boolean[] used){result.add(new ArrayList<>(path));//想想递归终止条件if(startIndex>=nums.length) return;for(int i = startIndex; i< nums.length; i++){if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}path.add(nums[i]);used[i] = true;backtracking(nums, i+1, used);used[i] = false;path.removeLast();}}public List<List<Integer>> subsetsWithDup(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backtracking(nums, 0, used);return result;}
}
class Solution(object):def __init__(self):self.result = []self.path = []def backtracking(self, nums, startIndex, used):self.result.append(list(self.path))if(startIndex>=len(nums)):#递归终止条件也可以不写returnfor i in range(startIndex, len(nums)):if(i>startIndex and nums[i] == nums[i-1] and not used[i-1]):continue#去重self.path.append(nums[i])used[i] = Trueself.backtracking(nums, i+1, used)used[i] = Falseself.path.pop()def subsetsWithDup(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()#别忘了排序used = [False]*len(nums)self.backtracking(nums, 0, used)return self.result参考文章
- https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
