算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇)

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


前言


提示:阳光好的时候,会感觉还可以活很久,甚至可以活出喜悦。 --余秀华

回溯是非常重要的算法思想之一,主要解决一些暴力枚举也搞不定的问题(这里埋个坑💣)例如组合、分割、子集、棋盘等等。从性能角度来看回溯算法的效率并不是很高,但是对于暴力也解决不了的问题,它往往很快可以出结果,效率低就可以理解了吧。接下来,就看看回溯的事情吧🤩

回溯的核心问题

递归+局部枚举+放下前任

接着看这个题目:77. 组合 - 力扣(LeetCode)

算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
当n = 4时,我们可以选择的有n有{1,2,3,4}这四种情况,所以我们从第一层到第二层的分支有四个,分别表示可取1,2,3,4.而且这里从左到右取数,取过的数,不在重复取。第一次取1,集合变为2,3,4.因为k= 2,我们也只能再取1个数就可以了,分别取2,3,4.得到的集合就是[1,2]、[1,3]、[1,4]。一次类推:

横向:

算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
每次从集合中选取元素,可选择的范围回逐步收缩,到了取4时就直接返为空了。

继续观察树结构,可以发现,图中每次访问到一个叶子节点(图中的标记处),我们就可以得到一个结果。虽然到最后时空的,但是不影响最终结果。这里相当于从根节点开始每次选择的内容(分支)达到叶子节点时,将其收起起来就是我们想要的结果。

你可以尝试画下n=5,k=3的结果:有没有感觉

算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
从图中我们发现元素个数n相当于树的宽度(横向),而每个结果的元素个数k相当于树的深度(纵向)。所以我们说回溯问题就是一纵一横而已。在分析我们回发现下面几个规律:

  • 我们每次选择都是从类似{1,2,3,4},{1,2,3,4}这个样的序列中一个一个选的,这就是为什么说是局部枚举,后面的枚举范围回越来越小。
  • 枚举时,我们就是简单的暴露测试而已,一个一个验证,能否满足要求,从上图可以看到,这就是N叉树的遍历过程,一次代码相似度很高。
  • 我们再看叶子过程,这部分是不是和(n = 4,k = 2)处理的结果一致,也就说是很明显的递归结构。

到此,我们还有一个问题待解决,就是回溯一般会有一个手动撤销的操作,为什么要这么做呢?

继续观察纵横图:
算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
我们可以看到,我们收集的每个结果不是针对叶子节点的,而是针对树枝的,比如最上层我们首先确定了1,下层我们如果选择了2,那么结果就是{1,2},如果选择了3,结果就是{1,3}.一次类推。现在时怎么确定得到第一个结果时{1,2}之后,得到第二个结果是{1,3}呢?

继续观察纵横图 ,可以看到,我们在得到{1,2}之后将2撤销,再继续使用3,就得到了{1,3},同理也可以得到{1,4},之后这一层就没有了,我们可以撤销1,继续从最上层取2继续进行。

这里对应的代码操作就是先将第一个结果放在临时列表的Path里面,得到第一个结果{1,2},之后就将path里面的内容放进结果列表resultList中,之后,将path里面的2撤销掉,继续寻找下一个结果{1,3},继续将path加入resultList中,然后再次撤销,继续寻找。

现在了解为什么要撤销,看图。这个过程,我们称它“放下前任,继续前进”,后面的回溯大都是这样的思路。

这几条就是回溯的基本规律,了解这一点,我们就可以看看代码是怎么回事了,到此我们看看完整的代码时怎样的:

 public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <=0 || n < k){
            return res;
        }Deque<Integer> path = new ArrayDeque<>();dfs(n,k,1,path,res);
        return res;
    }public void dfs(int n,int k,int startIndex,Deque<Integer> path,List<List<Integer>> res){
        // 递归终止条件,path 等于k(刚好完成一次
        if (path.size() == k){
            res.add((new ArrayList<>(path)));
            return;
        }
        // 针对每个节点,这里就是遍历搜索,也就是枚举
        for(int i = startIndex; i <= n; i++){
            // 向路径里添加一个数(分支里的取值
            path.addLast(i);
            // 搜索起点要加1,就是缩小范围,准备下一轮递归(这里不允许重复
            dfs(n,k,i + 1,path,res);
            // 递归之后要做同样的逆向操作,撤销掉
            path.removeLast();
        }
    }

上面代码还有一个问题需要解释:startIndex和i是怎么变化的,为什么要传递到下一层(+ 1)

我们来看看这里的递归循环:

   // 针对每个节点,这里就是遍历搜索,也就是枚举
        for(int i = startIndex; i <= n; i++){
            // 向路径里添加一个数(分支里的取值
            path.addLast(i);
            // 搜索起点要加1,就是缩小范围,准备下一轮递归(这里不允许重复
            dfs(n,k,i + 1,path,res);
            // 递归之后要做同样的逆向操作,撤销掉
            path.removeLast();
        }

这里的循环有什么作用呢?看看这里,其实来说是一个枚举,第一次n=4,可以选择1,2,3,4四种情况,所以就存在4个分支,for就需要执行4次:
算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
对于第二层来说,第一个数,选择1之后,身下的元素就只有2,3,4了。所以这时候for循环就执行3次,后面的只有2次和1次了。

撤销操作解释

