网站建设高端培训班功能分类模块类型网站

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

网站建设高端培训班,功能分类模块类型网站,wordpress拖曳式建站,微信公众号模板素材网站理论回顾 回溯法也可以叫做回溯搜索法#xff0c;它是一种搜索的方式。回溯是递归的副产品#xff0c;只要有递归就会有回溯。 回溯的本质是穷举#xff0c;穷举所有可能#xff0c;然后选出我们想要的答案#xff0c;如果想让回溯法高效一些#xff0c;可以加一些剪枝…理论回顾 回溯法也可以叫做回溯搜索法它是一种搜索的方式。回溯是递归的副产品只要有递归就会有回溯。 回溯的本质是穷举穷举所有可能然后选出我们想要的答案如果想让回溯法高效一些可以加一些剪枝的操作但也改不了回溯法就是穷举的本质。 回溯法一般可以解决如下几种问题 组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等 理解回溯 回溯法解决的问题都可以抽象为树形结构是所有回溯法的问题都可以抽象为树形结构 因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度就构成了树的深度。 递归就要有终止条件所以必然是一棵高度有限的树N叉树。 回溯法模板 回溯函数模板返回值以及参数回溯函数终止条件回溯搜索的遍历过程

1. 组合 要点 以暴搜为起点进行思考的话搜索k为2时的结果可以使用两个嵌套for循环实现。将k拓展到大于2的数可以发现用同样的思路解决问题就需要做k次嵌套的for循环。肯定无法解决本题的问题。 实际上在回溯算法中k次嵌套其实就是算法中递归的深度了通过递归来解决不定次数的嵌套循环即可轻松解决。 解法 树形结构 输入输出两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合。 两个参数既然是集合n里面取k个数那么n和k是两个int型的参数。然后还需要一个参数为int型变量startIndex这个参数用来记录本层递归的中集合从哪里开始遍历 终止条件到达满足输出要求叶子节点 单步逻辑for循环每次从startIndex开始遍历然后用path保存取到的节点i。 实现 class Solution:def combine(self, n: int, k: int) - List[List[int]]:# 创建所有结果的总表results list()self.backtracking(n, k, 1, [], results)return resultsdef backtracking(self, n, k, start_idx, path, results):# 终止条件 当path长度达到了要求 表示已经深入到了叶子节点if len(path) k:results.append(path[:])returnfor i in range(start_idx, n 1):path.append(i)# 使用递归来完成等价多个for循环的嵌套self.backtracking(n, k, i 1, path, results)# 回溯步 撤销本层的遍历结果path.pop() 将for循环的右区间换成下面这个表达就可以进行特定情况下的剪枝。含义是已经选择的元素个数 len(path) ; 还需要的元素个数为: k - len(path)还需要选择的元素数量不能大于数组中剩余的数量。 for i in range(startIndex, n - (k - len(path)) 2):pass
2. 组合总和 III 要点 转换成树形问题之后可以观察到和组合的相似之处。遍历的宽度是确定值9个数而深度则是k目标值是n。  解法 全局变量依然需要一维数组path来存放符合条件的结果二维数组result来存放结果集 输入输出1. 目标和n2. 数量k3. 目标和sum4. 起始索引start_idx 终止条件path.size() 和 k相等了就终止; 单步逻辑添加一步总和累加和回溯减去即可 实现 class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:results list()self.backtracking(n, k, 0, 1, [], results)return resultsdef backtracking(self, tar_sum, num_count, cur_sum, start_idx, path, results):if cur_sum tar_sum:returnif len(path) num_count:if cur_sum tar_sum:results.append(path[:])returnfor i in range(start_idx, 9 - (num_count - len(path)) 2):path.append(i)cur_sum iself.backtracking(tar_sum, num_count, cur_sum, i 1, path, results)cur_sum - ipath.pop()
3. 电话号码的字母组合 要点 一个数字会对应多个字母可能出现多个数字。因此这里需要一个index来指向正在遍历的数字。 实现 class Solution:def init(self):self.letterMap [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.result []def get_comb(self, digits, idx, sub_res):# 当索引和数字总长一致时添加字母结果并返回if idx len(digits):self.result.append(sub_res)return# 通过数字取字母数组letter_str self.letterMap[int(digits[idx])]# 通过for循环将每个数组中的结果依次加入子结果for letter in letter_str:self.get_comb(digits, idx 1, sub_res letter)def letterCombinations(self, digits: str) - List[str]:if len(digits) 0:return []self.get_comb(digits, 0, )return self.result
4. 组合总和 要点 本题没有数量要求可以无限重复但是有总和的限制所以间接的也是有个数的限制。终止条件则应设定为超过目标值则判断并返回。 解法 全局变量一个sub_res存放单个path一个results存放所有结果 输入输出和组合总和基本类似原始数组目标值记录一个当前值总和开始索引分支结果和全部结果。 和之前的不同在于在backtrack中将start_idx设置成当前循环索引即不用额外做i1。 实现 class Solution:def backtrack(self, candidates, target, cur_sum, start_idx, sub_res, results):if cur_sum target:returnif cur_sum target:results.append(sub_res[:])return for i in range(start_idx, len(candidates)):cur_sum candidates[i]sub_res.append(candidates[i])# 之前使用了i 1 这里直接从i开始表示可以重复使用self.backtrack(candidates, target, cur_sum, i, sub_res, results)cur_sum - candidates[i]sub_res.pop()def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:results []self.backtrack(candidates, target, 0, 0, [], results)return results
5. 组合总和 II 要点 这里指定了每个数字只能使用一次数组candidates的元素是有重复的且解集中不能有重复结果。 在回溯中的去重本质就是使用过的元素不能重复选取。 已知组合问题可以抽象为树形结构那么“使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上使用过一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 会导致不能彻底理解去重。 转换成树形结构可以总结元素在同一个组合内是可以重复的怎么重复都没事但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。 想要进行树层的去重首先需要对候选数组进行一次排序。除此之外此题还需要加一个bool型数组used来记录每个元素的使用情况。最核心的理解在于回溯中的递归以上图为例假设在第一个分支里已经取过了第二个1那么在第二个分支中应该忽略掉连续取两个1的情况因为同样的结果已经出现在了第一个递归的分支中。 used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过 这里就体现了排序的必要性只有先进行排序才能确保只对前一位的使用情况进行判断就能够去除所有重复大小颠倒的组合情况被自然消除了。 解法 输入参数输入数组目标数值总和起始索引已使用元素记录单条路径最终结果 终止条件达到target返回遇到重复或超过目标值分别跳过和停止递归 单步逻辑按照上述描述进行去重传入新的startindex进行递归计算 实现 class Solution:def backtrack(self, candidates, target, total, start_idx, used, path, result):if total target:result.append(path[:])returnfor i in range(start_idx, len(candidates)):# 去重逻辑 只去除相同数字 且上一个相同数字没用的情况if i start_idx and candidates[i] candidates[i - 1] and not used[i - 1]:continue# if total target:break# 三个变量依次修改total candidates[i]path.append(candidates[i])used[i] True# 从i 1开始 保证正确递归顺序self.backtrack(candidates, target, total, i 1, used, path, result)used[i] Falsepath.pop()total - candidates[i]def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:used [False] * len(candidates)result []candidates.sort()self.backtrack(candidates, target, 0, 0, used, [], result)return result
6. 分割回文串 要点 这里提出了需要返回所有可能的分割方案观察可得所谓的分割其实也是一种组合问题。 例如对于字符串abcdef 组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段。 所以此类切割的问题可以转换成树形问题 解法: 输入输出本题递归函数参数还需要startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。 单步逻辑递归循环中如何截取子串在一个子循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。和组合问题一致。在单步过程中判断每次切割出的子串是不是回文字串。如果是那么进行下一步递归。 终止条件当i已经是最后一位则停止 实现 class Solution:def backtrack(self, s, start_idx, path, results):if start_idx len(s):results.append(path[:])returnfor i in range(start_idx, len(s)):## 右侧需要从start的下一位开始 遵循python切片左闭右开if s[start_idx: i1] s[start_idx: i1][::-1]:path.append(s[start_idx: i1])self.backtrack(s, i 1, path, results)path.pop()def partition(self, s: str) - List[List[str]]:results list()self.backtrack(s, 0, [], results)return results