目录
93. 复原 IP 地址 - 力扣（LeetCode）
题目描述
解题思路
78. 子集
题目描述
解题思路
90. 子集 II
题目描述
解题思路
93. 复原 IP 地址 - 力扣（LeetCode）
题目描述
有效 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 地址。
- 例如：
给定一个只包含数字的字符串
s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在s中插入'.'来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。
解题思路
- 本题同131. 分割回文串，都是分割字符串，区别就在判断合法的逻辑，本题由于题目中给定所有字符均为数字，故只需要考虑区间在
1~255和无无效前导零 - 我的前导零判断逻辑是：该数为两位及两位以上，并且首位为0
class Solution: def restoreIpAddresses(self, s: str) -> List[str]: self.path = [] self.res = [] self.backtracking(s,0) return self.res def backtracking(self,s,start): if start >= len(s) and len(self.path) == 4: self.res.append('.'.join(self.path[:])) return for i in range(start,len(s)): if self.if_valid(s,start,i): self.path.append(s[start:i+1]) self.backtracking(s,i+1) self.path.pop() def if_valid(self,s,start,end): str_ = s[start:end+1] num = int(str_) if num < 0 or num > 255:return False if s[start] == '0' and end != start:return False return True78. 子集
题目描述
给你一个整数数组
nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
解题思路
- 将过程中收集的
path都记录到res,path长度等于res时当前路径停止回溯
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: self.path = [] self.res = [[]] self.backtracking(nums,0) return self.res def backtracking(self,nums,start): if len(self.path) == len(nums): return for i in range(start,len(nums)): self.path.append(nums[i]) self.res.append(self.path[:]) self.backtracking(nums,i+1) self.path.pop()90. 子集 II
题目描述
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
解题思路
- 本题类似于40. 组合总和 II，特别注意的是都要先进行排序，不然重复的元素就不在一起，结果有误
class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: self.path = [] self.res = [] self.used = [False] * len(nums) nums.sort() self.backtracking(nums,0) return self.res def backtracking(self,nums,start): self.res.append(self.path[:]) if len(self.path) == len(nums): return for i in range(start,len(nums)): if i > 0 and nums[i] == nums[i - 1] and self.used[i-1] == False: continue self.used[i] = True self.path.append(nums[i]) self.backtracking(nums,i+1) self.used[i] = False self.path.pop()
