写了三百篇算法题解,关于如何刷题有些话我想对你说

共 6692字,需浏览 14分钟

 ·

2021-08-12 21:38

这篇文章憋了我挺久的,感觉都快憋出内伤,一次次的打开 Typora 写几十个字,一次次的修改删除最后关闭 Typora,如此反复。

为什么会如此纠结?

或许是太狂妄了,我真的想让那些看了这篇文章的人都能从中受益,无论是算法小白还是高手,导致文章的立意拔的太高,高到我驾驭不住,远远超出了我的实际水平,于是一次次的开始写,一次次的废除。

直到最近才想明白我应该写一篇什么样的文章,这篇文章的目标群体不是那些立志于参加 ACM 的大佬,也不是早早的就是刷了好几百道 LeetCode 的高手,而是那些徘徊在要不要刷题、如何刷题的算法初学者们,我问自己,当年还是小白,为了进大厂,在珠江新城艰难挤上地铁后打开手机日复一日不断的重复看算法面试视频时, 是否想要看这样的文章来确定方向,我的答案是会,收藏然后狠狠地点个赞仔细的看。

开头稍微啰嗦了几句,下面开始进入正题。


不知道你们一开始刷算法题的时候是否有过如下的困惑。

  • 1、题目很长,半天看不明白是什么意思
  • 2、明明看懂了题目,但写出的代码却提交不通过
  • 3、代码写到一半发现不知道怎么往下写了
  • 4、别人的题解一看就懂,但自己想破脑袋都想不出要用这种方法
  • 5、即使刷了两百多道题目,面试的时候一紧张还是会头脑空白发慌

你问我为啥知道这些?因为我都经历过。

我们都是从应试教育中厮杀出来的,所以对刷题应该是挺熟悉的,缺的只是方法,人人都可以是小镇做题家。

方法是什么呢?

可以归纳为两个,一个是战略,一个是战术,犹如行军打仗,两手都要抓。

在战略上,我们需要做到的是藐视算法题。

在战术上,我们需要做到的是重视刷算法题。

一、战略上藐视算法题

在战略上藐视算法题的目的是为了在心理层面上克服恐惧,事实上,不仅仅是算法题,诸如学习计算机基础、计算机网络、编译原理等程序员必备的知识时,有这个心态可以学起来事半功倍。

我亲身经历过这样的改变。

作为一个转行程序员,在转行学习编程的那段日子,没有人告诉我说要去学数据结构,也没有人告诉我说要去刷 LeetCode,都是靠自己一个人摸索,绝大部分的时间都花在具体项目上,误认为自己和那些已经工作的程序员的区别在于有没有做过项目。

这就是科班出身和非科班出身的学生最大的区别,科班出身的学生知道去学什么,知道大学期间安排的每一门课程是干什么的,知道要先去做哪些小项目来循序渐进的编码练习,知道知识点在工作中能起到什么样的具体作用,非科班出身的程序员感觉计算机相关的知识点简直是一团乱麻。

这种情况导致我去找工作参加面试的时候,很多基础面都通过不了,最后侥幸进入一家要求不太高的创业公司,薪资不高,为了进大厂必须完善算法和计算机的知识。

因为未知,所以恐惧,恐惧导致盲目的崇拜,我认为那些科班出身的程序员太牛逼了,居然可以掌握那么多繁杂的计算机知识;那些写源码分析的程序员都是大神;那些写算法题解的程序员都是高手。

恐惧把小的问题放大,比如学到单调栈、双向链表、记忆化的内容,一看到题目要用到这些概念便觉得代码很难写,索性那些内容就不看,所以学了大半年还在原地踏步,还在原来的公司拿着微薄的工资做着 CURD。

几个月后,创业公司不行了,受迫于重新找工作的压力,只好咬着牙再去啃,再去刷题。

而当我开始写题解、做动画的时候,我就发现算法题也就那样,缺的只是时间去不断的重复练习。

单调栈无非就是在栈的概念基础上增加了排序,记忆化也就是增加一个数组用于存储,动态规划在面试和实际工作中用到的只需要掌握百分之五就行。

抱着编程技术也就那样的心态,学习了爬虫以及 Vue。

