4. 递归 —— Ficow 陪你学算法和数据结构

| 算法/数据结构

 

内容概览

  • 前言
  • 递归
  • 思维要点
  • 实战题目
  • 总结

 

前言

 

3. 树、二叉树、二叉搜索树 —— Ficow 陪你学算法和数据结构 中,Ficow 和您分享了自己的学习笔记。本文将深入讲解常用的递归算法,而且文末还附有覃超老师推荐的练习题目。

提到递归,很多朋友都会皱起眉头。毕竟,递归比较抽象,用递归来解决问题更加抽象。
然而,很多企业在面试的时候都会有递归相关的题目。比如,树的面试题解法,一般都是基于递归的。

既然已经知道了这个龙门,那咱们就使劲练习、不断提高,逼一下自己就跳过去了~

 

在开始阅读后文之前,我强烈建议您学习覃超老师在 极客时间 上开设的 算法训练营体验课,我已经亲身学习过并推荐给了朋友、同事们。

该课程的内容主要是以视频为主,质量非常高,而且短小精悍。主要涉及:

  • 复杂度分析
  • 数组、链表、跳表
  • 树、二叉树、二叉搜索树
  • 递归(代码模板非常给力)

截止 Ficow 创作此文当日,该课程售价还是 9.9 元,性价比还是挺高的。极客时间的新用户还可以免费领取,有效期是一周。赶快行动吧~

因为本文属于 Ficow 陪你入门 系列文章,所以 Ficow 也会记录自己的学习历程,并和您分享我自己的学习笔记。欢迎您留言和我交流,大家共同进步!

 

递归(Recursion)

 

递归其实本质上就是利用函数体来进行循环。在更底层的汇编语言实现中,递归其实就是程序在执行过程中跳回(JMP)到之前执行过的某个指令,如此反复跳回就形成了我们看到的递归调用。

生动有趣的故事:从前有座山,山里有座庙,庙里有个和尚在讲故事,讲什么呢?从前有座山,山里 ……

更有意思的例子:《盗梦空间》中的一层套一层的梦境,逐层深入,时间变得更慢,最终将某种状态从梦境中带回现实世界。

 

最简单的阶乘递归示例:

最终产生的递归栈:

实用的递归模板:

每次写递归代码的时候都先打好这个模板,然后再开始填充逻辑:
  • 递归终止条件
  • 处理当前递归层级的逻辑
  • 进入到递归的下一层级
  • 如果有必要的话,清理当前递归层级的状态(比如:调整全局变量的值)

 

思维要点

 

下面就展开来讲解这几个要点:

  • 在写递归代码时,很多人会陷入人肉递归的情况(人脑模拟计算机去运行代码,很快就会晕头转向),这个其实是我们必须要警惕的思维误区。
  • 能写成递归的代码,一定存在重复的子问题,找到了子问题就可以写出递归代码。而且,面试题的正确答案一般都比较简短,最多也就几十行。
  • 思考当 n 为 1 时的情况,当 n 为 2 时的情况,当 n 为 3 时的情况,然后就不要再这样简单地重复下去。这时候,要找出重复的规律,而且要保证没有漏算的情况,保证结果是互斥且穷尽的(MECE: Mutually Exclusive, Collectively Exhaustive)。最后,找出的重复规律应当满足这个条件:当 n 为 n 时以及 n 为 n + 1 时也符合这个规律。

 

实战题目

 

爬楼梯:https://leetcode-cn.com/problems/climbing-stairs/
生成括号:https://leetcode-cn.com/problems/generate-parentheses/
二叉树的最大深度:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
二叉树的最小深度:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
验证二叉搜索树:https://leetcode-cn.com/problems/validate-binary-search-tree/
翻转二叉树:https://leetcode-cn.com/problems/invert-binary-tree/
二叉树的序列化和反序列化:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
二叉树的最近公共祖先:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
从前序与中序遍历序列构造二叉树:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
组合:https://leetcode-cn.com/problems/combinations/
全排列:https://leetcode-cn.com/problems/permutations/
全排列 II:https://leetcode-cn.com/problems/permutations-ii/

练题的操作步骤:

  • 写出自己的思路,多种解法 都写下来,最后再去比较并找出最好的解法;
  • 用代码实现自己的解法,然后用题目提供的测试数据进行测试(多尝试几组数据,比如特殊情况);
  • 测试通过后即可提交代码,然后查看该代码的审题结果,主要看耗时以及时间复杂度
  • 寻求反馈:Code Review(尽量这样做)、查看题解(跳过糟糕的解法),理解别人的思路还有代码的写法,然后自己实践几遍;
  • 复制题解的网址,删除域名中的 -cn,然后打开 LeetCode 国际站,在 题目的 Discuss 页面选择 Most Votes,消化吸收各种优秀的解法,同时提升英语水平。
  • 把这个题目刷 5遍5遍5遍!!!千万不要只刷一遍!!!

 

总结

 

互联网名企的笔试面试都会考察类似的题目,所以我们一定要做足充分的准备。在准备的过程中,要尽可能做到以下几点:

  • 只是知道概念是没什么用的,一定要把题目练习到熟练并且专业的程度。如果不熟练,在笔试面试过程中会更加紧张,最后就很容易失误。
  • 刻意练习,持续地刻意练习。深耕一个领域,需要有节奏有规划的刻意练习(一万小时定律)。
  • 要锻炼分析、解决问题的能力。学知识、刷算法题,本质上是为了提升自己解决问题的能力。在这个过程中,我们会不断地提升抽象问题、分析问题的能力。
  • 三人行必有我师,要善于向他人请教(比如:LeetCode 题解、去极客时间参加培训课)。

到本文创作完成之时,Ficow 已经把这个视频刷了 3 遍。接下来,Ficow 会去刻意练习这些题目,我想会是 5 遍。虽然有些题目在大学时期就已经做过,但是当时并没有按照覃超老师推荐的方法去练习,而且也远远没有达到熟练甚至专业的水平。

知道自己的不足是一件好事,至少自己还有比较清晰的努力方向!朋友,如果你也看到了自己的不足,那就赶快行动起来吧!!!💪💪💪

您有什么想和 Ficow 交流的,大可不必拘束,尽管留言吧~ 😄

 

参考内容:

极客时间
算法训练营体验课
LeetCode
LeetCode - 中文站

 

觉得不错?点个赞呗~

本文链接:4. 递归 —— Ficow 陪你学算法和数据结构

转载声明:本站文章如无特别说明,皆为原创。转载请注明:Ficow Shen's Blog

评论区(期待你的留言)