Merge Two Sorted Lists (Python)

2014年2月10日 16:05

curr = curr.next执行后要确保curr不是None, 而是一个ListNode, 这就需要预先给curr一个ListNode, 也就是开头的curr = ListNode(0), 调了好久才发现, 晕...

继续阅读

Combination Sum (Python)

2014年2月10日 02:04

动态规划,依次求出target=1, 2, 3 ... N时的solution set, 后面的结果依赖于前面的结果。

继续阅读

先遍历,记录下每个节点在第几层,然后按层输出。

继续阅读

Restore IP Addresses (Python)

2014年2月09日 17:31

递归方法,str(int(s)) == s是为了去掉前导0,即Input="010010"时, Output不能是"0.1.0.010"之类的。

继续阅读

Rotate Image (Python)

2014年2月09日 10:59

In-place的话,先以matrix[0][n-1]...matrix[n-1][0]对角线为轴交换元素,再以水平中线(即第(n+1)/2行)交换元素。

继续阅读

看了这个, 挺简洁的, 不断消灭每一层的左子树。

继续阅读

Path Sum (Python)

2014年2月08日 17:26

树的题一开始要讨论root是否为空

继续阅读

First Missing Positive (Python)

2014年2月08日 16:51

题目给出1到N的正整数,但是不全,里面也可能混着0和负整数,找出第一个缺失的正整数。要求时间O(N)空间固定,可使用原数组,通过交换元素使得A[i] = i + 1,第二次遍历时不满足A[i] = i + 1的就是要找的数。

继续阅读

Subsets (Python)

2014年2月06日 11:36

 

继续阅读

二分法,分别讨论左边单调递增还是右边单调递增。

继续阅读

Sqrt(x) @ LeetCode (Python)

2014年2月05日 21:20

自己写果然一上来就超时啊, 看了水中的鱼的解体报告, 可以用二分法, 也可以用牛顿迭代法, x = (x + a / x) / 2, 膜拜大神啊

继续阅读

Add Binary (Python)

2014年2月05日 19:18

 

继续阅读

看了这个讲解, O(N)解法, 挺明白的。要一个栈来存放非递减的height序列, 即碰到大于等于栈顶的就入栈, 碰到小于栈顶的就pop。对于每个pop出的元素h[stack[top]],都要计算以它为最低高度的矩形的面积, 高度就是h[stack[top]], 宽度就是i - stack[-1] - 1, 注意栈中的元素都是非递减的。在h末尾多加一个0的目的是保证栈中的元素都可以被pop出。感谢朱老师提供了一个升级版(Largest rectangle problem)。

继续阅读

Maximum Subarray (Python)

2014年1月31日 21:50

看了Discuss才会的, 题目说还可以divide and conquer, 咋整捏? S[i]存的是以A[i]为结尾的Subarray的最大和。

继续阅读

Combinations (Python)

2014年1月31日 21:05

递归解法和非递归解法都能过。非递归解法中p指针指的位置如果达到了允许的最大值, p指针就前移。比如C(5,3)得到了[1,2,5], p指向第三个位置已经达到了最大值5, 则p前移,指向第二个位置,c[p]+=1, 于是得到[1,3,4]。当p指向第一个位置且它达到最大值,也就是[3,4,5]的时候就结束了,多谢朱老师的点播。递归解法要注意C(self, List, k)返回的是list of list。

 

继续阅读

Longest Common Prefix (Python)

2014年1月30日 01:13

继续阅读

3Sum (Python)

2014年1月30日 00:54

O(N^2)的解法, 对sum排序。先定下来a,在从a~末尾的这一段区间里找b,c, 两头往中间走。需要注意去重, 对于num=[-4,-1,-1,0,1,2]不要出来两组(-1,0,1)

继续阅读

Reverse Integer (Python)

2014年1月29日 18:32

继续阅读

注意head == None的情况,没用到Sorted这个特性,应该有占空间更少的解法。

继续阅读

Two Sum @ LeetCode (Python)

2014年1月29日 13:51

经Derek提醒,可用dict来存每个integer的初始位置。需注意num=[0,4,3,0], target=0这种两加数相等的情况。

 

继续阅读