今晚是一次丰盛的聚餐:羊肉汤,金鲳鱼,红烧排骨,炒牛肉和炒青菜。

这次比赛我全都做出来了!可惜前三题都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),使得

(s[j] - s[i]) % k == 0 and j - i >= 2

我们在计算前缀和的时候应该同时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