刷题的况味

写下这个标题的时候我才发现我竟然一直都不是很确定“况味”这个词到底是个什么意思，忘记了中学时候在什么地方看到过这个词，估计是在哪一堂语文课或者哪一次语文阅读的时候遇到的吧。去查了一下才知道跟“滋味”是差不多的，这么说来放在标题也还是挺贴切的。

我的博客里目前有343篇属于LeetCode类别的文章，而我实际在LeetCode上solve了834题，翻了提交记录发现我的第一次提交是在5年两个月前，也就是2015年的3月份。现在我已经忘记了当时为什么要开始做题，那个时候我还没有能出国、能来硅谷的奢望，估计大概是为了准备那一年的蓝桥杯和暑假里的保研夏令营吧。

我一开始的做题过程完全没有章法，纯粹是随机挑一题开始做，第一次提交竟然是#191，不知道当时是怎么找到这一题的。我本科的时候曾经还参与过学校的ACM比赛，水平实在是过于垃圾所以我用“参与”而不是“参加”，那个时候我看过刘汝佳的白书（算法竞赛入门经典），虽然几乎什么都没有记住，但是也算是对于LeetCode这种形式不是一张白纸吧。

我真正开始正视刷题这件事应该是在16年下半年的时候，毕竟有在北美找工作的压力，但是也还是没有什么计划性，我记得那时候应该是按照题号从小往大来刷的，笔记啊，整理啊更是统统没有（其实我现在也是没有🤷‍♂️）。我应该是从那个时候开始做周赛的，从那之后一直做了好几年。17年的时候应该一直在刷题，但是同时CMU的课业也是相当繁重，所以我也不清楚做了多少题。

绝大多数的题我都已经没有印象了，但是我还清晰的记得某些难题做不出来的时候，那种感受跟高中时的数学或者物理试卷上碰到难题的感觉差不多，似乎能抓住一点尾巴但是脑袋里面总是像是堵满了浆糊。

从18年，或者19的时候开始，大概做了400到500题左右，我能感觉到我的做题水平进入了一个新的阶段。很难精确地去描述这种感觉，我能感觉到我已经能在脑中快速过一遍LeetCode题目用到的所有的数据结构和算法，在看到一道题的时候，读完题我大概就知道需要用什么数据结构和算法来做。还有一个表现就是抽象能力的提高，稍微复杂一点的题目的文字描述总是会找一个情景套进去，从这个情景的描述中快速抽象出实际上应该使用的数据结构和算法是很重要的。

很多人总是会说做题无用，数据结构和算法在实际工作中基本上用不到。v2ex上这种自称CRUD boy的人尤其的多。不错，我工作快两年来一次都没有用到过DP和图论之类的东西，但是我认为更重要的不是你能记住几种算法，而是面对实际问题快速把它抽象为计算机语言的能力。

其实我是不喜欢“刷题”这个说法的，它给我的感觉总是有点功利化，有点漫不经心。做题本身应该是一种解决问题的娱乐方式，就像做数独，读侦探小说一样享受解谜的快感。而不是机械得去“刷”。

有一个很好的例子，在我写POI浏览器的舰娘收集进度插件的时候，遇到过这种情况：舰C服务器返回的数据中，舰娘类别数据和拥有的舰娘本身的数据是分开的。可以把类别数据当作是一个类，而实际拥有的舰娘是类的实例，比如你可以有两艘吹雪，她们都是同一个“类别”，每个舰娘的属性有一个ID会指向她的舰种。我现在的第一舰队旗舰是Fletcher改，她的舰船ID（api_id）是24326，舰种ID（api_ship_id）是692。而收集进度插件在处理的时候应该考虑类别而非实际舰娘，也就是即使你有两艘吹雪也只应该代表着“吹雪”这艘船已经收集了。但当考虑到改造的时候，问题就变得复杂了，在舰C服务器的数据中，每个舰娘类别中都有一个api_aftershipid属性，它指的是改造后的舰娘类别ID；与此同时吹雪、吹雪改和吹雪改二在收集进度中应该考虑为同一艘船，那么在有吹雪多号机以及不同改造形态的情况下，如何判断一艘吹雪改和一艘吹雪改二都是“吹雪”？稍微了解一些数据结构就能很容易地想到这个结构是一个典型的单链表：吹雪=>吹雪改=>吹雪改二，那么问题就抽象为，给定两个单链表节点，它们可能在也可能不在一个链表中，你要实现一个函数，返回它们是否在一个链表中。bruteforce的方法就是从一个节点开始遍历看能否到达另一个节点，因为两个节点的先后顺序不确定，所以前后调换再遍历一次。

让这个问题变得更有趣的是，舰娘改造现在是可以“反复横跳”的。Fletcher改 Mod.2的api_aftershipid指向Fletcher Mk.II，而Fletcher Mk.II的api_aftershipid又指向Fletcher改 Mod.2，在游戏中的表现就是形态切换了。而这个机制的存在就让上述的链表算法可能陷入死循环中。问题现在加了一个条件，这个单链表可能有环。要在链表的基础上解决这个问题就有点麻烦了，你也许会说：Fletcher这种情况，只要判断aftershipid是不是前一个节点不就行了？对于Fletcher这个特例，或者说大多数双形态切换来说都可行，但刷过题你应该就知道，用特例来通过边界条件是大忌，因为你不知道还有没有其他的边界条件。夕张就是这么个边界条件，她是三形态切换，具体的表现就是夕张改二、夕张改二特和夕张改二丁首尾相连都在环中。你需要一个更具有普适性的算法。

想到链表其实是一个有向图，而在我们的问题中，方向并不是很重要，所以可以抽象为一个无向有环图，实际上要解决的问题是非连通无向有环图中判断两个节点是否连通，或者说这两个节点是否在一个集合中。说到这里是不是觉得很熟悉了，刷了题你就应该知道无向图中两个节点是否连通是个非常常见的问题，你可以用DFS，BFS或者并查集来解决。而并查集简直就是为了解决这个问题而存在的。到此为止，这个问题终于有了一个简洁优雅的算法。

算法题没有做到熟练，对于数据结构不够熟悉，你可能要在这个问题上耗费不少的时间写出bug一堆的代码。谁也不知道在实际工作中会不会哪一天就碰到这种问题，如果没有过这种经历的话，恐怕真的到了那个时候才能体味一下刷题的况味吧。