如果你还是不清楚的话,这里就带图详细的走一遍,回溯也就是这个地方有点晕,拿下就是胜利✌。

   // 针对每个节点,这里就是遍历搜索,也就是枚举
        for(int i = startIndex; i <= n; i++){
            // 向路径里添加一个数(分支里的取值
            path.addLast(i);
            // 搜索起点要加1,就是缩小范围,准备下一轮递归(这里不允许重复
            dfs(n,k,i + 1,path,res);
            // 递归之后要做同样的逆向操作,撤销掉
            path.removeLast();
        }

为什么要remove呢?看下图,当第一层取1时,最底层的遍历从左到右执行,取2,取3,取4.而取3的时候,此时res里面存储的是{1,2},所以这里前提是需要撤销掉2(path.removeLast();)的作用。

这里我们拆解一下递归方法,将递归拆分成函数调用,输出第一条路径{1,2}的步骤如下:
算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
我们在递归说过一个特点:不到南墙不回头,回溯也是这个道理,我们看看这个过程。

算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
然后,怎么在次进行呢,这里就需要撤回一下了,但是如果将这里的remove代码去掉,就会是这个样子:
算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java
这里知道遍历完成,然会的就不做撤销,就会下一场进入for循环,也就是回变成{1,2,3}.

path是一个全局的引用的,各个递归的函数是公用的,所以这里处理完{1,2},之后,需要把2撤出去,将1保留,再让三进入,从而得到{1,3}.所以这里不许remove一下的。

同样处理完之后,后续的也是依次处理,需要撤销的,这里也就是不得不处理撤销的操作。


总结

提示:什么叫回溯;保留状态;撤销操作;回溯核心思想;回溯的入门


如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~

也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇),算法集训营,算法笔记,什么叫回溯,保留状态,撤销操作,Java文章来源地址https://www.toymoban.com/news/detail-741507.html

到了这里,关于算法通过村第十八关-回溯|青铜笔记|什么叫回溯(中篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法通过村第四关-栈黄金笔记|表达式问题

    提示:快乐的人没有过去,不快乐的人除了过去一无所有。 --理查德·弗兰纳根《深入北方的小路》 栈的进阶来了,还记得栈的使用场景吗?表达式和符号,这不就来了 参考题目介绍:227. 基本计算器 II - 力扣(LeetCode) 计算问题在栈的运用也是非常广泛的。在乘除优先于加

    2024年02月10日
    浏览(35)
  • 算法通过村第二关-链表黄金笔记|K个一组反转

    提示:没有人天生就喜欢一种气味而讨厌另一种气味。文明的暗示而已。 给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。 k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

    2024年02月14日
    浏览(43)
  • 算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现

    提示:我曾如此渴望命运的波澜,到最后才发现:人生最曼妙的风景,竟是内心的淡定从容。 我们层如此盼望世界的认可,到最后才知道:世界是自己,与他人毫无关系。 --杨绛 LRU 是非常经典的问题,而且在常年的算法中也是热门,但是他是存在技巧的,我们这就来一起看

    2024年02月09日
    浏览(37)
  • 算法通关村第十八关——排列问题

    LeetCode46.给定一个没有重复数字的序列,返回其所有可能的全排列。例如: 输入:[1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次,所以就不能使用startlndex了,为此可以使用一个used数组来标记已经选择的元

    2024年02月09日
    浏览(45)
  • 算法通关第十九关-青铜挑战理解动态规划

    大家好我是苏麟 , 今天聊聊动态规划 . 动态规划是最热门、最重要的算法思想之一,在面试中大量出现,而且题目整体都偏难一些对于大部人来说,最大的问题是不知道动态规划到底是怎么回事。很多人看教程等,都被里面的状态子问题、状态转移方程等等劝退了。 其实,所

    2024年02月03日
    浏览(40)
  • 算法通关村第十七关:青铜挑战-贪心其实很简单

    1. 难以解释的贪心算法 贪心学习法则:直接做题,不考虑贪不贪心 贪心(贪婪)算法 是指在问题尽心求解时,在每一步选择中都采取最好或者最优(最有利)的选择,从而希望能够导致结果最好或者最优的算法 贪心算法所得到的结果不一定是最优的结果,但是都是相对近似最

    2024年02月09日
    浏览(41)
  • 算法通关村第十六关:青铜挑战-滑动窗口其实很简单

    1. 滑动窗口基本思想 数组引入双指针的背景: 很多算法会大量移动数组中的元素,频繁移动元素会导致执行效率低下或者超时,使用两个变量能比较好的解决很多相关问题 数组双指针,之前介绍过 对撞型 和 快慢型 两种,滑动窗口思想就是快慢型的特例 滑动窗口 示例:

    2024年02月09日
    浏览(43)
  • 算法通关村第十五关:青铜-用4KB内存寻找重复元素

    位运算在查找元素中的妙用 题目要求: 给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。 思路分析 本题是非常典型的海量数据处理的问题,使用的是位运算结构 内存大小关系

    2024年02月10日
    浏览(37)
  • [Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素

    在 海量数据 中,此时普通的数组、链表、Hash、树等等结构有无效了 ,因为内存空间放不下了。而常规的递归、排序,回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须另外想办法。这类问题该如何下手呢?这里介绍三种非常典型的思路: 使用位存储 ,使用

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

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

    2024年02月13日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包