454. 4Sum II： 每两组创建一个hash，key是和，value是这个和的值出现的次数。
456. 132 Pattern： 大概的思路比上次做的一头雾水要清晰了，不过还是没有做出来
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(set(nums)) < 3:
return False
stack = []
for n in nums:
if not stack or n < stack[-1][0]:
stack.append([n, n]) # 保持stack 中的每一段都是以其第一个值单调递减的, 所以当前的值[0]是全栈的最小值，以后要检查的就是是否有一个元素落在了 [0] .. [1] 之间
elif n > stack[-1][0]: # 此时 n 大于 stack top的最小值
last = stack.pop()
if n < last[1]: # 如果 n 同时小于 stack top的最大值，那么返回True
return True
else:
last[1] = n # 否则的话，把stack top的最大值更新为n， 注意此时stack top的最小值，是全部stack元素的最小值
# last形成了一个新的range，pop出所有被新range包含的旧的range
while stack and n >= stack[-1][1]: # 如果 n 比stack 栈顶元素的最大值还要大，那么说明当前的range包含于pop出来的元素的range， 所以pop栈顶
stack.pop()
if stack and stack[-1][0] < n: # 此时的情况是如果栈顶最小值比n小，同时栈顶的最大值比n大
return True
stack.append(last)
print stack
return False
462. Minimum Moves to Equal Array Elements II: 找median，然后每个值到median的距离。需要数学解释
464. Can I Win: 这种题我一向弱得很，哎。。。看来有必要上一期dp的班？
class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
return False
self.memo = {}
return self.helper(range(1, maxChoosableInteger + 1), desiredTotal)
def helper(self, nums, desiredTotal):
hash = str(nums) # 记录当前状态
if hash in self.memo:
return self.memo[hash]
if nums[-1] >= desiredTotal:
return True
for i in range(len(nums)):
if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
# 如果下一个人不能赢，也就是对于所有的状况都不能赢，那么记录当前hash值，并且记录
self.memo[hash]= True # current state for player one
return True
self.memo[hash] = False
return False
467. Unique Substrings in Wraparound String: 这题看着挺简单，实际还是有点麻烦。而且最终是个DP问题，真是万万没想到。
class Solution(object):
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
N = len(p)
if N <= 1: return N
dp = [0 for i in range(N)]
start, seen = 0, {}
dp[0], seen[p[0]] = 1, 1
for i in range(1, N):
if p[i - 1] == 'z' and p[i] == 'a' or ord(p[i - 1]) + 1 == ord(p[i]): # 如果当前值和前一个值连续
x = i - start + 1 # 计算当前的长度
if p[i] not in seen: # 如果当前值没有被访问过
dp[i] = x # dp[i] = 当前的长度， 为什么存储长度呢，比如说 abcd，如果ending with d，就有abcd, bcd, cd, d四个值，正好是其字符串长度
seen[p[i]] = dp[i] # 并且把前长度加入dict
else:
if x > seen[p[i]]: # 如果当前值已被访问过，而且当前的长度比上一次存储的长度还要大
dp[i] = x - seen[p[i]] # 那么只需要存储差值
seen[p[i]] = x # 并且更新当前长度
else:
dp[i] = 0 # 否则存储0，就是当前的状态已经存储好了
else:
if p[i] not in seen: # 如果不连续而且没访问过，那么存储1
dp[i] = 1
seen[p[i]] = dp[i]
else:
dp[i] = 0 # 如果不连续而且访问过 那么存储0
# 如果不连续，那么就更新当前的起始值
start = i
return sum(dp)
468. Validate IP Address: 这道题倒是简单的，把情况考虑齐全一点就好了。
469. Convex Polygon: 计算几何，完全没思路啊。tag还是Google，Google要是考这种题就直接跪了啊。下面答案的思路，a，b是两条边：if tmp == 0, a -> b 180° on the same line; elif tmp > 0, a -> b clockwise; else tmp < 0, a -> anticlockwise;
class Solution(object):
def isConvex(self, points):
"""
:type points: List[List[int]]
:rtype: bool
"""
last, tmp = 0, 0
for i in xrange(2, len(points) + 3):
p0, p1, p2 = points[(i - 2) % len(points)], points[(i - 1) % len(points)], points[i % len(points)]
tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1])
if tmp:
if last * tmp < 0:
return False
last = tmp
return True
473. Matchsticks to Square: backtracking的题目，可以考虑memcache来优化。
474. Ones and Zeroes: 这是个背包问题，手写一下。没写出来。。。。实在是。。。
477. Total Hamming Distance: 32位的数字每一位有多少个1多少个0，乘一下求和就可以了。
