代码随想录算法训练营Day28 | 93.复原IP地址、78.子集、90.子集II | Python | 个人记录向

本文主要是介绍代码随想录算法训练营Day28 | 93.复原IP地址、78.子集、90.子集II | Python | 个人记录向，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

93.复原IP地址

代码随想录：93.复原IP地址
Leetcode：93.复原IP地址

做题

不知道回溯怎么写。

看文章

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

时间复杂度: O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。
空间复杂度: O(n)

另一种实现方法如下：（个人更喜欢这种）

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.子集

代码随想录：78.子集
Leetcode：78.子集

做题

思路简单。

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

时间复杂度: O(n * 2^n)
空间复杂度: O(n)

看文章

需要遍历整棵树，思路一样。

90.子集II

代码随想录：90.子集II
Leetcode：90.子集II

做题

思路没错，要注意：去重需要对数组进行排序。

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:self.size = len(nums)self.res = []self.path = []nums.sort()self.backtracking(nums, 0)return self.resdef backtracking(self, nums, start):self.res.append(self.path[:])for i in range(start, self.size):if i > start and nums[i] == nums[i-1]:continueself.path.append(nums[i])self.backtracking(nums, i+1)self.path.pop()

时间复杂度: O(n * 2^n)
空间复杂度: O(n)

看文章

思路一致，也可以用used数组、set进行去重，但最好的还是上面的实现方法。

以往忽略的知识点小结

• 对于特殊子集问题（比如判断ip），重点是在dfs时，取出这一条树上的数值（使用 start 和 i ），然后做判断（判断是否是ip）

个人体会

完成时间：2h。
心得：主要还是在处理特殊子集上比较有难度，常规的找子集和去重已经没什么问题。

​

这篇关于代码随想录算法训练营Day28 | 93.复原IP地址、78.子集、90.子集II | Python | 个人记录向的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---