写在Leetcode1000题之后

date

Feb 6, 2023

slug

after-leetcode1000

status

Published

我与编程

忘记写下第一行代码是什么时候了，应该是大一的C语言程序设计实验课上吧。不同于很多人，初学编程并没有给我带来很多惊喜，反倒是让我对编程犯怵。因此后来在科协实验室选择方向的时候毫不犹豫的选择了硬件，虽然之后断断续续的写过一些单片机程序，但我对编程实在算不上入门，还不如电路板画的好。

现在很多人在谈到职业发展、职业规划的时候喜欢讲兴趣，喜欢说要听从你的内心、要追随你的兴趣。但于我个人而言，编程实在算不上兴趣，写代码很大一部分原因并不是因为兴趣，而是责任，在一项任务中我扮演了写代码的角色，我就要把代码写好，仅此而已。

而事实上，其实我根本不知道自己的兴趣是什么，如果非要说个兴趣，那我对知识本身，以及在学习知识的这个过程中探索世界是很享受的。但这个东西和编程并没有必然的关系，不管程序员也好，职业股民也罢，都可以有这个学习知识的过程。也大概因此，我没有成为一名专业的程序员，以至于在临近毕业之际依旧没有找到让我很满意的工作。

我与LeetCode

可能是时代变了，也可能是我所处的环境变了，2020年研究生入学之后，总是不自觉的听到师兄谈论找工作的事情，也无意间知道了找工作要刷Leetcode。在我研一结束的那个暑假，写完论文之后，大概是2021年8月中旬吧，我终于开始了刷题之路。到2022年九月份秋招之际，大概写了1100题目。2022年底Leetcode官方给出年终回顾是：一整年写题天数为262天（9月份之后秋招受挫基本没写题了……），写了1011道题目。

看起来像是2021年那半年没有写题，怎么从21年9月到22年底写了1100多题，22年一整年还是写了1000来题？但实际上21年9月份之后的那几个月才是我写题最认真的时候，22年不过是在熟练之前学的一些方法技巧。

从提交次数就能看出我是勤奋型选手，在写算法题这件事上我和天赋完全不搭边，作为一个苦逼的勤奋型选手我想分享两个关于学习的方法论。

首先我认为学习要像烧开水一样一鼓作气，尤其是在刚接触某个新东西时。先看一个拙劣但形象的比喻，想象一下你从水井里面抽了一大壶水，在未来的某一天你随时可能要喝水，当然在喝水之前你需要烧开它。因此你可以先一次性花30分钟把水烧开，然后在之后某天需要喝水的时候再稍微加热一两分钟；你也可以每天坚持烧5分钟，尽管烧不开，但当你需要喝水的时候，可以以自我感动式的方式硬着头皮喝下去，毕竟你坚持了这么多天，水里的细菌会给你面子的。关于烧这壶水我相信每一个理智的人会有正确的判断。把需要学习的新东西看作是刚从井里抽出来需要烧开的一壶水，所学的新东西像水一样，在日后某天会用到，你可以一次性花三五个月把新东西彻底学会，然后之后用到的时候再稍加复习，也可以每天学一点，但代价就是一年之后依旧不会，反而会由初期的自我感动慢慢转为自我放弃。

其次我认为成体系的知识大都不是线性的，因此学习是一个不断重复的抗遗忘的过程。不是线性的该如何理解呢？如果用数据结构的语言来描述，所学的知识大都是呈一张有向有环图，而不是线性的链表。因此在学习的时候，不要想着先把一个知识点 A 彻底学会，然后再看 BCD，任何试图遍历一遍知识的链表就想掌握它都是痴心妄想。而正确的方式是在这张图上来回的遍历，来主动的把知识点串联起来，我相信每一次从不同的路径遍历到某个节点时都会有不同的收获。不断重复的抗遗忘的过程就很好理解了，首先遗忘是大脑的固有机制，况且我不是天赋型选手，因此自然需要不断重复来抵抗遗忘；其次学习是一个过程，没有终点，也因此知识可以常看常新。

在上述方法论的指导下，我用了3个多月每天大概两小时的时间来熟练各种数据结构和算法，熟练的方式主要是写题，当然我也会经常站在巨人的肩膀上看别人的一些讲解。在初窥了Leetcode上各种题型的全貌之后，便是不断的重复，不断的查漏补缺，在这个过程中，又不断的对各种题型有了新的感悟。

对于编程本身我并没有太多的兴趣，在学习数据结构与算法或者说做Leetcode题的过程中，也经常被一些算法和难题打击，但我终究还是上道了。我想这可以归因于以下一些因素。

一方面思考的过程及解题的快感我是很享受的，对我而言在Leetcode上写题不能算编程，代码只是我写题的一种工具，这与在草稿纸上写数学题并没什么区别。我想我所享受的这种解题的快感与王小波所说的“大便通畅似的快感“应该是一样的；

注：王小波在《》中曾写到：解几何题和编程序都是对自己智力的考验，通过了考验 (解对了一道题目或者编对一段程序)，有种大便通畅似的快感。

另一方面我很享受Leetcode上这种确定性的即时的反馈，提交一道题之后，要么通过，要么不通过，而不通过不外乎是语法问题、思路错误、边界考虑不周到、复杂度不满足这几种，干干脆脆的，我可太喜欢这种即时的确定性反馈了，以至于经常幻想着人与人打交道要是能这么简单就好了；