“自大”的认为爬虫能有多难,基本步骤无非以下几步:

  • 1、找到需要爬取内容的网页URL
  • 2、打开该网页的检查页面
  • 3、在 HTML 代码中找到你要提取的数据
  • 4、写 Python 代码进行网页请求、解析
  • 5、存储数据

下载安装 Pycharm,安装 Scrapy,根据步骤输入 URL 和数据格式,在完全不懂分布式、ip代理、js加密、模拟登陆、MongoDB的前提下,顺利拿到了自己想要的数据。

无论是分布式还是ip代理,爬虫的每个知识点深挖下去都大有文章,我所学习到的爬虫知识只是冰山一角,但这并不妨碍我们可以从战略上去蔑视编程,编程的很多内容没有那么高不可攀,缺的只是时间去学习,时间恰恰是我们可以去支配的。

二、战术上重视刷题

战术,分为道与术。

回顾一下我们以前学数学的过程,会发现,数学题有千千万,最后在脑海中记住的并非是这道题的具体写法,而是解这道题的思路。

算法刷题同样如此,很难做到让你把做过的题目代码都背下来,然后在面试的时候一五一十的写出来,但是你可能知道这道题的思路,用什么样的数据结构和什么样的算法思想,知道可以用这样那样的方法做出来,差的就是细节。

也就是说,刷题和应试教育中的学习是一样的,都需要先经过大量刻意的重复练习,见多识广,才能在面试时做到游刃有余。

说白了,就是要多刷才行。

这里的多刷题,不是指多瞎刷题,而是有方法的去刷,有目的的练习,而一个合理的练习方式,比练习的时间长短,更为重要。

如何做到有目的的进行练习,大概可以分为以下五个步骤:

1、找到具有定义明确的具体特定目标 2、具有专注练习的状态 3、找到导师模仿练习 4、走出舒适圈,突破自我 5、强化前行的理由

1、找到具有定义明确的具体特定目标

目标必须是十分具体的,可以逐个解决,把目标进行分类并制定一个可实施的计划。

目标是什么?

通过算法面试不是目标,而是一个结果,我们的目标是怎么样合理的刷完算法面试需要的那些题目,推荐的做法是按照标签来刷,难度上循序渐进,即把多种同类型的题先放在一起来做,比如一个时间段,只刷链表题,待刷得差不多的时候,接下来再刷二叉树的题。

由于不断的刷同个类型的题目,相当于在不断的重复练习,可以不断地加深自己对某个数据结构的理解,刷到后面可能发现这类题目都是有固定的套路,甚至一部分代码都是一模一样的。

这种刷法不仅在大方向上找到具有定义明确的具体特定目标,即合理的刷完算法面试需要的那些题目,与此同时,当刷同类型的题目出现困惑时,也能有目的性的去搜索相关的特定资料。

2、具有专注练习的状态

不建议在一开始刷题就去搜索一些模板来背,然后在解题的时候套模板,这样的刷题只是重复而不是练习,收获的只是经历而不是经验,背的再熟练,平时写的多块,没有自己的一个完整思考过程,在面试时很容易卡壳。

在刷题的过程中,争取做到三件事:

1、当写出 AC 的代码时,思考为什么自己可以做到

2、当写出 AC 的代码时,思考能不能优化一些

3、是否用到了题目给出的所有条件

很多题目都是由相似的题目改编而来的,增删一些条件题目的难度就会发生巨大的提升,基于这三个思考,每道题目都去多想一步,一步一步再一步,不同维度不同姿势都尝试一下,不要满足于一种解法,各种解法都写一写,争取做到 beat 100%,把每个题目都做干净,彻底攻克一道题。

3、找到导师模仿练习

搜索任何一道算法题,在网上都能发现不少文章,不过很多文章都是只提供解题代码或者加上一些简单的文字说明,为什么要这么写以及是怎么样想到这些方法的很少有文章会涉及到,这些人是高手,却不是导师。

高手和导师最大的区别在于,很多高手未必可以总结出自己的方法论,他们真的很牛逼但核心内容却只可意会不可言传,而导师一定有一套可以复制的方法论,他或许不一定是最牛逼的,但却是最适合模仿学习的。

目前 LeetCode 的题解区有不少大神写了不少细致的题解,找几个你看的顺眼的,模仿他们的思路去思考问题。

