这周六的菜单是牛排骨、金鲳鱼和土豆丝，甜点是蛋糕。

这次比赛有四题，我只做出来了前三道。

第一道是简单的字符串处理。

class Solution(object):
    def detectCapitalUse(self, word):
        """
        :type word: str
        :rtype: bool
        """
        if all('A' <= c <= 'Z' for c in word):
            return True
        if all('a' <= c <= 'z' for c in word):
            return True
        return 'A' <= word[0] <= 'Z' and all('a' <= c <= 'z' for c in word[1:])

第二道直接深度优先搜索就是。

class Solution(object):
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        def dfs(i, used, ans):
            if i == N + 1:
                ans[0] += 1
            else:
                for j in xrange(1, N+1):
                    if not used[j] and (i % j == 0 or j % i == 0):
                        used[j] = True
                        dfs(i+1, used, ans)
                        used[j] = False
        ans = [0]
        dfs(1, [False] * (N+1), ans)
        return ans[0]

第三道我挂了三次才成功的。一开始以为可以用binary search：答案最小可能值是0，最大可能值是2*[len(num)/2]，我就对这个区间二分查找。但是后来发现这个算法是不对的，反例如下：

nums = [1, 1, 0, 0, 0, 0, 1, 1]

这测试数据应该要返回8，但明显不存在长度为6的连续子数组使得0和1的个数一样。所以这个问题并不符合二分查找的条件。

给定nums，其实我们要找最大的l，使得存在一个i，我们有

nums[i]+nums[i+1]+...+nums[i+l-1] = l/2

做一个简单的运算，上述等式就变成
(2nums[i]-1)+(2nums[i+1]-1)+...+(2nums[i+l-1]-1) = 0

如果我们将nums的所有数都做了一个n -> 2n-1的变换，并且将变换后的数组求出其前缀和放在数组s里，那么上述等式等价于
s[i+l-1] - s[i-1] = 0 或者说是 s[i+1-l] = s[i-1]

所以我们可以初始化ans = 0，然后从小到大遍历所有i，找出最大的j使得s[j] = s[i-1]，然后更新ans = max(ans, j-i+1)。为了快速查找这样的j，我们用一个哈希表d来记录某个和出现的最右位置。算法详细实现如下。

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = [0]
        for n in nums:
            s.append(s[-1]+2*n-1)
        d = {}
        for i, n in enumerate(s):
            d[n] = i
        ans = 0
        for i in xrange(1, len(s)):
            j = d.get(s[i-1], -1)
            ans = max(ans, j - i + 1)
        return ans

第四题比赛的时候没有写出来。看了别人的代码发现算法其实很简单：假设最后每个洗衣机的平均值为k，对于洗衣机i，如果

machines[0]+...+machines[i] >= k(i + 1)

那么说明需要从第i个位置向右移动machines[0]+...+machines[i]-k(i + 1)单位的衣服，反之则是说明需要从第i+1个位置向左移动k(i + 1)-(machines[0]+...+machines[i])单位的衣服。最后答案就是每个位置向左向右移动之和的最大值。

class Solution(object):
    def findMinMoves(self, machines):
        """
        :type machines: List[int]
        :rtype: int
        """
        s = machines[:]
        for i in xrange(1, len(s)):
            s[i] += s[i-1]
        if s[-1] % len(s) != 0:
            return -1
        k = s[-1] / len(s)
        to_left = [0] * len(s)
        to_right = [0] * len(s)
        for i in xrange(len(s)):
            if s[i] >= k*(i+1):
                to_right[i] = s[i] - k*(i+1)
            else:
                to_left[i+1] = k*(i+1) - s[i]
        return max(a+b for a, b in zip(to_left, to_right))

我们可以降低空间的使用：

class Solution(object):
    def findMinMoves(self, machines):
        """
        :type machines: List[int]
        :rtype: int
        """
        s, l = sum(machines), len(machines)
        if s % l != 0:
            return -1
        k, c = s / l, 0
        to_left = ans = 0
        for i, n in enumerate(machines):
            n += c
            if n >= k:
                ans = max(n-k+to_left, ans)
                to_left = 0
            else:
                ans = max(to_left, ans)
                to_left = k - n
            c = n - k
        return ans
contest leetcode