leetcode刷题

leetcode刷到150了，记得我刚开始刷的时候leetcode上面好像才200道题出头。主要是断断续续有一阵没一阵的，刷了好久。上个图，写点东西，留个纪念。

最开始刷的时候风格是随机挑一个，开始做。后来有点功利了，按acceptance排序，切水题。

记得刚开始刷时候时甚至在纸上写代码了再敲上去，所以早期做的题还经常出现编译不过什么的。后来用编辑器敲代码了，再后来，leetcodeh上面推出了testcase功能以后喜欢直接在线编辑器，通过率的含金量就低很多。

大部分题目都是独立在思考，去网上参考别人的答案的还算挺少的，这点比较欣慰。不过也有不好的地方是没有做完之后去对比别人的解法，举一反三，寻求最佳解法。

说一些好玩的吧！

C语言像很基础的数据结构都没有库。所以一些简单的代码，我常常就stack[500]或者queue[1000]这种样子把数组大小写死。有时候会挂，就改大了再去试(有些题的测试用例是非常大的)。要不就是内存分配了不释放的，总之是很偷懒。

常常忘记初始化。像栈上的临时变量，Go都是默认初始化过，写多了习惯了，再写c就容易漏。像比如二叉树，就常常忘记将那些无子结点的初始化为NULL，导致容易runtime error。

有些看起来很简单的题，不使用优化的算法绝对是超时的。想都不要想用基础算法能通过。比如求小于n的质数，比如实现strStr。考点就是进阶算法。

还有些直接递归写法，基本是超时，像有些有动态规划的。不要心存侥幸，要不就打表缓存计算结果。

处理涉及到+-1边界问题的时候，千万不能心急，不能抱着试的态度去做。一定要写代码时就好好想清楚边界条件。比如说有次已经是凌晨0点37分了，很困，想做完那道题了睡觉，结果提交-出错-再改一改去撞运气-又出错，弄了好几次还是没AC...最终郁闷的老老实实去睡觉了。第二天花了10分钟认真考虑好边界条件再重写代码，一次通过。

涉及到溢出的题目是特别恶心的。像Sqrt()时用到tmp*tmp可能超整数表示范；还有pow(x, n)对于负数处理，因为负数表示最大范围比正数大1，abs(INT_MIN)不等于正数，因为补码表示负数会比正数表示的范围大一个。像Contains Duplicate III会有溢出的测试用例。可以用除法转到浮点数了再计算；还有做哪道题来着，二分就必须mid=beg+(end-beg)/2，也是故意搞了溢出的测试用例的。

需要返回二维数组的题也是特别恶心。主要是C语言的处理比较麻烦。老实说比较不喜欢做这类题，有时候题目很简单，反而是处理二维数组生成结果的代码更让人觉得特繁琐。

还有偏智力题或者说有投机取巧倾向的也是我不喜欢的：169,136。

细心很重要。有些看上去很简单，实际上还是很要注意小细节的。比如说两个链表相加那题，就要考虑到最后一位有进位的结点。二叉树序列化那题，我直接把结点拷出来放数组里面，指针改成下标，弄巧成拙：slice扩容后数组地址会变，里面的空间是不能传指针的，只能用下标！！

巧妙的数据结构的选用影响非常大。N皇后问题。自己做的时候是用struct Pos {int x; int y}的数组来表式皇后放置位置的。每次重(0,0)位置开始查找下一个皇后应该放置的位置，这样求出来不是distinct解。虽然可以排序再去重，但这种做法比较麻烦。后来看到网上用一维数组表示放置位置，数组中第i个元素的值代表第i行的皇后位置，这种表示就简单好多。

好了，不说了。代码在这里 https://github.com/tiancaiamao/leetcode