图解leetcode经典题型，普通人的刷题经验(200+)

背景：
转码选手，工作经验总共7年 偏前端，相当于CS本科毕业工作5年吧。Leetcode只刷了200+题，所以大牛们可以关闭此页了。一共刷了2遍，第一次是5年前，第二次是今年3月重新刷起，直到5月拿了offer。我自己的经验是，刷题就是一个在大脑里画图的过程。一开始刷比较艰难，刷到100题左右脑袋里开始有图浮现，到现在看完一道题就在脑袋里用图解，最后图画完了 题目也就解出来了。

因为从来没有看到过类似的刷题总结，所以想自己写一篇，如果能早些看到应该能省一半刷题时间。可能你的方法跟我不一样，欢迎讨论。

适用读者：
觉得刷题有难度，medium都很吃力；逻辑能力稍弱；刚转码选手；刷了大量题但没有总结思路的人
希望此文可以帮到你

废话不多，接下来图文解析经典题型↓↓ 喜欢的话别忘了点个赞，能送点米就更好了！
注：所有代码都是伪代码
题型1：Linked List
题目链接：https://leetcode.com/problems/reverse-linked-list/
先拿最简单的练练手，先看参数设置：
c - 传入的head
p - preHead，一般初始会定义一个preHead = new Node(0, head)，即它的next为head。最后return p.next就行了
n - c.next
肯定需要遍历一遍才能reverse inplace。每次分4步，基本原理是将一个node的箭头指向另一个地方。

(1) 初始(确认n存在)
(2) 把p.next指向n
(3) 把c.next指向n.next
(4) 把n.next指向c
最后使n = c.next就能开始下一轮循环了。
是不是很简单呢，接下来加大难度

题型2：backtrack or DFS/BFS
题目链接：https://leetcode.com/problems/subsets/
backtrack其实涵盖很多，其中DFS最为经典，来看这道subsets。
首先先用数学的方法分析一下，最后结果有多少子集(输入n)？

答案是：nC0 + nC1 + nC2 + nC3 + ... = 2^n
简单的for/while循环只能整n遍，所以看到这个数字你想啊，两层循环才n^2，肯定搞不定啊。所以要用backtrack，我想称之为套娃。来画个图吧，数字代表index从1开始：(有点乱，蓝色的部分最后看)

我们再来看代码怎么实现的呢，如下currentArray代表上图中箭头旁的array：[1], [1,2], [1,3] ....

1. function 套娃(nums, index, result, currentArray) {
   
2.     result.push(currentArray) // <----- 套大娃进最终结果
   
3. 
   
4.     for (let i = index ; i < nums.length ; i++) {
   
5. 
   
6.         currentArray.push(nums) // <----- 把这个小娃套进去
   
7. 
   
8.         dfs(nums, i + 1, result, currentArray) // <----- 打包成2->n, 3->n....
   
9. 
   
10.         currentArray.pop() // <----- 把上面套进去的小娃拿出来
    
11. 
    
12.         // follow up: 如果nums里包含重复元素，那if 这里nums == nums[i-1]，则直接continue。想一下为什么
    
13.     }
    
14. 
    
15. }
    
16. 
    
17. 
    
18. function subsets(nums) {
    
19.     Array<Array<Integer>> result = new Array<>();
    
20. 
    
21.     套娃(nums, 0, result, [])
    
22. 
    
23.     return result
    
24. };

复制代码

配合图形应该不难脑补出整个过程。。。以后如果碰到变种题，只要想象在图中哪块区域操作一下就能解决了。


题型3：tree node
题目链接：https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/binary-tree-preorder-traversal/
https://leetcode.com/problems/binary-tree-postorder-traversal/

如果你能轻松的理解第二题，那么这里大概可以跳过了。
对于tree类型的题，只要理解了本质，那么各类变种都是千篇一律。这次我们先看代码：

1. function travel(root) {
   
2. // 判断是否为空
   
3. if (!root) {
   
4.   return
   
5. }
   
6. 
   
7. travel(root.left)
   
8. 
   
9. travel(root.right)
   
10. 
    
11. }
    
12. 
    
13. function solution(root) {
    
14. travel(root)
    
15. 
    
16. reuturn ...
    
17. }
    

复制代码

再来看图，标注的方块index为上面代码遍历的顺序

所以现在我们已经有了怎么遍历tree的方法，想求inorder, preorder, postorder,怎么办呢？小修改下代码：

