kitt blog (欢迎留言，最近刷的题目放到github上了)

先对num排序, 然后建一个dictionary d, d[num[p]+num[q]] = [(p,q) pairs 满足num[p] + num[q]], 而且这里的(p,q) pair总是满足p < q。然后用二层循环来搜, num[i]是四元组最小的数, num[j]是第二小的数, 判断d中有没有target - num[i] - num[j]这个key的时间是O(1), 如果有这个key, 就把找到的四元组加入最后的返回结果。res使用set()来去重, 否则对于输入[-3,-2,-1,0,0,1,2,3], 0会出现两个[-3, 0, 1, 2]和两个[-2, -1, 0, 3]。

First sort num, then build a dictionary d, d[num[p]+num[q]] = [(p,q) pairs which satisfy num[p] + num[q]], here all (p,q) pairs satisfy p < q. Then use a nested for-loop to search, num[i] is the min number in quadruplet and num[j] is the second min number. The time complexity of checking whether d has the key target - num[i] - num[j] is O(1). If this key exists, add one quadruplet to the result. Use set() to remove duplicates in res, otherwise for input [-3,-2,-1,0,0,1,2,3], 0 there will be two [-3, 0, 1, 2] and two [-2, -1, 0, 3].

class Solution:
    # @return an integer
    def maxArea(self, height):
        L, R, maxV = 0, len(height) - 1, -1
        while L < R:
            maxV = max(maxV, min( height[L], height[R] ) * (R - L) )
            if height[L] <= height[R]:
                L += 1
            else:
                R -= 1
        return maxV

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def deleteDuplicates(self, head):
        if head == None: return None
        dummy = ListNode(10**10)
        dummy.next, head = head, dummy # add a dummy node
        pprev, prev, curr, dupFlag = head, head.next, head.next.next, False
        while True:
            if dupFlag == True:
                if curr == None:
                    pprev.next = None
                    break
                if prev.val != curr.val:
                    pprev.next, prev, dupFlag = curr, curr, False
            else:
                if curr == None: break
                if prev.val == curr.val: 
                    dupFlag = True
                else:
                    pprev, prev = pprev.next, prev.next
            curr = curr.next
        return head.next # remove dummy

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    # @param inorder, a list of integers
    # @param postorder, a list of integers
    # @return a tree node
    def buildTree(self, inorder, postorder):
        if not inorder: return None # inorder is empty
        self.inorder, self.postorder = inorder, postorder
        return self.dfs(0, 0, len(inorder))
    
    def dfs(self, inLeft, postLeft, Len):
        if Len <= 0:
            return None
        root = TreeNode(self.postorder[postLeft + Len - 1])
        rootPos = self.inorder.index(self.postorder[postLeft + Len - 1])
        root.left = self.dfs(inLeft, postLeft, rootPos - inLeft)
        root.right = self.dfs(rootPos + 1, postLeft + rootPos - inLeft, Len - 1 - (rootPos - inLeft))
        return root

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param preorder, a list of integers
    # @param inorder, a list of integers
    # @return a tree node
    def buildTree(self, preorder, inorder):
        if not inorder: return None # inorder is empty
        root = TreeNode(preorder[0])
        rootPos = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1 : 1 + rootPos], inorder[ : rootPos])
        root.right = self.buildTree(preorder[rootPos + 1 : ], inorder[rootPos + 1 : ])
        return root

class Solution:
    # @return a list of integers
    def grayCode(self, n):
        if n == 0: return [0]
        L = [0, 1]
        for i in xrange(2, n + 1):
            t = 1 << (i - 1)
            L = L + [ j + t for j in L[::-1] ]
        return L

另一种解法:

class Solution:
    # @param {integer} n
    # @return {integer[]}
    def grayCode(self, n):
        # from wikipedia, https://en.wikipedia.org/wiki/Gray_code
        # binaryToGray: return (num >> 1) ^ num, i.e. (num / 2) XOR num
        # grayToBinary:
        # unsigned int mask;
        # for (mask = num >> 1; mask != 0; mask = mask >> 1)
        #     num = num ^ mask;
        # return num;
        return [(i >> 1) ^ i for i in xrange(2 ** n)] 

使用DFS, 不要再开一个新的棋盘或其他很大的变量来记录状态，不然容易超时。

Use DFS. Don't make a new board or other large variables to record state, or it's easy to TLE.

先求出每个子串是否为palindrome, 用isPal记录。isPal[i][j] == true含义是从s[i]到s[j]的子串(包含起点终点)是回文串。再用DFS。

First use isPal to record each substring is palindrome or not. "isPal[i][j] == true" means a substring starts from s[i] (included) to s[j] (included) is a palindrome. Then use DFS.

用一个栈记录左括号, 右括号和index, 如果当前括号是右括号且栈顶是左括号, 则弹栈并更新maxLen。

