Leetcode 编程训练

jopen 9年前

        Leetcode 这个网站上的题都是一些经典的公司用来面试应聘者的面试题,很多人通过刷这些题来应聘一些喜欢面试算法的公司,比如:Google、微软、非死book、Amazon 之类的这些公司,基本上是应试教育的功利主义。

        我做这些题目的不是为了要去应聘这些公司,而是为了锻炼一下自己的算法和编程能力。因为我开始工作的时候基本没有这样的训练算法和编程的网站, 除了大学里的“算法和数据结构”里的好些最基础最基础的知识,基本上没有什么训练。所以,当我看到有人在做这些题的时候,我也蠢蠢欲动地想去刷一下。

        于是,我花了3-4 个月的业余时间,我把 Leetcode 的 154 道题全部做完了。(这也是最近我没有太多的时间来写博客的原因,你可以看到我之前做的那个活动中有几个算法题来自于 Leetcode)有人说我时间太多了,这里声明一下,我基本上都是利用了晚上 10 点以后的时间来做这些题的。

        LeetCode 的题大致分成两类:

        1)基础算法的知识。这些题里面有大量的算法题,解这些题都是有套路的,不是用递归(深度优先 DFS,广度优先 BFS),就是要用动态规划(Dynamic Programming),或是拆半查找(Binary Search),或是回溯(Back tracing),或是分治法(Divide and Conquer),还有大量的对树,数组、链表、字符串和 hash 表的操作。通过做这些题能让你对这些最基础的算法的思路有非常扎实的了解和训练。对我而言,Dynamic Programming 是我的短板,尤其是一些比较复杂的问题,在推导递推公式上总是有思维的缺陷(数学是我的硬伤),通过做了这些题后,我能感到我在 DP 的思路上有了很大的收获。

        2)编程题。比如:atoi,strstr,add two num,括号匹配,字符串乘法,通配符匹配,文件路径简化,Text Justification,反转单词等等,这些题的 Edge Case, Corner Case 有很多。这些题需要你想清楚了再干,只要你稍有疏忽,就会有几个 case 让你痛不欲生,而且一不小心就会让你的代码会写得又臭又长,无法阅读。通过做这些题,可以非常好的训练你对各种情况的考虑,以及你对程序代码组织的掌控(其实就是其中的状态变量)。还记得我在《函数式编程》中说的,程序中的状态是你程序变得复杂难维护的直接原因。

        我觉得每个程序员都应该花时间和精力做这些题,因为你会从这些题中得到很大的收益。做完这些题后你一定会明白下面几个道理:

        1)想清楚了再干。这个观点我以前就在《多些时间可以少些代码》说过。如果你拿到题就上去直接写代码的话,你一定会被各种 case 打回来了。然后呢,你一着急,你就会进入那种我在《开发团队的效率》中说的那种毫无效率 case by case 的开发模式,而你也进入了“平庸模式”。于是你就会出现下图那样的情况。

Leetcode 编程训练

Case-by-Case Development

        2) 编程是脑力劳动,急不得。这个事情在这做这些题的时候你就会发现,要么是脑子转不过来了,要么就是明 明就差一点了,但程序怎么都调不对。如果你越着急的话,你就会发现你会离目标越远,而花的时间也会更多。另外,你会发现这些题基本上都是 50 行代码内就可以搞定的,但是为了这 50 行以内的代码,你要花好多时间和精力。coding  50 行代码在我们的日常工作中分分钟就完成,而 Leetcode 里的 50 行代码却没那么简单,也许,用这个你就可以区别什么是码农,什么是程序员了。

        3)加班要不得。因为我总是在晚上 10 点以后做题,所以,基本上都是在加班状态中工作。这种状态过上两三天,你就会发现,整个大脑已经不转了,而且不但不转,还会犯很多低级错误,很多事情都想 不清楚,一个晚上都在和程序的状态控制做搏斗,代码写得越来越乱,越来越没条理。于是这种时候,我都会休息几天,不做题了,然后再做题的时候,就觉得非常 地清楚。可见加班是编程最致命的敌人!

        我把我的 C++ 代码放到了 Github 上,大家也帮我 review 一下,看看有没有可以改善的。https://github.com/haoel/leetcode

        好了,不多说了,我希望大家有时间都去练练 LeetCode,无论是找工作还是对你的编程能力会有非常大的提高。

来自: coolshell.cn