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