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

目录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.1681.1是无效IP 地址。给定一个只包含数字的字符串s用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在s中插入.来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。解题思路本题同131. 分割回文串都是分割字符串区别就在判断合法的逻辑本题由于题目中给定所有字符均为数字故只需要考虑区间在1~255和无无效前导零我的前导零判断逻辑是该数为两位及两位以上并且首位为0class 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:i1]) self.backtracking(s,i1) self.path.pop() def if_valid(self,s,start,end): str_ s[start:end1] 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,i1) 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,i1) self.used[i] False self.path.pop()