divideandconquer

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example, Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def generateTrees(self, n):
    """
    :type n: int
    :rtype: List[TreeNode]
    """
    if n == 0: return []
    return self.generate(1,n)

def generate(self, i, j):
    l = []
    if i > j: l.append(None)
    for k in xrange(i, j+1):
        left = self.generate(i,k-1)
        right = self.generate(k+1,j)
        for nodeleft in left:
            for noderight in right:
                root = TreeNode(k)
                root.left = nodeleft
                root.right = noderight
                l.append(root)
    return l

第二题 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

解法

class Solution(object):
def restoreIpAddresses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    res = []
    for a in range(1,4):
        for b in range(1,4):
            for c in range(1,4):
                for d in range(1,4):
                    if a+b+c+d == len(s):
                        A = int(s[0:a])
                        B = int(s[a:a+b])
                        C = int(s[a+b:a+b+c])
                        D = int(s[a+b+c:a+b+c+d])
                        if A <= 255 and B <= 255 and C <= 255 and D <= 255:
                            ans = str(A)+'.'+str(B)+'.'+str(C)+'.'+str(D)
                            if len(ans) == len(s) + 3:
                                res.append(ans)
    return res

第三题 Permutations

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解法

class Solution(object):
def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    res = []
    self.dfs(nums, [], res)
    return res

def dfs(self, nums, path, res):
    if not nums:
        res.append(path)
    for i in xrange(len(nums)):
        self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

第四题 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

解法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def sortedArrayToBST(self, nums):
    """
    :type nums: List[int]
    :rtype: TreeNode
    """
    if not nums: return None
    return self.dfs(nums, 0, len(nums)-1)


def dfs(self, num, start, end):
    if start > end:
        return None
    if start == end:
        return TreeNode(num[start])
    mid = start + (end-start)/2
    root = TreeNode(num[mid])
    root.left = self.dfs(num, start, mid-1)
    root.right = self.dfs(num, mid+1, end)
    return root

第五题 Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

解法

class Solution:
# @param {ListNode} head
# @return {TreeNode}
def sortedListToBST(self, head):
    if not head:
        return None
    if not head.next:
        return TreeNode(head.val)

    dummyHead = ListNode(0)
    dummyHead.next = head
    slow, fast = dummyHead, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    root = TreeNode(slow.next.val)
    root.right = self.sortedListToBST(slow.next.next)
    slow.next = None
    root.left = self.sortedListToBST(head)

    return root

第六题 Median of Two Sorted Arrays

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

解法

class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
    l=len(A)+len(B)
    return self.findKth(A,B,l//2) if l%2==1 else (self.findKth(A,B,l//2-1)+self.findKth(A,B,l//2))/2.0


def findKth(self,A,B,k):
    if len(A)>len(B):
        A,B=B,A
    if not A:
        return B[k]
    if k==len(A)+len(B)-1:
        return max(A[-1],B[-1])
    i=len(A)//2
    j=k-i
    if A[i]>B[j]:
        #Here I assume it is O(1) to get A[:i] and B[j:]. In python, it's not but in cpp it is.
        return self.findKth(A[:i],B[j:],i) # 如果A[i] > B[j]，那么必然不在B[:j]里，所以裁去B[:j]部分
    else: 
        return self.findKth(A[i:],B[:j],j)

第七题 Validate Binary Search Tree

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1:

    2
   / \
  1   3

    1
   / \
  2   3

解法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):

def func(self, root, start, end):
    if not root:
        return True
    if root.left:
        if root.left.val <= start or root.left.val >= root.val:
            return False
    if root.right:
        if root.right.val >= end or root.right.val <= root.val:
            return False
    tmpEnd = end
    tmpStart = start
    if root.val < end:
        tmpEnd = root.val
    if root.val > start:
        tmpStart = root.val
    return self.func(root.left, start, tmpEnd) and self.func(root.right, tmpStart, end)



def isValidBST(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    return self.func(root, -9999999999999, 999999999999999)

分治和递归

第一题 Unique Binary Search Trees II

解法