代码随想录算法训练营第二十九天|93.复原IP地址 78.子集 90.子集II

93.复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1：

• 输入：s = "25525511135"
• 输出：["255.255.11.135","255.255.111.35"]

示例 2：

• 输入：s = "0000"
• 输出：["0.0.0.0"]

示例 3：

• 输入：s = "1111"
• 输出：["1.1.1.1"]

示例 4：

• 输入：s = "010010"
• 输出：["0.10.0.10","0.100.1.0"]

示例 5：

• 输入：s = "101023"
• 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 0 <= s.length <= 3000
• s 仅由数字组成

思路：

本题和其他字符串切割的题目类似，只是在切割点处应该用“.”连接起来得到一个IP地址，需要注意的是每个分割后的字段转换为数字后应该保持在0-255的范围内，此处注意点也是可以作为剪枝的方向。另外一个需要注意的点是前导0，如果在切割的时候发现存在前导0，此时不应该继续扩大字段，存在0的字段只能为0。

代码实现如下：

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:self.result = []if len(s) > 12:     # IP最长长度为3*4（255.255.255.255），此处可剪枝return self.resultself.backtracking(s, 0, [])return self.resultdef backtracking(self, s:str, start:int, path:List):if len(path)==4 and start>=len(s):self.result.append(".".join(path))cur = 0#zero = False      # 本来想判断是否存在前导0，但是如果存在并不需要进一步判断,如果cur*10+s[i]等于0说明只能做切割for i in range(start, len(s)):cur = cur * 10 + int(s[i])#if zero==False and cur==0:if cur == 0:#zero = Truepath.append(str(cur))self.backtracking(s, i+1, path)path.pop()returnif cur>0 and cur<=255:path.append(str(cur))self.backtracking(s, i+1, path)path.pop()if cur>255:         #一个段最大为255，大于则剪枝return

规范代码：

回溯（版本一）

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:result = []self.backtracking(s, 0, 0, "", result)return resultdef backtracking(self, s, start_index, point_num, current, result):if point_num == 3:  # 逗点数量为3时，分隔结束if self.is_valid(s, start_index, len(s) - 1):  # 判断第四段子字符串是否合法current += s[start_index:]  # 添加最后一段子字符串result.append(current)returnfor i in range(start_index, len(s)):if self.is_valid(s, start_index, i):  # 判断 [start_index, i] 这个区间的子串是否合法sub = s[start_index:i + 1]self.backtracking(s, i + 1, point_num + 1, current + sub + '.', result)else:breakdef is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = 0for i in range(start, end + 1):if not s[i].isdigit():  # 遇到非数字字符不合法return Falsenum = num * 10 + int(s[i])if num > 255:  # 如果大于255了不合法return Falsereturn True

回溯（版本二）

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:results = []self.backtracking(s, 0, [], results)return resultsdef backtracking(self, s, index, path, results):if index == len(s) and len(path) == 4:results.append('.'.join(path))returnif len(path) > 4:  # 剪枝returnfor i in range(index, min(index + 3, len(s))):if self.is_valid(s, index, i):sub = s[index:i+1]path.append(sub)self.backtracking(s, i+1, path, results)path.pop()def is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = int(s[start:end+1])return 0 <= num <= 255

78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]

思路：

将本题问题可以归结为分别对0~len(nums)个数组长度的切割，所以在回溯函数backtracking中加入length参数，并且从0~len(nums）循环输入进这个参数来进行调用，最后得到的结果数组即可。

代码实现如下：

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:self.result = []for i in range(len(nums)+1):self.backtracking(nums, 0, [], i)return self.resultdef backtracking(self, nums:List[int], start:int, path:List, length:int):if length == 0:self.result.append(path[:])returnfor i in range(start, len(nums)):path.append(nums[i])self.backtracking(nums, i+1, path, length-1)path.pop()

规范代码：（简洁很多，需学习）

class Solution:def subsets(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集，要放在终止添加的上面，否则会漏掉自己# if startIndex >= len(nums):  # 终止条件可以不加#     returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

90.子集II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

• 输入: [1,2,2]
• 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

思路：

与上一题相比，多了一个去重步骤，和昨天的题目类似，在开始一个for循环的时候，判断遍历的元素是否与for循环中前一个元素相同，如果相同，说明此时在相同位置出现了同样的元素，所得到的结果必然也是相同的，所以此时应该忽略，寻找下一个不相同的元素。

代码实现如下：

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:self.result = []nums.sort()for i in range(len(nums)+1):       # i代表子集的长度（0~len（nums））self.backtracking(nums, 0, [], i)return self.resultdef backtracking(self, nums: List[int], start:int, path:List, length:int):if length == 0:self.result.append(path[:])returnfor i in range(start, len(nums)):if i>start and nums[i]==nums[i-1]: # 避免重复结果，一个循环内同元素可跳过，相当于起点是相同元素，不会得到不同结果continuepath.append(nums[i])self.backtracking(nums, i+1, path, length-1)path.pop()

规范代码：

回溯 利用used数组去重

class Solution:def subsetsWithDup(self, nums):result = []path = []used = [False] * len(nums)nums.sort()  # 去重需要排序self.backtracking(nums, 0, used, path, result)return resultdef backtracking(self, nums, startIndex, used, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# used[i - 1] == True，说明同一树枝 nums[i - 1] 使用过# used[i - 1] == False，说明同一树层 nums[i - 1] 使用过# 而我们要对同一树层使用过的元素进行跳过if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:continuepath.append(nums[i])used[i] = Trueself.backtracking(nums, i + 1, used, path, result)used[i] = Falsepath.pop()

回溯 利用集合去重

class Solution:def subsetsWithDup(self, nums):result = []path = []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集uset = set()for i in range(startIndex, len(nums)):if nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

回溯 利用递归的时候下一个startIndex是i+1而不是0去重

class Solution:def subsetsWithDup(self, nums):result = []path = []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# 而我们要对同一树层使用过的元素进行跳过if i > startIndex and nums[i] == nums[i - 1]:continuepath.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()