推广的网站,嘉兴网站建设方案咨询,wordpress仿魔客吧,设计网站大全扣西湖南岚鸿首选青铜挑战-回溯是怎么回事
回溯#xff0c;最重要的算法之一 主要解决一些暴力枚举也搞不定的问题#xff0c;例如组合、分割、子集、排列、棋盘等
从性能角度来看回溯算法的效率并不高#xff0c;但对于这些暴力都搞不定的算法能出结果就很好了#xff0c;效率低点没关系…青铜挑战-回溯是怎么回事
回溯最重要的算法之一 主要解决一些暴力枚举也搞不定的问题例如组合、分割、子集、排列、棋盘等
从性能角度来看回溯算法的效率并不高但对于这些暴力都搞不定的算法能出结果就很好了效率低点没关系
回溯可视为递归的拓展很多思想和解法都与递归密切相关对比递归来分析其特征会理解的更深刻
举例说明递归和回溯的区别 设想一个场景某猛男想脱单两种策略
递归策略先与意中人制造偶遇然后了解人家的情况然后约人家吃饭有好感之后尝试拉人家的手没有拒绝就表白回溯策略先统计周围所有单身女孩然后一个一个表白被拒绝就说”我喝醉了“然后就当啥也没有发生继续下一个
回溯最大的好处有非常明确的模板 所有的回溯都是一个大框架因此透彻理解回溯的框架是解决一切回溯问题的基础
回溯不是万能的解决的问题也是非常明确的例如组合、分割、子集、排列、棋盘等 不过这些问题具体处理时又有很多不同
回溯可视为递归的拓展代码结构特别像深度遍历N叉树 难点回溯在递归语句之后有个”撤销“的操作。 好比谈了个新女朋友来你家之前要将前任的东西赶紧藏起来。回溯也一样有些信息是前任的要处理掉才能重新开始。
回溯的模板如下
void backtracking(参数){if(终止条件){存放结果;return;}for(选择本层集合中元素(画成树就是树节点孩子的大小)){处理节点;backtracking(参数);回溯撤销处理结果}
}1. 从N叉树说起
二叉树的前序遍历
class TreeNode:def __init__(self, val):self.val valself.left Noneself.right Nonedef tree_dfs(root):if root is None:returnprint(root.val)tree_dfs(root.left)tree_dfs(root.right)N叉树的前序遍历
class TreeNode:def __init__(self, val):self.val valself.children []def tree_dfs(root):# 递归终止条件if root is None:return# 节点处理print(root.val)# 通过循环分别遍历N个子树for i in root.children:tree_dfs(i)回溯模板与N叉树的遍历模板非常像
2. 为什么有的问题暴力枚举也不行
什么问题暴力枚举也不行
举个例子
LeetCode77 组合 https://leetcode.cn/problems/combinations/ 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 n4, k2时双层暴力枚举
def violent_enumeration():res []for i in range(1, 5):for j in range(i 1, 5):res.append((i, j))return resif __name__ __main__:print(violent_enumeration()) # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]n10, k3时三层暴力枚举
def violent_enumeration():res []for i in range(1, 11):for j in range(i 1, 11):for k in range(j 1, 11):res.append((i, j, k))return resk未知时循环次数未知这时暴力枚举就失效了
这就是组合类型问题除此之外子集、排列、切割、棋盘等方面都有类似的问题我们需要找到更好的方式
3. 回溯递归局部枚举手动撤销放下前任
继续研究 LeetCode77 组合 https://leetcode.cn/problems/combinations/ 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 n4, k2时
n5, k3时
从图中我们可以发现元素个数n相当于树的宽度(横向)每个结果的元素个数k相当于树的深度(纵向) 此外还有一下规律
局部枚举每次都是从类似 [1,2,3,4] 这样的序列进行枚举越往后枚举范围越小递归再看n5,k3时图中红色大框部分执行过程与n4,k2处理过程一直时可以递归的子结构手动撤销观察图中可以看到取3得到[1,2,3]之后需要将3撤掉再继续取4得到[1,2,4] 对应的代码操作:将第一个结果放到 path中path[1]将第二个结果放到 path中path[1,2]将第三个结果放到 path中path[1,2,3]将结果输出撤销3, path[1,2]继续枚举将第三个结果放到 path中path[1,2,4]…
综上可以得到 回溯递归枚举手动撤销
这就是回溯的基本规律掌握之后就可写出完整的回溯代码了
回溯代码实现
import copyclass Solution:def combine(self, n: int, k: int) - List[List[int]]:def dfs(k, n, begin, path, res):# 递归终止条件是path的长度等于kif len(path) k:res.append(copy.deepcopy(path))return# 枚举针对一个节点遍历可能的搜索起点for i in range(begin, n1):# 像路径变量里添加一个数就是树枝的值path.append(i)# 搜索起点加1缩小范围为下一轮递归做准备因为不允许出现重复的元素dfs(k, n, i 1, path, res)# 手动撤销path.pop()res []if k 0 or n k:return respath []begin 1dfs(k, n, begin, path, res)return res4. 图解为什么有个撤销的操作
暂无理解了上一小节的 手动撤销 即可
5. 回溯热身-再论二叉树的路径问题
5.1 输出二叉树的所有路径
LeetCode 257 https://leetcode.cn/problems/binary-tree-paths/
思路分析
方法1深度优先搜索 深度优先搜索就是从根节点开始一直找到叶子结点这里可以先判断当前节点是不是叶子结点再决定是不是向下走如果是叶子结点我们就增加一条路径。这个之前学习这里不再赘述
方法2回溯 从回溯的角度分析得到第一条路径ABD之后怎么找到第二条路径ABE这里就是先将D撤销然后再继续递归就可以了
难点手动撤销
代码实现
方法1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]:def search_path(node, path):if not node:return path str(node.val)if not node.left and not node.right:paths.append(path)else:path -search_path(node.left, path)search_path(node.right, path)paths []if root:search_path(root, path)return paths
方法2回溯
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]:def search_path(node, path, paths):if node is None:returnpath.append(str(node.val))if node.left is None and node.right is None:paths.append(-.join(path))for i in [node.left, node.right]:search_path(i, path, paths)path.pop() # 返回上一层递归时要让当前路径恢复原样paths []path []if root:search_path(root, path, paths)return paths5.2 路径总和问题
LeetCode 113 路径总和 II https://leetcode.cn/problems/path-sum-ii/
思路分析
目标路径总和 targetSum22 根节点5需要左侧或右侧target_sum22-517继续看左子树node(4)需要node(4)左子树或右子树满足 target_sum17-413依次类推 … …
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
import copyclass Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]:def find(node, target_sum, path, paths):if node is None:returnpath.append(node.val)if node.left is None and node.right is None and node.val target_sum:paths.append(copy.deepcopy(path))target_sum - node.valfor i in [node.left, node.right]:find(i, target_sum, path, paths)path.pop()paths []path []if root:find(root, targetSum, path, paths)return paths
注不想用copy也可以用 path[:] 替代
