东营企业网站排名优化无为教育网站

当前位置： 首页 > news >正文

东营企业网站排名优化,无为教育网站,做一家网站,wordpress单屏模板93.复原IP地址 给定一个只包含数字的字符串#xff0c;复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。 例如#xff1a;…93.复原IP地址 给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。 有效的 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 地址。 示例 1 输入s 25525511135输出[255.255.11.135,255.255.111.35] 示例 2 输入s 0000输出[0.0.0.0] 示例 3 输入s 1111输出[1.1.1.1] 示例 4 输入s 010010输出[0.10.0.10,0.100.1.0] 示例 5 输入s 101023输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3] 提示 0 s.length 3000s 仅由数字组成 思路 本题和其他字符串切割的题目类似只是在切割点处应该用“.”连接起来得到一个IP地址需要注意的是每个分割后的字段转换为数字后应该保持在0-255的范围内此处注意点也是可以作为剪枝的方向。另外一个需要注意的点是前导0如果在切割的时候发现存在前导0此时不应该继续扩大字段存在0的字段只能为0。 代码实现如下 class Solution:def restoreIpAddresses(self, s: str) - List[str]:self.result []if len(s) 12:     # IP最长长度为3*4255.255.255.255此处可剪枝return self.resultself.backtracking(s, 0, [])return self.resultdef backtracking(self, s:str, start:int, path:List):if len(path)4 and startlen(s):self.result.append(..join(path))cur 0#zero False      # 本来想判断是否存在前导0但是如果存在并不需要进一步判断,如果cur*10s[i]等于0说明只能做切割for i in range(start, len(s)):cur cur * 10  int(s[i])#if zeroFalse and cur0:if cur 0:#zero Truepath.append(str(cur))self.backtracking(s, i1, path)path.pop()returnif cur0 and cur255:path.append(str(cur))self.backtracking(s, i1, path)path.pop()if cur255:         #一个段最大为255大于则剪枝return 规范代码 回溯版本一 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 回溯版本二 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:i1]path.append(sub)self.backtracking(s, i1, 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:end1])return 0 num 255 78.子集 给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。 说明解集不能包含重复的子集。 示例: 输入: nums [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ] 思路 将本题问题可以归结为分别对0~len(nums)个数组长度的切割所以在回溯函数backtracking中加入length参数并且从0~len(nums循环输入进这个参数来进行调用最后得到的结果数组即可。 代码实现如下 class Solution:def subsets(self, nums: List[int]) - List[List[int]]:self.result []for i in range(len(nums)1):self.backtracking(nums, 0, [], i)return self.resultdef backtracking(self, nums:List[int], start:int, path:List, length:int):if length 0:self.result.append(path[:])returnfor i in range(start, len(nums)):path.append(nums[i])self.backtracking(nums, i1, path, length-1)path.pop() 规范代码简洁很多需学习 class Solution:def subsets(self, nums):result []path []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集要放在终止添加的上面否则会漏掉自己# if startIndex len(nums):  # 终止条件可以不加#     returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i 1, path, result)path.pop() 90.子集II 给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。 说明解集不能包含重复的子集。 示例: 输入: [1,2,2]输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 思路 与上一题相比多了一个去重步骤和昨天的题目类似在开始一个for循环的时候判断遍历的元素是否与for循环中前一个元素相同如果相同说明此时在相同位置出现了同样的元素所得到的结果必然也是相同的所以此时应该忽略寻找下一个不相同的元素。 代码实现如下 class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:self.result []nums.sort()for i in range(len(nums)1):       # i代表子集的长度0~lennumsself.backtracking(nums, 0, [], i)return self.resultdef backtracking(self, nums: List[int], start:int, path:List, length:int):if length 0:self.result.append(path[:])returnfor i in range(start, len(nums)):if istart and nums[i]nums[i-1]: # 避免重复结果一个循环内同元素可跳过相当于起点是相同元素不会得到不同结果continuepath.append(nums[i])self.backtracking(nums, i1, path, length-1)path.pop() 规范代码 回溯 利用used数组去重 class Solution:def subsetsWithDup(self, nums):result []path []used [False] * len(nums)nums.sort()  # 去重需要排序self.backtracking(nums, 0, used, path, result)return resultdef backtracking(self, nums, startIndex, used, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# used[i - 1] True说明同一树枝 nums[i - 1] 使用过# used[i - 1] False说明同一树层 nums[i - 1] 使用过# 而我们要对同一树层使用过的元素进行跳过if i 0 and nums[i] nums[i - 1] and not used[i - 1]:continuepath.append(nums[i])used[i] Trueself.backtracking(nums, i 1, used, path, result)used[i] Falsepath.pop() 回溯 利用集合去重 class Solution:def subsetsWithDup(self, nums):result []path []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集uset set()for i in range(startIndex, len(nums)):if nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])self.backtracking(nums, i 1, path, result)path.pop() 回溯 利用递归的时候下一个startIndex是i1而不是0去重 class Solution:def subsetsWithDup(self, nums):result []path []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# 而我们要对同一树层使用过的元素进行跳过if i startIndex and nums[i] nums[i - 1]:continuepath.append(nums[i])self.backtracking(nums, i 1, path, result)path.pop()