leetcode 刷题有感

[cloudzhou]

花了两个半月刷 leetcode，基本都解决了，其中大概有 10+ 道题目是参照答案来实现的。
因为边工作所以整个过程不容易，常常陷入一道题目不能自拔，有时候熬夜来做题目。
体会：
1 数据结构和算法是计算机技术的基础，有时候可以体会到美感。每一个 coder 都应该加强这方面的知识。
2 不要在乎题目本身，而是每个题目代表一定的背景知识，比如 dfs，剪枝，贪心和动态规划。
3 竞技和工程化写代码毕竟还是不一样的，思维方式不一样，最开始做题很困难是正常的。
4 实在想不出来可以看看提示，因为如果缺乏理论知识，怎么想也是想不出来的。

注意点：
1 建议从 AC Rates 排序的容易开始做起，能有一个良好的开始。
2 oj 这方面还是以 cpp 为主，我使用 python 实现的，有一些算法基本一样，cpp 能过而 python 不能过。

next：
我准备回归理论知识，因为在这个过程发现理论知识不够，特别是数学类的分析。

[likaci]

然后发现数学才是真爱，转行做数学去了……

[cloudzhou]

@likaci 我还真的是很喜欢数学啊 :-)，就是遗憾没有太多时间啊

[chengdujin]

同刷中，国庆刚过完一遍 也是用 Python :D

还剩三道题感觉太麻烦，没做
20.0% Regular Expression Matching
14.0% Text Justification
14.0% Wildcard Matching

准备本周开始下一遍

[cloudzhou]

@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 对这道题目的评判标准提高了？

[chengdujin]

@cloudzhou 哈 longest palindromic substring 我也是n^2的，没过折腾了两天，最后还是选择用自己的办法（所以最后还是问号不是勾）

这道题我看讨论，n^2是过不了的，要用一个叫Manacher Algorithm的O(n)算法

[cloudzhou]

@chengdujin 恩，看来是必须 O(n) 才能过，这个算法我就没有深究了。
leetcode 有一些题目，包括一些面试题，有点“讨巧”的意味，我不认为这是好的面试题。
对于个人，我更喜欢一些贴近现实的题目，比如 LRU 的实现，再引入并发，探讨空间很大，这是面试的好题目。

[yangff]

@cloudzhou mc是一个挺有用的算法。
特别是它蕴含了一个字符串的本质不同的回文串是O(n)级别的

[cloudzhou]

@yangff 还有人说可以使用后缀数组实现，也没有仔细看。等我补充一点理论知识再来做题 :-)

[lxgone]

哎，最近找工作也刷leetcode，也是按照AC Rate从高到底来的，可惜还是木有刷完

[lushl9301]

回归理论真的必要么。
我在几年前做竞赛，理论基础比较差，但是大量时间练习。大脑零落，编程快速准确。
如今大学学习紧张，很少时间练习。虽然理论知识强了，但是编程水平下降到无法看。自己也一直觉得脑残。。非常不爽快。。。

估计是可能需要通过刷题库来解决了。。

[cloudzhou]

@lushl9301 所以这就是竞技和实际开发的不同啊。
如果只是竞技，那就是不断的刷题，并且练习快速编程。
如果为了加强计算机基础，提高实际掌握问题的能力，那就回归到理论。
对我来说，竞技根本就没有必要，并且不是为了刷提为目的的，所以认真看书，加强理论知识才是我要做的。

[liuchang0812]

@cloudzhou 可以过啊。。。。

[liuchang0812]

@cloudzhou 可以过啊。。。。我就是n2过的
https://github.com/Liuchang0812/leetcode/blob/master/longest-palindromic-substring.cpp

[dingyaguang117]

正则那题要是在大三学编译原理的时候肯定能做出来，nfa转dfa，不过现在完全不记得

[cloudzhou]

@liuchang0812
@chengdujin
真是很神奇，@liuchang0812 的算法真的能过，我是参照 https://github.com/soulmachine/leetcode 里面的解法的，完全照抄也没有通过，这两者之间有什么不一样呢？

[cloudzhou]

@liuchang0812 这是另一种做法，按理来说算法复杂度一样，为什么不能过呢？

https://gist.githubusercontent.com/azhoulinux/10f082db81ff5561d243/raw/e0d37ff35c09919ffe1fb42a16adf101a9a93253/gistfile1.txt

[cloudzhou]

@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 是一个很好的习惯。

[chenggiant]

膜拜一下！我刷了4个月了，还是只做了60题...

[liuchang0812]

@cloudzhou
这个数组,代码本来紧跟着就是初始化的过程.工程上来说也不应该多次对大内存操作,而且还是无用的操作.

[thinkmore]

数学很重要，可是天赋。。。

[cloudzhou]

@liuchang0812 我对 c/c++ 不了解，之前看书的时候是推荐申请内存之后 memset zero，是一种编程上的防御手段吧。所以我也不了解现在默认情况下申请内存后就是 zero 的。

谁对这一块了解的麻烦讲讲？

[wudikua]

java实现的飘过~

[tension2012]

test data貌似也不能看啊

[lushl9301]

@cloudzhou 我觉得如果这样想，看efficient cpp呀，code complete啊，programming pearls。再加上TAOCP，慢慢啃。哈哈。
我是大一去啃APUE，看了有1/8. 看TAOCP一卷多，然后转到programming pearls。加油加油。。。希望找到一起学习计算机经典的人。。

[cloudzhou]

@lushl9301 你们现在这种意识真好，以前迷迷糊糊不知道怎么学起，计算机就应该从基本理论，算法和数据结构开始学起

[John1984]

@chengdujin O(n^2)可以过，python代码。http://blog.csdn.net/cjhou/article/details/45044813

[armstrong]

真是羡慕你们呀，我是从今年才开始意识到这个问题，正在努力弥补中