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

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


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]


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


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)