“为什么我做不出算法题/Why I cannot solve algorithm questions”
07 Mar 2020看了下LeetCode刷题记录，开始刷题已经一年了，但是到现在如果遇到不明确/不熟悉的新题（eg：周赛），还是有很大的可能做不出来，不过做不出来的原因和一年前刚开始刷LeetCode已经有变化了。
一年前刚开始刷题的时候（也是刚开始学会写代码的时候），对数据结构有哪些都没什么了解，Java的API用的也不熟练，当时很多Easy题看答案都没办法理解，基本上全靠背。。。
一年过去了，对数据结构的掌握比以前要好不少，基本上遇到一道题能想出来大概可以用什么样的数据结构来解决。但是编程能力还是有问题，或者说是思维上还是不够严谨？比如说“星球坠落”那道题，看到题目的时候就想到了应该用Stack来解决不同方向的星球碰撞问题，但是两个星球相遇的时候，用什么样的逻辑来解决，思路上还不是很清晰，最后还是要靠看答案才能写出来，这应该是逻辑上思考的不够深入？
拿一年前不会做，但是现在可以比较流畅的做出来的题目来比较的话，这一年对刷题的领悟大概有三点：
- 对题目的理解 - Two Sum。 刚开始刷题的时候只会用两层循环来做，后来看答案会了HashMap，但是实际上掌握的还是不够熟练。现在已经可以用Map+双指针来做了，感觉上最重要不是某种算法，而是对题目的理解，对题目的输入输出理解透彻之后，就可以得心应手的写出想要的答案。
- 对数据结构的掌握 - Add Two Numbers。这是我亚马逊Intern面试的时候(19-2-26)被问到的题目。可以说在当时那个阶段，这道题完全靠背。我第一次接触到这个题目的时候是18年本科快毕业的时候的，当时看答案好久都没看明白（那个时候还没有学过算法，本科也几乎没有写过代码），难点就是根本就不懂数据是怎么保留住成功进入下一层的，当时答案区的三目表达式 ( val = node == null ? 0 : node.val) 也对我造成了很大的困扰。 后来在做完链表的专项训练之后，突然就感觉这道题很简单了，这一提升来自于对对应数据结构的掌握。同时，那段时间困扰我许久的LRU Cache也迎刃而解了，是在我想别的链表问题的时候突然醒悟到，LRU Cache不就是一个链表操作问题嘛？然后在白板上画了LRU Cache的结构图并且手写了代码，完美通过。
- 对算法的熟悉 - Number of Islands/Course Schedule/Word Ladder/AlienDict。岛屿数量这道题第一次遇到是在18年刚入学的时候，yjx在做twitter的oa的时候遇到的。当时我对这个题目完全没法理解，甚至连满屏幕的000111001001的输入也看不明白，当时同学秒掉了这道题目之后，我想了一会儿没想懂，就没再看了。 后来再接触到这个题目，是19年实习结束后，看九章算法的课的时候才想明白的（其实18年我已经学过算法课并且学了BFS/DFS了），在熟悉了BFS的思路之后，这道题也几乎是迎刃而解了。对这道题目的第二次理解加深是学Union-Find算法的时候，同样也是在研究算法的过程中，突然想到这道题可以用Union-Find来做，然后写出了代码。并且那两天用Union-Find做了好多之前用BFS/DFS的题，几乎都没有看答案，很流畅的写了出来。这一切主要还是来源于我对一个新算法的掌握而不是对答案的理解。(同类的通过学会对应算法就会做的题目还有很多，Course Schedule，AlienDict这种)
但是实际上现在困扰我的问题还有很多，比如String，Array这种题目(eg: 字符串匹配，最长子数列的和等等等），真的是几乎每一道Hard我都无能为力，都要看答案之后才知道要往哪个方向努力，Recursion的题目也要靠不同的练习来保持手感，看答案很容易看懂，但是很难自己想Recursion的写法。最近的计划是复习一下算法书中的基本内容，过段时间再来看看，以前不会做的题目是不能能熟练的做出来。