算法通关村第十八关:青铜挑战-回溯是怎么回事

这篇具有很好参考价值的文章主要介绍了算法通关村第十八关:青铜挑战-回溯是怎么回事。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

青铜挑战-回溯是怎么回事

回溯,最重要的算法之一
主要解决一些暴力枚举也搞不定的问题,例如组合、分割、子集、排列、棋盘等

从性能角度来看回溯算法的效率并不高,但对于这些暴力都搞不定的算法能出结果就很好了,效率低点没关系

回溯可视为递归的拓展,很多思想和解法都与递归密切相关,对比递归来分析其特征会理解的更深刻

举例说明递归和回溯的区别:
设想一个场景,某猛男想脱单,两种策略:

  1. 递归策略:先与意中人制造偶遇,然后了解人家的情况,然后约人家吃饭,有好感之后尝试拉人家的手,没有拒绝就表白
  2. 回溯策略:先统计周围所有单身女孩,然后一个一个表白,被拒绝就说”我喝醉了“,然后就当啥也没有发生,继续下一个

回溯最大的好处:有非常明确的模板
所有的回溯都是一个大框架,因此透彻理解回溯的框架是解决一切回溯问题的基础

回溯不是万能的,解决的问题也是非常明确的,例如组合、分割、子集、排列、棋盘等
不过这些问题具体处理时又有很多不同

回溯可视为递归的拓展,代码结构特别像深度遍历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时
算法通关村第十八关:青铜挑战-回溯是怎么回事,python,开发语言

n=5, k=3时
算法通关村第十八关:青铜挑战-回溯是怎么回事,python,开发语言

从图中我们可以发现,元素个数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撤销,然后再继续递归就可以了

难点,手动撤销

代码实现

方法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

算法通关村第十八关:青铜挑战-回溯是怎么回事,python,开发语言

  • 根节点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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村|青铜挑战----链表

    前言:数据结构的基础:创建+增删改查 学习目标:单链表的创建+增删改查,双链表的创建+增删改查 数据域+指针域 数据域:当前节点的元素值 指针域:当前节点保存的下一个节点的元素的地址,其中最后一个元素的指针域指向null 标准的面向对象的节点的定义: LeetCode中节

    2024年02月15日
    浏览(33)
  • [Go版]算法通关村第一关青铜——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月13日
    浏览(37)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(38)
  • 算法通关村第一关———链表青铜挑战笔记

    通过类来构建节点,用next指针将节点连起来。 会有插入位置的范围问题,不能超出链表范围 会有删除位置的范围问题 构造双向链表 插入和删除都有三种情况,头中尾  

    2024年02月15日
    浏览(42)
  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(42)
  • 算法通关村第一关 | 链表青铜挑战笔记

    一、 什么是链表? 链表是一种比较简单、很常见的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 二、链表的特点 链表是一种比较简单、很常见的数据结构,是线性表(List)的一种,是一种物理存

    2024年02月14日
    浏览(36)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(41)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(40)
  • 算法通关村第一关——链表青铜挑战笔记(单链表)

    在LeeCode中一般这样创建链表 要注意创建一个变量来遍历,不要把head丢掉了 count position - 1可以方便操作,还能防止下标越界(cur为null)

    2024年02月15日
    浏览(37)
  • 【无标题】算法通关村第一关——链表青铜挑战笔记

    算法通关村第一关——链表青铜挑战笔记 C语言是如何构造出链表的 0.定义节点结构 1.建立头指针 2.建立temp指针 3.将节点连起来 3.1 把p指向temp 3.2 设立循环节点a+temp指向a+temp变为a

    2024年02月15日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包