再一方面大概是潜藏心底的私欲，周围的环境让彼时的我认为写好算法题就能找到好工作，而一份好工作就意味着丰厚的薪水，试问谁对钱不感兴趣呢。当然，关于写题 = 找好工作的误区就又是另外的话题了，也许日后有时间我会再写点东西。

刷题心得

在谈完这些高屋建瓴的东西之后，我想沉下来分享一些对具体题目的看法。

首先是一些常用的数据结构：

基础的栈和队列。栈由于其先入后出的特性，有不少专门考察或者利用该特性的题目；队列则在BFS中用的比较多，例如，在二叉树层次遍历中便经常用到，需要注意有时在元素出队时需要记住当前队列的大小。

单调栈。单调栈通常用来寻找前一个（或者或一个）较大（或者较小）元素，最经典的题目当属接雨水了，理清楚了思路之后自然懂了时间复杂度为O(n)了。

堆 / 优先队列。初级使用的化只需要会自定义排序规则即可，具体应用如归并排序、Dijkstra等算法。进阶的化可以掌握堆这种数据结构是如何设计的，以及如何实现堆排序的。

链表。翻转链表、找倒数第n个节点、循环链表。所用算法无非是快慢指针、链表找环。

二叉树。基础的几种遍历方式一定要掌握，此外注意构建树、判断子树、树上信息的传递这几类类题型，然后遇到平衡二叉树的题目时注意其特性。

图。掌握图的表示以及拓扑排序、BFS、DFS、Dijkstra 这四种算法应该没问题了。

并查集。理解并查集的思想，然后了解几种优化方式后就把模板背下来吧。拿岛屿问题练练手。

其次是常用的一些算法：

BFS、DFS、Dijkstra。走迷宫一类的题目多练。

二分法。注意边界条件，除了普通的题目之外，注意利用二分法在答案集上搜索的题目。

拓扑排序。最不像排序的排序算法了，因为这是按照元素的先后拓扑关系来排序，而不是按照元素的大小属性。

滑动窗口。掌握滑动窗口思想之后，背模板就好了。

排序。重点掌握快速排序、堆排序、归并排序、桶排序这几种，其他排序算法了解即可。还有时间复杂度空间复杂度要回分析，尤其是快排。

前缀和与差分。更多是作为技巧来优化时间复杂度的。

动态规划。最常考的线性dp（股票买卖类题目）、双序列dp（编辑距离类题目）、背包问题。其他的dp（如树上dp）难度太大了建议放弃。

记忆化搜索。掌握了 DFS 和 DP之后就会发现这是一种很自然的解法。

最后是一些小众的数据结构与算法：

前缀树。学会构建一颗前缀树，且掌握前缀树上的DFS 与BFS。

树状数组。通常用来解决区间值会修改的区间问题，掌握之后就把模板背下来吧。

滚动哈希。手写滚动哈希来匹配字符串。

单调队列。其实不算小众，放这里仅仅是因为不太好理解，且题目少见。

快速幂。矩阵的快速幂可以用来优化爬楼梯这类题目，达到O(logn)的时间复杂度。

欧拉筛。用来统计素数的，注意从埃式筛到欧拉筛的优化。

在写题过程中，我也有不断的整理笔记，如

Data Structure & Algorithm 笔记，以及为了在短期内应付面试的

算法速通。

Leetcode于我

我知道不少人会觉得我这种写题过程太过于功利了，直接用最粗暴的学习方式来践踏算法这么优美的东西，将完全感受不到算法的美感。是的，之前我也思考过写题过程中除了学习新东西的喜悦与提交成功的快感之外还给我带来了什么。不过我慢慢的找到了答案，1000题之后，代码的调试能力也有了质的飞跃，我看一些技术文档能很快理解了，编程也感觉上了道。最主要的，我对编程没有了恐惧，我相信没有我学不会的技术。

Leetcode算法题在平时的工作中能用得到吗？这几乎是一个日经问题了，不管是q群还是技术论坛经常能看到有人讨论这个。我的答案是 As you will。虽然我还没有参见工作，但在最近上的一门网课中我体会到了，课程的作业是从0实现一个深度学习框架，在实现自动微分机制的时候，我很自然的想到了反向传播不过是在计算图上按照逆向拓扑排序的顺序来分别计算各个节点的梯度进而生成扩展计算图，领悟了这一点，写起代码来真是得心应手。然后在设计多维数组的数据结构的时候，需要用数组的shape来计算 strides，在草稿纸上稍微动了动手指，我又发现了这不过是后缀积的应用罢了。

最后借用王小波的话来结束这篇文章：

编程也好，解几何题也罢，一开始时，你总是很笨的。不用蒙师来打手板，也不用学官来打屁股，你自己心里知道：程序死在机器里，题也做不出来，不笨还能说是很聪明的吗？后来程序能走通，题目也能做出来，不光有大便通畅之感，还感觉自己正在变得聪明——人活在世界上，需要这样的经历：做成了一件事，又做成一件事，逐渐地对自己要做的事有了把握。从书上看到，有很多大学问家都有这样的心路历程。