【leetcode刷刷】93.复原IP地址、78.子集、90.子集II

本文主要是介绍【leetcode刷刷】93.复原IP地址、78.子集、90.子集II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

93.复原IP地址

跟之前的分割序列很像，所以也比较好想

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:# 找3个分割点？# 最后一个分割点的时候，判断path，加入res# 不符合规则的就跳过self.res = []self.backtracking(s, 0, [])return self.resdef backtracking(self, s, start_index, path):if len(path) == 4 and start_index == len(s):self.res.append(".".join(path))returnif len(path) > 4: return for i in range(start_index, len(s)):if i - start_index > 2: continueif self.is_valid(s[start_index:i+1]):path.append(s[start_index:i+1])self.backtracking(s, i+1, path)path.pop()def is_valid(self, s):if s[0] == '0' and len(s) > 1:return Falseif int(s) > 255: return Falsereturn True

78.子集

和组合的思路是一样的，而且应该不能剪枝吧
self.res.append(path[:])在回溯上面，可以使得[]也在答案里面

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:# 所有的子集，不能包含重复子集# 元素互不相同，所以子集不会重复    # 和组合问题的区别是什么？？？？self.res = [[]]self.backtracking(nums, 0, [])return self.resdef backtracking(self, nums, start_index, path):self.res.append(path[:])for i in range(start_index, len(nums)):path.append(nums[i])self.backtracking(nums, i+1, path)path.pop()

90.子集II

这个去重，和组合的去重是一样的。要注意一定要先排序。刚写的时候忘记了。

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