Leetcode Contest 21
今晚是一次丰盛的聚餐：羊肉汤，金鲳鱼，红烧排骨，炒牛肉和炒青菜。
这次比赛我全都做出来了！可惜前三题都WA了一次，而且都是粗心大意的错。
第一题Minimum Absolute Difference in BST，我采取了简单粗暴的方法：首先中序遍历将所有数放在一个数组里，然后返回相邻两个数之间差的最小值。
# 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 getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return min(ans[i+1]-ans[i] for i in xrange(len(ans)-1))
第二题Continuous Subarray Sum。思路是这样的：首先计算nums的前缀和s，那么我们要找的是一对(i, j)，使得
我们在计算前缀和的时候应该同时mod k，这样上述的条件的第一部分就变成：s[i] == s[j]。剩下的就交给哈希表吧～对了，因为mod k的时候k不能是0，所以对k＝0的情况要单独考虑。
class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if k == 0:
for i in xrange(len(nums)-1):
if nums[i] == nums[i+1] == 0:
return True
else:
s = [0]
for n in nums:
s.append((s[-1]+n)%k)
d = {}
for i, n in enumerate(s):
j = d.get(n, i)
if j != i:
if i - j >= 2:
return True
else:
d[n] = i
return False
第三题Longest Word in Dictionary through Deleting。直接暴力搞就是：首先找出所有可能通过删除操作得到的字符串（那些可能的w，必然是s的一个子串），然后找出最优解。
class Solution(object):
def findLongestWord(self, s, d):
"""
:type s: str
:type d: List[str]
:rtype: str
"""
def check(w):
i = j = 0
while j < len(s):
while j < len(s) and w[i] != s[j]:
j += 1
if j < len(s):
i += 1
if i == len(w):
return True
j += 1
return False
t = filter(check, d)
ans = ''
for w in t:
if len(w) > len(ans) or (len(w) == len(ans) and w < ans):
ans = w
return ans
第四题Minesweeper是一道模拟题。我是用BFS写的。
class Solution(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
ans = []
for b in board:
ans.append(b[:])
n = len(ans)
if n == 0:
return ans
m = len(ans[0])
a, b = click
if ans[a][b] == 'M':
ans[a][b] = 'X'
return ans
d = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
queue = [(a, b)]
visited = set(queue)
i = 0
while i < len(queue):
a, b = queue[i]
c = 0
tmp = []
for da, db in d:
x, y = a+da, b+db
if x < 0 or y < 0 or x >= n or y >= m:
continue
if ans[x][y] == 'M' or ans[x][y] == 'X':
c += 1
if ans[x][y] == 'E' and (x, y) not in visited:
tmp.append((x, y))
ans[a][b] = str(c) if c != 0 else 'B'
if c == 0:
for x, y in tmp:
visited.add((x, y))
queue.append((x, y))
i += 1
return ans
