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]


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


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

(2nums[i]-1)+(2nums[i+1]-1)+...+(2nums[i+l-1]-1) = 0

s[i+l-1] - s[i-1] = 0 或者说是 s[i+1-l] = s[i-1]

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


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

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