这次比赛不难，但是我在最简单的两题各错了一次。

第一题Flood Fill

给定一个二维数组表示一张图片，以及一个坐标(r, c)。我们需要包含这个坐标且数字一样的连通分支整体变成另一个数。

我记得高中的时候学到Flood Fill这个词的时候有种莫名开心，可能是因为这个名字很形象地描述了DFS的过程吧。

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        visited = set()
        n = len(image)
        m = len(image[0])
        color = image[sr][sc]

        def dfs(r, c):
            image[r][c] = newColor
            visited.add((r, c))
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                x, y = r+dr, c+dc
                if x < 0 or y < 0 or x >= n or y >= m or image[x][y] != color:
                    continue
                if (x, y) in visited:
                    continue
                dfs(x, y)

        dfs(sr, sc)
        return image

第二题Sentence Similarity

给定两个列表代表两句话，以及一些词语的相似关系。如果两个句子对应的词是相似的，那么我们说这两个句子相似。问给定的两个句子是否相似。

首先建立一个哈希表建立词语间的相似关系，然后遍历两个句子中的每个词语进行判断即可。

class Solution(object):
    def areSentencesSimilar(self, words1, words2, pairs):
        """
        :type words1: List[str]
        :type words2: List[str]
        :type pairs: List[List[str]]
        :rtype: bool
        """
        if len(words1) != len(words2):
            return False
        m = {}
        for a, b in pairs:
            if a not in m:
                m[a] = set([a])
            m[a].add(b)
            if b not in m:
                m[b] = set([b])
            m[b].add(a)
        for a, b in zip(words1, words2):
            if a not in m:
                if a != b:
                    return False
            else:
                if b not in m[a]:
                    return False
        return True

第三题Remove Comments

给定一个非零数组，正数表示该数往右运动，负数表示往左运动。如果两个数相遇，那么绝对值大的数留下来，如果两个数的绝对值一样，则两个数都消失。求消除后的数组。

我们可以依次处理每个数，并以ans表示当前消除后的数组。如果ans是空的，或者这个数是正的，又或者ans最后一个数是与当前的数都是负的（都往左运动），那么这个数不会跟ans的数相遇，所以直接加进ans即可。因此，产生碰撞时当前的数必然是负的。这意味着处理碰撞时只会涉及位于ans最后位置的正数。详细算法参考如下代码。

class Solution(object):
    def asteroidCollision(self, asteroids):
        """
        :type asteroids: List[int]
        :rtype: List[int]
        """
        ans = []
        for a in asteroids:
            if not ans or a > 0 or ans[-1]*a > 0:
                ans.append(a)
                continue
            while ans and ans[-1] > 0 and ans[-1]+a < 0:
                ans.pop()
            if not ans or ans[-1] < 0:
                ans.append(a)
                continue
            if ans[-1]+a == 0:
                ans.pop()
        return ans

第四题Parse Lisp Expression

给定一个Lisp表达式，返回执行后的值。这个表达式只含let, add和mult运算。

比较麻烦的题，我觉得难点在于局部变量以及全局变量的处理。我简单介绍一下下面代码中的三个关键函数：split, get和lisp。

split是将表达式ex分成若干块，每一块都是合法的子表达式。

get首先假设输入参数v是一个变量，直接尝试转化成整数或者从局部变量集合ls或者全局变量gs中获得。如果上述方法无法获得v的值，说明v是一个表达式而不是变量，所以对v调用lisp函数。

lisp的输入参数ex表示一个表达式，gs表示全局变量列表。首先调用split函数将ex分解，然后按照let, add和mult分类讨论。

class Solution(object):
    def evaluate(self, expression):
        """
        :type expression: str
        :rtype: int
        """
        def split(ex):
            el = []
            cur = ''
            p = 0
            s = 5
            if ex.startswith('(mult'):
                s = 6
            for ch in ex[s:-1]:
                if ch == '(':
                    p += 1
                elif ch == ')':
                    p -= 1
                elif ch == ' ':
                    if p == 0:
                        el.append(cur)
                        cur = ''
                        continue
                cur += ch
            el.append(cur)
            return el

        def get(v, ls, gs):
            try:
                return int(v)
            except:
                if v in ls:
                    return ls[v]
                for g in gs[::-1]:
                    if v in g:
                        return g[v]
            gs.append(ls)
            ans = lisp(v, gs)
            gs.pop()
            return ans

        def lisp(ex, gs):
            ls = {}
            el = split(ex)

            if ex.startswith('(let'):
                for i in range(0, len(el)-1, 2):
                    ls[el[i]] = get(el[i+1], ls, gs)
                return get(el[-1], ls, gs)
            else: 
                first = get(el[0], ls, gs)
                second = get(el[1], ls, gs)
                if ex.startswith('(add'):
                    return first+second
                else:
                    return first*second

        return lisp(expression, [])
leetcode contest