这次比赛跪了。。

第一题Repeated String Match

给定字符串A和B，问至少要重复多少次A使得B是A的子字符串。

二分查找。首先算出最少需要多少次才有可能使得B是子字符串：必须要保证重复后的A的长度不小于B的长度。我们可以简单算出最少需要重复：

i = (len(A) + len(B) - 1) / len(A)

最大次数j的上界是2i。然后对[i, j]这个区间进行二分查找。

这题竟然WA了2次(因为typo)，TLE一次(一开始用j＝10i)。。。

class Solution(object):
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        i = (len(A) + len(B) - 1) / len(A)
        j = 2 * i
        ans = -1
        while i <= j:
            k = (i+j) / 2
            tmp = A * k
            if tmp.find(B) != -1:
                ans = k
                j = k - 1
            else:
                i = k + 1
        return ans

空间上有很大的优化：我们可以自己写一个函数判断B是不是A重复k次后的子字符串。

第二题Longest Univalue Path

给入一棵二叉树，找出所有值一样的路径中的最长路径长度。

DFS。一开始重复计算导致TLE了。

# 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 longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = [0]
        def dfs(root):
            if not root:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            ml = 1
            if l > 0 and root.left.val == root.val:
                ml += l
            mr = 1
            if r > 0 and root.right.val == root.val:
                mr += r
            ans[0] = max(ans[0], ml+mr-2)
            return max(ml, mr)
        dfs(root)
        return ans[0]

第三题Knight Probability in Chessboard

现在有块N x N的格板，求骑士在初始位置(r, c)连续跳k步仍然留着板上的概率。假设骑士往8个方向跳的概率都一样。

比赛的时候没有做出来。但是其实是简单的计数问题。按照乘法原理，k步之后仍然留在板上的概率是每步之后都留在板上的概率之积。

class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        b = [[[-1, 0] for _ in range(N)] for _ in range(N)]
        b[r][c] = [0, 1]
        ans = 1.0
        for i in range(K):
            ic = oc = 0
            tb = [[[-1, 0] for _ in range(N)] for _ in range(N)]
            for r in range(N):
                for c in range(N):
                    if b[r][c][0] != i:
                        continue
                    for dr in (-1, -2, 1, 2):
                        for dc in (-1, -2, 1, 2):
                            if abs(dr) == abs(dc):
                                continue
                            nr, nc = r+dr, c+dc
                            if nr < 0 or nc < 0 or nr >= N or nc >= N:
                                oc += b[r][c][1]
                                continue
                            ic += b[r][c][1]
                            tb[nr][nc][0] = i+1
                            tb[nr][nc][1] += b[r][c][1]
            if ic == 0:
                return 0
            ans *= (float(ic) / float(ic + oc))
            b = tb
        return ans

第四题Maximum Sum of 3 Non-Overlapping Subarrays

给定一个正整数数组nums，找出三个互不重叠长度为k的子区间，使得它们之和最大。返回一个三元组，表示三个子区间的起始位置。

这是我这次比赛唯一一道直接AC的题目。不过代码写得不是很让我满意。我的想法是这样：进行三轮操作。第一轮操作算出以每个位置开始长度为k的子区间之和（第－个子区间的和）。第二轮操作对第一轮的结果进一步处理，算出以第i个区间为第二个子区间的最大和并记录区间的起始位置。第二轮操作结束后，我们得到了选择两个长度为k的区间的最优结果。第三轮操作跟第二轮操作类似，这次是找第三个子区间。三轮操作结束后再枚举一下所有可能的结果找出最大值就好。每轮的操作都是O(n)的。

每轮操作注意起始位置的选择范围。假设n是nums的长度。第一轮操作中，起始位置的选择范围是[0, n-k]。第二轮选择的时候，因为我们要保证选择的区间前面还有一个区间，所以起始位置的选择范围是[k, n-k]。类似地，第三轮起始位置的选择范围是[2k, n-k]。

最后说一下如何解决选择的区间不重复的问题（第二第三轮操作才有的问题）。以第二轮操作为例。我们保存对第i个区间（从位置i开始）可以选择的最优区间。在处理下一个区间（从位置i＋1开始），那么让保存的最优区间与第i＋1－k个区间（从位置i＋1－k开始）比较，两者取最优者。这样我们得到的是对第i＋1个区间可以选择的最优区间。这样我们就可以在保证不重复的同时能在O(n)完成每轮操作。

class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        n = len(nums)
        p = [0] * (n+1)
        p[0] = nums[0]
        for i in xrange(1, n):
            p[i] = p[i-1] + nums[i]

        # round 1
        m = n-k+1
        s = [0] * n
        for i in range(m):
            s[i] = p[i+k-1] - p[i-1]

        # round 2
        f = [None] * n
        cm = ci = 0
        for i in xrange(k, m):
            if s[i-k] > cm:
                cm, ci = s[i-k], i-k
            f[i] = (s[i]+cm, ci, i)

        # round 3
        g = [None] * n
        cm = ci = cj = 0
        for i in xrange(2*k, m):
            if f[i-k][0] > cm:
                cm, ci, cj = f[i-k]
            g[i] = (s[i]+cm, ci, cj, i)

        # find answer
        ans = None
        cm = 0
        for x in g:
            if x is None or x[0] <= cm:
                continue
            cm = x[0]
            ans = x[1:]
        return ans
leetcode contest