Use a stack to record left paren, right paren and index. If current paren is ')' and stack top is '(' then pop up and update maxLen.

当没有重复元素时, A[left] <= A[mid]表示右边部分是rotated的。当有重复的元素时, A[left] <= A[mid]要分开讨论了, 比如A=[1,3,1,1,1], left = 0, right = 4, mid = 2, 虽然A[left] <= A[mid], 但是rotated的部分在左边。此时A[left] < A[mid]才表示右边部分是rotated,  A[left] == A[mid]时left++即可。

When there's no duplicate, A[left] <= A[mid] means the right part is rotated. When there are duplicates, A[left] <= A[mid] is not certain. E.g. A=[1,3,1,1,1], left = 0, right = 4, mid = 2, although A[left] <= A[mid], the left part is rotated. Here A[left] < A[mid] means the right part is rotated, when A[left] == A[mid] just left ++.

先找到list的中点, 把后半部分reverse, 再merge前半部分list和后半部分list。

Find the middle node of the list, then reverse the second half of the list, then merge the first half list and the second half list.

动态规划。看了水中的鱼的解题报告, dp[i][j]表示word1前i个字母变成word2前j个字母的步数(edit distance)。如果word1的第i个字母等于word2的第j个字母, 则dp[i][j] = dp[i-1][j-1]。如果不等, 则有三种情况:

1) 把word1的前i-1个字母变成word2的前j-1个字母, 再把word1的第i个字母换成word2的第j个字母, 即dp[i-1][j-1] + 1

2) 把word1的前i个字母变成word2的前j-1个字母, 再加上word2的第j个字母, 即dp[i][j-1] + 1

3) 删掉word1的第i个字母, 把word1的前i-1个字母变成word2的前j个字母, 即1 + dp[i-1][j]

三种情况的最小值就是dp[i][j]。初始情况: dp[i][0] = i (0 <= i <= word1 length), dp[0][j] = j (0 <= j <= word2 length).

Dynamic programming. Let dp[i][j] indicate the steps (edit distance) of changing word1's first i letters to word2's first j letters. If word1's ith letter equals to word2's jth letter, then dp[i][j] = dp[i-1][j-1]. If not, 3 cases:

1) Change word1's first i-1 letters to word2's j-1 letters, then change word1's ith letter to word2's jth letter, i.e. dp[i-1][j-1] + 1

2) Change word1's first i letters to word2's first j-1 letters, then add word2's jth letter, i.e. dp[i][j-1] + 1

3) Delete word1's ith letter, then change word1's first i-1 letters to word2's first j letters, i.e. 1 + dp[i-1][j]

dp[i][j] is the min value of the above 3 cases. Initialization: dp[i][0] = i (0 <= i <= word1 length), dp[0][j] = j (0 <= j <= word2 length).

Let num = [1,2,3,...,n]. The first digit is k/(n-1)!, then let k = k % (n-1)! and remove this digit from num. The second digit is k/(n-2)!, then let k = k % (n-2)! and remove this digit from num and so on.

看了水中的鱼的解题报告。Find a solution here.

1. From right to left, find the first digit (PartitionNumber) which violates the increase trend.

2. From right to left, find the first digit which is larger than PartitionNumber, call it ChangeNumber.

3. Swap PartitionNumber and ChangeNumber.

4. Reverse all the digit on the right of partition index.

使用0,1,2,3四个值表示方向以便切换, 用maxUp, maxDown, maxLeft, maxRight四个变量记录四个边界。当 curr >= n * n 就结束。

0,1,2,3 four values are used to indicates direction, maxUp, maxDown, maxLeft, maxRight four variables are used to record four boundaries. When curr >= n * n program can return.

使用0,1,2,3四个值表示方向以便切换, 用maxUp, maxDown, maxLeft, maxRight四个变量记录四个边界。当maxUp > maxDown 或 maxLeft > maxRight时就结束。

0,1,2,3 four values are used to indicates direction, maxUp, maxDown, maxLeft, maxRight four variables are used to record four boundaries. When maxUp > maxDown or maxLeft > maxRight program can return.

使用一个快指针fast来遍历数组, 一个慢指针slow来记录最终结果, 用count记录同一个数出现的次数, 如果遇到新数或count<=2则更新A[slow]。

Use a "fast" pointer to traverse the array, a "slow" pointer to record final results. Use "count" to record the occurrences of a number. If "fast" meets a new number or count <= 2, then update A[slow].

二分查找, 把二维的坐标换成一维的即可。

Binary search, just convert 2D coordinate to linear coordinate.

Add a dummy node (aka header node), things will become easier.

从这里看到一种很巧妙的解法, 在遍历当前层时, 构建下一层。

I saw a wonderful solution here. When traversing the current level, build the next level.