然后悄咪咪的吹一下自己,我利用动画的形式讲解算法,写了几百篇文章了,期间有不少人也在模仿我的风格去写作,取得了不错的效果,我最近把精力花在自己的个人网站 AlgoMooc 上,立志于更加细致的讲解 LeetCode,如果你找不到合适的导师,不妨访问 https://www.algomooc.com 来看看我的文章,我争取每道题目都录制视频,用五分钟讲清楚。

4、走出舒适圈,突破自我

当我们跌跌撞撞的刷了一些题目时,实际上,刷题已经变成了我们的舒适圈,在这个圈子中,你已经可以熟练的掌握了一些知识,如果我们想让练习取得成绩,我们得逼着自己走出舒适圈,最好的方法是自己去写题解,写一篇新手也能看懂的题解。

也就是熟知的费曼学习法

什么是费曼学习法呢?

简单来说就是以教促学,每当你认为学会或者掌握一个知识后,去给别人讲明白,通过这种方式对自己做一个检验,突破自我。

李笑来曾经分享过一个观点,他说教育主要分为 3 个环节——

  • 1、 教:我们最常做的读书、学习、听课等

  • 2、 练:就是练习,大量练习,重复练习

  • 3、 教练:在练习过程中遇到问题,教练帮忙指出来,然后继续练。

1、2 不断循环,直到把知识、技能练熟,能用到实践中,帮自己做成一些事情,创造价值。

以此作为参考,刷题也是可以分为 3 个环节---

  • 1、学:阅读别人的提交
  • 2、练:就是练习,模仿别人的思路来练习
  • 3、教:就是教练,通过写题解的形式给别人讲明白一道题目

1、2 两点属于被动学习,吸收效率在 10% 至 30% 之间,而 3 属于主动学习,也就是费曼学习,吸收效率高达 90% 。

也就是说,我们在刷题的过程中,为了提高学习效率,可以主动的去写技术博客分享,注意是写技术博客而非技术笔记,笔记是给自己看的,博客是给别人看的,在这个过程中,表面上你是在教会别人,事实上你通过教会别人的方式来逼自己查缺补漏,你可能以为你懂了,结果发现无法表达出来,事实上还是没有理解透彻;你以为你讲明白了,别人一问,发现还是有遗漏点。

5、强化前行的理由

当初你觉得进行刷题提升自己的时候,什么是你的动力?

这个问题最好在一开始的时候就想清楚,并记录下来。

在《思维的囚徒》一书中,提及到一个原则,叫:自由地选择你的态度 —— 人无论在什么情况下,都可以自由选择自己的态度。事实上,任何一件事情,我们都能找到它的意义,它能帮助自己变得更好的角度。

刷题这个过程必然是有难度的,会给自己很大的压力,所以一开始先把你认为刷题后能带来的积极结果写下来,越多越好,不管现实与否,每当你想要放弃的时候,多想想这些积极的结果,想想熬过这个痛苦的过程能提升多大的改变。

是从宏观角度来思考刷题,那么则是在微观的角度来看待每一道题目。

在具体做题的时候,可以采用以下三个步骤来进行。

  • 1、看懂题目

  • 2、分析解法

  • 3、代码实现

1、看懂题目

首先就是明确题目要我们解决的是什么问题?提供了哪些参考示例?是否提供了需要使用的数据结构和算法?时间复杂度或者空间复杂度有没有要求?提示的范围有没有比较特别的数?边界情况是否需要特殊处理?

怎么样去看懂题目呢?

给你个公式步骤进行参考,即 四步分析法 !

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

结合一道具体的算法题来说明整个过程,算法题来源于剑指 offer 上的例题:矩阵中的路径。

1、模拟

首先看一下矩阵的初始状态

我们需要在这个矩阵中寻找目标字符串 bfce,第一步要做的就是先匹配上目标字符串的第一个元素 b,我们从矩阵的第一行第一列的元素开始匹配,找到了 a 。

