响应式网站源码,学校网站制作多少钱,线上推广引流渠道,网站建设公司招商93. 复原 IP 地址#xff0c;78. 子集#xff0c; 90. 子集 II 93. 复原 IP 地址78. 子集90. 子集 II 93. 复原 IP 地址
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 0 0 到 255 255 255之间组成#xff0c;且不能含有前导 0 0 0#xff09;#xff0c;整… 93. 复原 IP 地址78. 子集 90. 子集 II 93. 复原 IP 地址78. 子集90. 子集 II 93. 复原 IP 地址
有效 IP 地址 正好由四个整数每个整数位于 0 0 0 到 255 255 255之间组成且不能含有前导 0 0 0整数之间用 ‘.’ 分隔。
例如“ 0.1.2.201 0.1.2.201 0.1.2.201” 和 “ 192.168.1.1 192.168.1.1 192.168.1.1” 是 有效 IP 地址但是 “ 0.011.255.245 0.011.255.245 0.011.255.245”、“ 192.168.1.312 192.168.1.312 192.168.1.312” 和 “ 192.168 1.1 192.1681.1 192.1681.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s s s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s s s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1
输入s “25525511135” 输出[“255.255.11.135”,“255.255.111.35”] 示例 2
输入s “0000” 输出[“0.0.0.0”] 示例 3
输入s “101023” 输出[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]
字符串只包含数字可以直接用int转换判断范围外加前导 0 0 0判断。题目条件是正好所以回溯要到判断index到结尾时候是否满足要求。
class Solution:def restoreIpAddresses(self, s: str) - List[str]: result []path []n len(s)self.backtracking(s,0,n,path,result)return resultdef backtracking(self,s,index,n,path,result):if index len(s) and len(path) 4:result.append(..join(path[:]))return if len(path) 4: # 剪枝returnfor i in range(index,min(n,index3)):if self.is_ip(s[index:i1]):path.append(s[index:i1])self.backtracking(s,i1,n,path,result)path.pop()def is_ip(self,num):if num[0]0 and len(num)1:return False if int(num)0 and int(num)255:return True
78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例 1 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2 输入nums [0] 输出[[],[0]]
不包含重复元素用模板直接回溯不需要判断return条件。
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:result []self.backtracking(nums,0,[],result) return result def backtracking(self,s,index,path,result):result.append(path[:])for i in range(index,len(s)):path.append(s[i])self.backtracking(s,i1,path,result)path.pop()90. 子集 II
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
涉及重复元素问题在回溯前先排序利用递归的时候下一个startIndex是i1而不是0去重对同一树层使用过的元素进行跳过。
示例 1 输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2 输入nums [0] 输出[[],[0]]
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:result []num1 sorted(nums)self.backtracking(num1,0,[],result) return result def backtracking(self,s,index,path,result):result.append(path[:])for i in range(index,len(s)): if iindex and s[i]s[i-1]:continuepath.append(s[i])self.backtracking(s,i1,path,result)path.pop()