1. function travel(root) {
   
2. // 判断是否为空
   
3. if (!root) {
   
4.   return
   
5. }
   
6. 
   
7. // <------ 想要preorder？在这里加
   
8. 
   
9. travel(root.left)
   
10. 
    
11. // <------ 想要inorder？在这里加
    
12. 
    
13. travel(root.right)
    
14. 
    
15. // <------ 想要postorder？在这里加
    
16. }
    
17. 
    
18. // <------ 想要成为rapstar？那你来错地方了，咳咳。。。
    

复制代码

题型4：dp
题目链接：https://leetcode.com/problems/longest-palindromic-substring/

不知道在哪看过这么一句话，跟string有关的问题，基本都能用dp解。
这道题求最长回文。判断一段string是不是回文复杂度O(n)，在一段string内求所有substring复杂度为O(n^2)，所以暴力解法复杂度为O(n^3)。于是，只要争取把复杂度优化到O(n^2)就算成功了。都是普通人，我们不考虑马拉车解法。。

用dp前，分析下能不能找到通项公式。我假设大家都学过高中数列哈，就是找n-1项与n项之间的关系。
一维：                A = f(A[i - 1])
二维(可能)：        A[j] = f(A[i - 1][j - 1])
....
能通过题目把概念化的dp带入A就行了。

再来看题，dp最好能代表一段substring是不是回文。
一维dp是不是不够用啊？用一维的话 i 代表什么好像都不对，
那就定义二维dp[j]。i，j分别代表substring的头跟尾index。然后看图说话：

以上，需要循环2遍，从j=0~n-1;i=0~j，因为i一直在j前面，复杂度O(n^2)。得出一个完整dp，里面储存了i~j是否为回文的信息。
如何求得最大值？我们需要对该dp再次遍历，找出最长，并且记录i, j。无法脑补的同学看下图(这里i在j前面，所以只有斜半区有值，且对角线上的值都为true)：

这次遍历又是O(n^2)，达到了预期，代码没什么花头就略了。


总结：
刷题只是敲门砖，我们大部分都是普通人，没必要去追求竞赛类的难度，舍本求末。但刷题确实有助于锻炼我们逻辑思维的能力，这是码农必不可缺的一堂课。可能得益于多年前端的经验，把算法图像化对我来讲比较容易。因为拿到offer，所以现在我的刷题之路就暂停了。大家如果有特别想图像化的题，可以留下评论，有时间的话我可以看看。

一米值千金！

厉害，用JS刷题比较佩服的，刚接触JS，感觉是一门很奇特的语言

hikagu 发表于 2021-6-8 02:49
想看segment tree! 谢谢楼主！

工作一段时间没回来看自己的贴了，居然这有个问题系统还没回？
一般给出tree，求数列，这样的问题都能用上面的代码解决，即

1. function travel(root) {
   
2.   if (!root) {
   
3.     return
   
4.   }
   
5.     // <------ 想要preorder？在这里加
   
6.   travel(root.left)
   
7.     // <------ 想要inorder？在这里加
   
8.   travel(root.right)
   
9.     // <------ 想要postorder？在这里加
   
10. }

复制代码

比如求inorder的数列：

1. function travel(root, list) {
   
2.   if (!root) {
   
3.     return
   
4.   }
   
5.   travel(root.left)
   
6.   list.push(root.val)
   
7.   travel(root.right)
   
8. }

复制代码

想象自己是个渺小的蚂蚁，遇到路口往左走，往右走，在什么地方停下干点活

剩下就是给数列，求tree的问题。那类比较复杂，以后再讲。。

lkean9 发表于 2021-6-6 12:33
感谢楼主，已加米。最近正好在做backtracking tag的题目，发现大多数题目都可以用相同的模板套路去做，其实 ...

如果是用Java解的，可以事先指定List的长度：n/0.75 + 1。防止扩容耗时
忘了pop的时候会不会调整长度了。。会的话找个别的方法
我用js做倒不用考虑这种问题

楼主辛苦了！加个米支持一下！

Falldawn 发表于 2021-06-05 13:58:56
厉害，用JS刷题比较佩服的，刚接触JS，感觉是一门很奇特的语言

js其实比java简单多了，基本没有数据结构。不过刷题的方法应该适用于所有语言

感谢楼主，已加米。最近正好在做backtracking tag的题目，发现大多数题目都可以用相同的模板套路去做，其实就是for 循环的dfs加上最后一行的pop。当然这种暴力循环复杂度大多时候都是N!，所以有些特殊的题目需要用memo或者trie去优化，不然会有些test case出现time limit exceeded的错误。大家刷题的时候最好也能花一些时间去思考可能存在的优化选择

谢谢分享

很好的总结，谢谢～

想看segment tree! 谢谢楼主！

谢谢分享!