目标字符串为 bfce,此时查找第一个元素为 a ,与目标字符串的第一个元素 b 不相同,需要在四个方向搜索,看看能不能找到符合要求的元素,我们按照上左下右的顺序进行遍历寻找。

  • 上:越界了
  • 左:越界了
  • 下:是 s ,与目标元素 b 不相同
  • 右:是 b,符合要求,依葫芦画瓢找第二个元素
  • 上:越界了
  • 左:是 a,与目标元素 f 不相同
  • 下:是 f,与目标元素 f 相同,符合要求,依葫芦画瓢找第三个元素
  • 上:根据题目要求不需要考虑
  • 左:是 s,与目标元素 c 不相同
  • 下:是 d,与目标元素 c 不相同
  • 右:是 c,与目标元素 c 相同,符合要求,依葫芦画瓢找第四个元素
  • 上:是 c,与目标元素 e 不相同
  • 左:根据题目要求不需要考虑
  • 下:是 e,与目标元素 e 相同,符合要求,寻找结束,匹配成功,返回 true

2、规律

  • 1、在搜索过程中,如果当前元素与目标元素不匹配,则回退到之前的节点再搜索
  • 2、在搜索过程中,如果当前元素与目标元素相匹配,则按照上左下右的方向进行再次搜索匹配剩下的元素
  • 3、在搜索过程中,搜索当前元素上左下右方向的元素时,会出现重复访问之前元素的情况,比如搜索匹配成功的第三个元素 c 的四个方向时,会重复访问一下 f

为了保证不重复访问节点,可以将这条路径上已经访问过的节点,修改为不在 word 当中的一个字符,保证以后再次访问时不会重复访问,这里我们将其修改为特殊字符  # 。

修改完后会出现一种情况,当前的节点元素与目标元素相匹配,但是在它的四个方向的节点中都找不到可以匹配到目标下一元素的节点。

比如此时当前元素 c 与目标元素 c 相匹配,但是目标下一元素为 x,而在当前元素的四个方向上都找不到 x ,需要把这个点回退,根据之前的操作,当前的节点被修改为了 #,所以为了能够回退成功,再回退操作时需要重新将 # 修改回原来的元素。

3、匹配

本题提供了一个矩阵,矩阵是一个二维数组,需要我们在二维数组中进行搜索,为了能够覆盖所有的情况,必然要使用两个嵌套的循环

在搜索过程中,当遇到匹配成功的元素,搜索其下一元素的操作与当前的操作一致,即可以使用递归

  • 递归参数:当前元素在矩阵 board 中的行列索引 i 和 j ,当前目标字符在word 中的索引 k

  • 终止条件

    • 返回 false

      (1) 行或列索引越界

      (2) 当前矩阵元素与目标字符不同

      (3) 当前矩阵元素已访问过

    • 返回 true: k = len(word) - 1 ,即字符串 word 已全部匹配。

  • 递推工作

    • 标记当前矩阵元素:将 board[ i ] [ j ] 修改为特殊字符 # ,代表此元素已访问过,防止之后搜索时重复访问。
    • 搜索下一节点:朝当前元素的 上、左、下、右 四个方向开启下层递归。
    • 回退时还原当前矩阵元素:将 board[ i ] [ j ] 元素还原至初始值,即 word[k] 。
  • 返回值: 返回布尔量 res ,代表是否搜索到目标字符串。

4、边界

  • 1、行越界
  • 2、列越界
  • 3、矩阵元素已访问过

2、分析解法

在看懂题目的前提下,分析解法就轻松多了, 在脑海中我们已经大概知道了题目想要考察的方向,接下来我们需要思考的是题目的逻辑是怎么样的,不需要考虑代码层面。

需要注意的是,在第一遍或者第二遍解题时,不要过分追求所谓奇淫技巧的解法,很多同学错误的认为了奇淫技巧等于水平高超,我之前也出现过这个误解,很多 LeetCode 上的数学题都能一行或两行代码就 AC,每次自己写大半天发现答案竟然如此简单很是受挫。

后来发现,这些奇淫技巧并不能提高自己的水平,除了发在评论区能引来别人一句卧槽的惊讶,从而带来一点内心虚荣心的满足以外,其余的用处不大。

当然,等你刷个两三百到题目再回过头来重新思考,你会发现那些奇淫技巧的方法是如此的美妙。

3、代码实现

看懂了题目,有了思路,其实这道题的 90% 你已经解决了,把它实现出来按理来说就是自然而然的事儿了。

有时,将一个思路转换成算法是很容易且自然的;但有时,有些思路转换成代码,是很有难度的事情,这就是你写代码的能力问题,其实就是练少了。

刷题说到底还是需要题海战术

总结

呼,总是写完了。

希望今天的这六千字的经验分享能带给你一些思考:)

浏览 31
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报