算法题错题本


Author: yifei / Created: Nov. 14, 2017, 5:53 a.m. / Modified: Nov. 14, 2017, 1:53 p.m. / Edit

指导思想

第一次刷的时候,要多总结,把每道题的解题思路都认真写出来,此之谓“把书读厚”。一遍又一遍地机械刷 LeetCode 是没有用的。每次刷都要总结出当时不会的题,下次重点看不会的题,此之谓“把书读薄”。

方法

  1. 举例法。先列举一个例子,看能不能看出正确答案,或者推到出一半规律
  2. 模式匹配法。将问题与现有问题对比
  3. 简化推广法。修改某个约束条件,比如数据类型或者数据量,从而简化这个问题
  4. 数据结构头脑风暴法。快速过一遍数据机构,然后逐一尝试。

检查

至少要考虑一下几种测试数据:

  1. 正常值
  2. 空值
  3. 零值
  4. 最小值
  5. 最大值

程序设计思路如何,编程风格如何,细节是否考虑到了,是否有内存泄漏,是否采取了最优的算法,程序的可扩展性如何,能否举一反三。

思路

  1. 记得 l = l.next (leetcode #2)
  2. 不要混淆游标(cur)和头指针(head), 需要不断移动的是cur, 需要最终返回的是head (leetcode #2)
  3. 记得做数字模拟相关的题, 要进位, 要记得加上 remainder, 进位的值也要记得清零 (leetcode #2)
  4. 当需要翻转的时候,考虑使用栈
  5. O(nlogn) 几乎和 O(N) 一样好, O(logN) 几乎和 O(1) 一样好,O(N^2) 几乎和 O(e^N) 一样坏,
  6. 双指针题目:无非就是(1)指针怎么往中间走 (2)什么时候调换指针指的值。
  7. 凡是遇到用 Hash 的思考一下是不是数据量比较小,可不可以用数组或者 bitmap 代替。
  8. 检测小端 if(*(char*)&n == 1)

LeetCode那么多题, 盲目的刷总觉得像黑瞎子掰苞米, 最后真正沉淀下来变成自己的东西非常少。 所以,

总结点题型, 记点Templates

其实编程面试远没有你想象的那么难, 一般的公司无非就是问问数组字符串这类小题, 大一点的公司像某G啊, 某A啊, 喜欢问些图相关的问题。 这些问题说难也难, 说简单也简单, 因为其实他们都是有套路的。

看看LeetCode的标签, 无非就是Binary Search, Two Pointers, Sort, Dynamic Programming, Backtracking, Graph, Tree etc. 每类题先搞明白一道, 记一个解题套路, 实在搞不明白就背一个Templates, 遇到类似的问题就往上套。

其实刷题都是其次, 锻炼自己解决问题的思路才是最重要的, 因为在日常工作中, 没有套路可寻, 每一个突破, 每一个功能的实现, 都需要你自己动脑筋想解决方案, 判断解决方案是不是最优, 测试解决方案的鲁棒性, 等等。 那么遇到一个问题, 或者想实现一个东西的时候, 如何入手呢? 这不是你拍脑门就能 想出来的, 这需要你平时养成好的思考习惯, 不断的锻炼你的思维能力, 还有在工作中不断的积累经验。 刷题就是一个积累经验的过程。 它把用户想实现的东西以题这种更具象的东西呈现在你面前, 你每次刷题的思考, 其实都是在为你自己将来积累经验。

每天耗在那里, 时间也浪费掉了, 然后还抱怨: 我也学了啊, 我也工作了啊, 为什么别人都有成绩, 我没有?

因为别人过脑子了, 而你没有。

不要让自己的大脑称为别人思想的跑马场, 不要去重复别人的观点, 不要人云亦云, 养成独立思考的好习惯。 这个过程不会很简单, 就像人长肌肉的过程一样, 每次练肌肉一定都是对自己的极限的一次挑战, 要流汗, 要经历撑不住了还得硬撑的时候, 因为只有这样, 肌肉才能生长。

YN: 所以刷题似乎应该按照分类刷, 而不应该按照序号或者难易程度刷. 这点很重要

[1] https://sophiesongge.github.io/leetcode/2017/01/19/get-random.html


有任何问题可以发邮件到 kongyifei (at) gmail.com 讨论