这次比赛简单。

第一题Distribute Candies

给定一个长度为偶数的数组，将所有数分成长度一样的两堆，求其中一堆不一样数字最多的数目。
class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        kind = set()
        for c in candies:
            kind.add(c)
        n = len(candies)/2
        if (n<=len(kind)):
            return n
        else:
            return len(kind)

第二题Subtree of Another Tree

给定两颗二叉树s和t，问t是不是s的子树。

首先写个程序判断两颗二叉树是否完全一样，然后遍历s的子树，一一与t比较。

# 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 isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """    
        def check(s, t):
            if (s and not t) or (not s and t):
                return False
            if not s and not t:
                return True
            return s.val==t.val and check(s.right, t.right) and check(s.left, t.left)

        def dfs(s, t):
            if not s:
                return
            if s.val==t.val and check(s, t):
                raise 'Found'
            else:
                dfs(s.right, t)
                dfs(s.left, t)

        try:
            dfs(s, t)
        except:
            return True
        return False

第三题Squirrel Simulation

在一个height x width的网格上有一棵树，一只松鼠和若干坚果（数量不为0）。松鼠每次只能运输一颗坚果，求松鼠将所有坚果运到树下的最短路径长度。

让我用dist(a, b)表示a与b之间的距离。如果松鼠首先收集nuts[i]然后收集其他坚果的最短路径长度pi为


pi = sum(2dist(tree, nuts[j]): all j)-dist(tree, nuts[i])+dist(squirrel, nuts[i])

答案明显是min(pi: all i)。

class Solution(object):
    def minDistance(self, height, width, tree, squirrel, nuts):
        """
        :type height: int
        :type width: int
        :type tree: List[int]
        :type squirrel: List[int]
        :type nuts: List[List[int]]
        :rtype: int
        """
        path = []
        tx, ty = tree
        sx, sy = squirrel
        for x, y in nuts:
            p = abs(tx-x)+abs(ty-y)
            path.append(p)
        s = 2*sum(path)
        ans = 2 ** 31
        for i in xrange(len(nuts)):
            x, y = nuts[i]
            p = abs(sx-x)+abs(sy-y)
            ans = min(ans, s-path[i]+p)
        return ans

第四题Out of Boundary Paths

一个m x n的网格上有个球，位置坐标为(x, y)。我们可以上下左右地移动球。如果我们最多能移动N次，问有多少种方法（模109+7）可以将球移出网格。

动态规划：用dp(k, i, j)表示刚好用k步从(i, j)位置移出网格的数量。那么


dp(k, i, j) = dp(k-1, i-1, j) + dp(k-1, i+1, j) + dp(k-1, i, j-1) + dp(k-1, i, j+1)

边界条件：

对于k＝0，dp(0, i, j) = 1，如果(i, j)不在网格里，否则dp(0, i, j)=0;

对于k>0, dp(k, i, j) = 0，如果(i, j)不在网格里。

从转移方程我们可以看出，k状态只与k-1状态有关，所以我们可以写简单的滚动实现。首先用一个m x n的数组s来表示每个位置第一步能移出网格的数目。这个数组只有边界一圈是非0的，下面的init就是用来算边界移出网格的方法数。然后我们用上述的状态转移方程依次算出走k步的数目。我下面的实现看起来有点不一样，但其实还是等价于上述的状态转移方程的。

class Solution(object):
    def findPaths(self, m, n, N, x, y):
        """
        :type m: int
        :type n: int
        :type N: int
        :type i: int
        :type j: int
        :rtype: int
        """
        def init(x, y):
            ans = 0
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx = x+dx
                ny = y+dy
                if nx<0 or nx>=m or ny<0 or ny>=n:
                    ans += 1
            return ans
        ans = 0
        s = [[0]*n for _ in xrange(m)]
        for i in xrange(n):
            s[0][i] = init(0, i)
            s[m-1][i] = init(m-1, i)
        for i in xrange(m):
            s[i][0] = init(i, 0)
            s[i][n-1] = init(i, n-1)

        for _ in xrange(N):
            ans = (ans+s[x][y]) % (10**9+7)
            t = [[0]*n for _ in xrange(m)]
            for i in xrange(m):
                for j in xrange(n):
                    for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                        ni = i+di
                        nj = j+dj
                        if ni<0 or ni>=m or nj<0 or nj>=n:
                            continue
                        t[ni][nj] = (t[ni][nj]+s[i][j]) % (10**9+7)
            s = t
        return ans
leetcode contest