假电影网站做注册,邢台做网站可信赖,wordpress页面侧边栏消失,docker wordpress 备份93.复原IP地址
题目链接
讲解链接
本题属于切割问题#xff0c;切割问题需要使用回溯算法来将所有的结果搜索出来#xff0c;与前一题分割回文串是类似的。本题的树形结构如下图所示#xff1a; 回溯三部曲#xff1a;
1.递归函数参数及返回值#xff1a;参数为待分割…93.复原IP地址
题目链接
讲解链接
本题属于切割问题切割问题需要使用回溯算法来将所有的结果搜索出来与前一题分割回文串是类似的。本题的树形结构如下图所示 回溯三部曲
1.递归函数参数及返回值参数为待分割的字符串s以及标记每次切割起始位置的index。
def backtracking(self, s, index):
2.递归终止条件当index位于字符串的末尾并且path的长度为4时意味着终止此时将path中的4个字符串用“.”连接起来并存入result中就得到了一个结果。
if index len(s) and len(self.path) 4:self.result.append(..join(self.path))return
if len(self.path) 4:return
3.单层递归逻辑在每轮循环中截取[startIndex, i]这个区间作为字串并判断这个子串是否合法。若合法则将其加入path中然后从i1的位置开始下一轮递归。
for i in range(index, len(s)):if self.isvalid(s, index, i):self.path.append(s[index:i 1])self.backtracking(s, i 1)self.path.pop()
整体代码如下
class Solution:def __init__(self):self.path []self.result []def isvalid(self, s, start, end): # 判断是否符合IP地址的格式if start end:return Falseif s[start] 0 and start ! end: # 不能有前导0return Falsenum int(s[start:end1])if num 255: # 数值必须小于等于255return Falsereturn Truedef backtracking(self, s, index):if index len(s) and len(self.path) 4: # 当path长度为4且index位于字符串末尾时终止self.result.append(..join(self.path)) # 将path中的值用“.”连接起来放入result中returnif len(self.path) 4: # 剪枝操作若长度大于4则直接返回不需要进行后续搜索returnfor i in range(index, min(index 3, len(s))): # min是为了剪枝不加也可以if self.isvalid(s, index, i):self.path.append(s[index:i 1])self.backtracking(s, i 1)self.path.pop()def restoreIpAddresses(self, s: str) - List[str]:self.backtracking(s, 0)return self.result
78.子集
题目链接
讲解链接
组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点。子集中集合是无序的取过的元素不会重复取所以写回溯算法的时候for就要从startIndex开始而不是从0开始。
总体思路与组合问题相差不大主要就是要注意取的是所有节点而不仅仅是叶子节点。
回溯三部曲
1.递归函数参数及返回值数组nums和开始位置strartindex。
def backtracking(self, nums, startindex):
2.递归终止条件当startindex位于数组末尾时直接返回。
if startindex len(nums):return 3.单层递归逻辑与组合问题基本一致每次递归下标从i1开始
for i in range(startindex, len(nums)):self.path.append(nums[i])self.backtracking(nums, i 1)self.path.pop()
整体代码如下
class Solution:def __init__(self):self.path []self.result []def backtracking(self, nums, startindex):self.result.append(self.path[:]) # 每次递归时都要先收获结果if startindex len(nums): # 终止条件returnfor i in range(startindex, len(nums)):self.path.append(nums[i])self.backtracking(nums, i 1)self.path.pop()def subsets(self, nums: List[int]) - List[List[int]]:self.backtracking(nums, 0)return self.result
90.子集Ⅱ
题目链接
讲解链接
本题与上一题相比主要区别在于数组中包含重复元素如果依旧按照原来的方法求子集最后结果中会有重复所以需要进行去重。而且是在树层上去重而不是树枝。去重的过程则和之前做过的组合总和问题类似可以考虑使用used数组来进行标记也可以直接在for循环中进行判断。整体代码如下
class Solution:def __init__(self):self.path []self.result []def backtracking(self, nums, startindex):self.result.append(self.path[:]) # 添加结果if startindex len(nums): # 终止条件也可以不写returnfor i in range(startindex, len(nums)):if i startindex and nums[i] nums[i - 1]: # 如果istartindex并且与前一个元素相同那么说明这个元素已经使用过了本轮循环直接continue即可continueself.path.append(nums[i])self.backtracking(nums, i 1)self.path.pop()def subsetsWithDup(self, nums: List[int]) - List[List[int]]:nums sorted(nums) # 去重问题一定要先对数组进行排序self.backtracking(nums, 0)return self.result
