leetcode 刷题有感
这是一个创建于 4105 天前的主题，其中的信息可能已经有所发展或是发生改变。
花了两个半月刷 leetcode，基本都解决了，其中大概有 10+ 道题目是参照答案来实现的。
因为边工作所以整个过程不容易，常常陷入一道题目不能自拔，有时候熬夜来做题目。
体会：
1 数据结构和算法是计算机技术的基础，有时候可以体会到美感。每一个 coder 都应该加强这方面的知识。
2 不要在乎题目本身，而是每个题目代表一定的背景知识，比如 dfs，剪枝，贪心和动态规划。
3 竞技和工程化写代码毕竟还是不一样的，思维方式不一样，最开始做题很困难是正常的。
4 实在想不出来可以看看提示，因为如果缺乏理论知识，怎么想也是想不出来的。
注意点：
1 建议从 AC Rates 排序的容易开始做起，能有一个良好的开始。
2 oj 这方面还是以 cpp 为主，我使用 python 实现的，有一些算法基本一样，cpp 能过而 python 不能过。
next：
我准备回归理论知识，因为在这个过程发现理论知识不够，特别是数学类的分析。
因为边工作所以整个过程不容易，常常陷入一道题目不能自拔，有时候熬夜来做题目。
体会：
1 数据结构和算法是计算机技术的基础，有时候可以体会到美感。每一个 coder 都应该加强这方面的知识。
2 不要在乎题目本身，而是每个题目代表一定的背景知识，比如 dfs，剪枝，贪心和动态规划。
3 竞技和工程化写代码毕竟还是不一样的，思维方式不一样，最开始做题很困难是正常的。
4 实在想不出来可以看看提示，因为如果缺乏理论知识，怎么想也是想不出来的。
注意点：
1 建议从 AC Rates 排序的容易开始做起，能有一个良好的开始。
2 oj 这方面还是以 cpp 为主，我使用 python 实现的，有一些算法基本一样，cpp 能过而 python 不能过。
next：
我准备回归理论知识，因为在这个过程发现理论知识不够，特别是数学类的分析。
 | 1 likaci 2014-10-08 14:12:42 +08:00  1 然后发现数学才是真爱，转行做数学去了…… |
 | 3 chengdujin 2014-10-08 14:49:36 +08:00 同刷中，国庆刚过完一遍 也是用 Python :D 还剩三道题感觉太麻烦，没做 20.0% Regular Expression Matching 14.0% Text Justification 14.0% Wildcard Matching 准备本周开始下一遍 |
 | 4 cloudzhou OP 1 @chengdujin Text Justification 难度很小，就是细节题目而已。 Wildcard Matching 这道题目我也是放弃了，虽然使用递归实现了，但是 timeout 了。 有一道题目我需要咨询一下： Longest Palindromic Substring 这道题目使用 动态规划 是很明显的，复杂度 O(n^2)，但是哪怕我照抄前人 cpp 的代码也不能通过。 我知道有一种 O(n) 的解法，http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html 不知道是不是 leetcode 对这道题目的评判标准提高了？ |
| 5 chengdujin 2014-10-08 15:27:05 +08:00 1 @cloudzhou 哈 longest palindromic substring 我也是n^2的，没过折腾了两天，最后还是选择用自己的办法（所以最后还是问号不是勾） 这道题我看讨论，n^2是过不了的，要用一个叫Manacher Algorithm的O(n)算法 |
| 6 cloudzhou OP @chengdujin 恩，看来是必须 O(n) 才能过，这个算法我就没有深究了。 leetcode 有一些题目，包括一些面试题，有点“讨巧”的意味，我不认为这是好的面试题。 对于个人，我更喜欢一些贴近现实的题目，比如 LRU 的实现，再引入并发，探讨空间很大，这是面试的好题目。 |
 | 7 yangff 2014-10-08 15:57:00 +08:00 via Android @cloudzhou mc是一个挺有用的算法。 特别是它蕴含了一个字符串的本质不同的回文串是O(n)级别的 |
 | 9 lxgone 2014-10-08 16:04:32 +08:00 哎，最近找工作也刷leetcode，也是按照AC Rate从高到底来的，可惜还是木有刷完 |
 | 10 lushl9301 2014-10-08 16:45:33 +08:00 回归理论真的必要么。 我在几年前做竞赛，理论基础比较差，但是大量时间练习。大脑零落，编程快速准确。 如今大学学习紧张，很少时间练习。虽然理论知识强了，但是编程水平下降到无法看。自己也一直觉得脑残。。非常不爽快。。。 估计是可能需要通过刷题库来解决了。。 |
