这次比赛做得还算可以，只是最后一题看错题目WA了3次😭

第一题Baseball Game

给定一串字符串，每个字符串有四种可能：

  1. 整数：代表本轮得分
  2. "+"：本轮得分为上两轮得分之和
  3. "D"：本轮得分为上轮得分的两倍
  4. "C"：上轮得分无效。

问最终得分之和。

class Solution(object):
    def calPoints(self, ops):
        """
        :type ops: List[str]
        :rtype: int
        """
        points = []
        for op in ops:
            if op == 'C':
                points.pop()
            elif op == 'D':
                points.append(points[-1]*2)
            elif op == '+':
                points.append(points[-1]+points[-2])
            else:
                points.append(int(op))
        return sum(points)

第二题Next Closest Time

输入格式为"HH:MM"的时间，用这个时间的数字构造该时间之后最近的时间。

最简单的想法就行：获取时间的所有数字，构造所有可能的时间，然后按照跟初始时间的距离排序，最后返回第一个就行。下面的代码是赛后经过大幅度修改的，所以看起来比较简洁。比赛的时候我可是用了4重for循环。

class Solution(object):
    def nextClosestTime(self, time):
        """
        :type time: str
        :rtype: str
        """
        timestamp = int(time[:2]) * 60 + int(time[-2:])
        digits = map(int, list(time.replace(':', '')))
        candidate = set()
        for i, j, k, l in itertools.product(digits, repeat=4):
            if 10*i+j < 24 and 10*k+l < 60:
                time_diff = 600*i+60*j+10*k+l
                time_diff -= timestamp
                if time_diff <= 0:
                    time_diff += 24*60
                candidate.add((time_diff, '{}{}:{}{}'.format(i, j, k, l)))

        return sorted(candidate)[0][1]

第三题Redundant Connection

用二维数组输入一棵节点都不一样的树，每对数对[u, v]表示v是u的子节点。现在的问题是输入的数据得到的并不是一颗树，但可以通过删除一个数对使得剩下的数对构成一棵树。要求找出这个数对，如果有多个可能性，找出在输入数组中最后出现那个。

并查集：对于当前输入[u, v]，找出u的父亲fu，v的父亲fv，如果fu与fv一样，那么添加[u, v]必然出现一个圈。

class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        f = [-1] * 2001
        def father(i):
            if f[i] == -1:
                return i
            f[i] = father(f[i])
            return f[i]
        for u, v in edges:
            fu = father(u)
            fv = father(v)
            if fu == fv:
                return [u, v]
            f[fv] = fu

第四题K Empty Slots

现在有N个花盆排成一列，以1到N编号。给定一个flowers数组（下标从1开始），其中flowers[i]表示第i天的时候flowers[i]编号的花开放。现在给定k，求出最小的d，使得第d天的时候存在两朵已经开放的花，他们之间有k朵花而且这k朵花都没有开。如果这样的d不存在，在返回-1。

我对flowers数组的解读出错了，导致错了3次！这题想法不难。如果将这N盆花看作一个数组a，0代表没有开，1代表已经开，那么第d天flowers[d]开放是在说第i天的时候a[flowers[d]]的值从0变成1了。假设x=flowers[d]。第d天的时候a[d]变成了1，只要考虑x+d+1以及x-d-1是否与x处的花满足条件就行，因为只有这两处的花与x处的花相隔k朵花。要检验两朵花x和y之间的花都没有开，实际上等价于检验

a[x+1]+...+a[y-1]=0

现在的问题是如何快速查询动态的区间和。明显，Binary Indexed Tree是最好的选择。

class Solution(object):
    def kEmptySlots(self, flowers, k):
        """
        :type flowers: List[int]
        :type k: int
        :rtype: int
        """
        n = len(flowers)
        bit = [0] * (n+1)
        def update(i):
            while i <= n:
                bit[i] += 1
                i += (i & -i)

        def query(i):
            ans = 0
            while i > 0:
                ans += bit[i]
                i -= (i & -i)
            return ans

        bloomed = set()
        for d, x in enumerate(flowers):
            update(x)
            if x+k+1 in bloomed and query(x+k+1)==query(x)+1:
                return d+1
            if x-k-1 in bloomed and query(x)==query(x-k-1)+1:
                return d+1
            bloomed.add(x)
        return -1
leetcode contest