leetcode刷题

2016-03-02

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

leetcode面试题