| 11 cloudzhou OP @lushl9301 所以这就是竞技和实际开发的不同啊。 如果只是竞技，那就是不断的刷题，并且练习快速编程。 如果为了加强计算机基础，提高实际掌握问题的能力，那就回归到理论。 对我来说，竞技根本就没有必要，并且不是为了刷提为目的的，所以认真看书，加强理论知识才是我要做的。 |
 | 12 liuchang0812 2014-10-08 22:41:11 +08:00 via Android @cloudzhou 可以过啊。。。。 |
| 13 liuchang0812 2014-10-08 22:41:49 +08:00 via Android |
 | 14 dingyaguang117 2014-10-08 23:09:51 +08:00 via iPhone 正则那题要是在大三学编译原理的时候肯定能做出来，nfa转dfa，不过现在完全不记得 |
| 15 cloudzhou OP @liuchang0812 @chengdujin 真是很神奇，@liuchang0812 的算法真的能过，我是参照 https://github.com/soulmachine/leetcode 里面的解法的，完全照抄也没有通过，这两者之间有什么不一样呢？ |
| 16 cloudzhou OP |
| 17 cloudzhou OP @liuchang0812 @chengdujin 哈哈，我已经找到问题的关键了，这两者复杂度是一样的，soulmachine/leetcode 的方法更加好理解，如果注销了 fill_n(&f[0][0], n * n, false); 这一句就完全可以通过了。 如果 @liuchang0812 加了 fill_n(&f[0][0], 1001 * 1001, 0); 这一句同样也是 Time Limit Exceeded 的，这真是个有趣的问题。 从工程化来说：申请并且对内存段进行 zero 是一个很好的习惯。 |
 | 18 chenggiant 2014-10-09 00:53:25 +08:00 via iPhone 膜拜一下！我刷了4个月了，还是只做了60题... |
| 19 liuchang0812 2014-10-09 00:58:38 +08:00 @cloudzhou 这个数组,代码本来紧跟着就是初始化的过程.工程上来说也不应该多次对大内存操作,而且还是无用的操作. |
 | 20 thinkmore 2014-10-09 09:01:58 +08:00 数学很重要，可是天赋。。。 |
| 21 cloudzhou OP @liuchang0812 我对 c/c++ 不了解，之前看书的时候是推荐申请内存之后 memset zero，是一种编程上的防御手段吧。所以我也不了解现在默认情况下申请内存后就是 zero 的。 谁对这一块了解的麻烦讲讲？ |
 | 22 wudikua 2014-10-09 11:28:23 +08:00 java实现的飘过~ |
 | 23 tension2012 2014-10-09 14:47:41 +08:00 test data貌似也不能看啊 |
| 24 lushl9301 2014-10-09 21:20:04 +08:00 @cloudzhou 我觉得如果这样想，看efficient cpp呀，code complete啊，programming pearls。再加上TAOCP，慢慢啃。哈哈。 我是大一去啃APUE，看了有1/8. 看TAOCP一卷多，然后转到programming pearls。加油加油。。。希望找到一起学习计算机经典的人。。 |
| 25 cloudzhou OP @lushl9301 你们现在这种意识真好，以前迷迷糊糊不知道怎么学起，计算机就应该从基本理论，算法和数据结构开始学起 |
 | 26 John1984 2015-04-14 20:52:14 +08:00 @chengdujin O(n^2)可以过，python代码。http://blog.csdn.net/cjhou/article/details/45044813 |
 | 27 armstrong 2017-03-12 14:15:37 +08:00 真是羡慕你们呀，我是从今年才开始意识到这个问题，正在努力弥补中 |
Select Language