偶尔冒泡参加 Leetcode 的比赛。这次四题都做出来了，但是第一、三和四题都各自错了一次。排名250左右。

第一题Detect Pattern of Length M Repeated K or More Times

问一个数组里面是否存在长度为 m 的子数组被重复至少 k 次。

因为数据比较小，直接暴力搜索就行。第一次 WA 是因为 n - m * k + 1 写成 n - m * k 了。

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        n = len(arr)
        for i in range(n - m * k + 1):
            t = True
            for s in range(m):
                for t in range(k):
                    if arr[i + s] != arr[i + s + t * m]:
                        t = False
                        break
                if not t:
                    break
            if t:
                return True
        return False

第二题Maximum Length of Subarray With Positive Product

找出一个数组中乘积为正的子数组的最大长度。

我的想法是将正数看作0，负数看作1。假设原来数组中没有0，题目就转化成求和为偶数的最大长度子数组。现在就用原数组中的0将数组分割成若干个分段，每个分段就没有0了。

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = [-1, -2]
        s = c = 0
        ans = 0
        for i, n in enumerate(nums):
            if n == 0:
                pos = [i, -2]
                s = c = 0
            elif n < 0:
                c = (c + 1) % 2

            if c == 1 and pos[1] == -2:
                pos[1] = i
            ans = max(ans, i - pos[c])
        return ans

第三题Minimum Number of Days to Disconnect Island

在一个只有0和1的二维数组中，我们可以每次让一个1变成0。问至少多少次操作之后能将1的区域变成非连通（上下左右相接为连通）。

这题我觉得是最难的。一开始打算二分查找，但是后来想想也许广度搜索就行。因为2维数组的每一行都不多于30位，我就用一个整形来代表一行了。于是有了以下巨丑的代码。第一次 TLE 是检测的时机不对，我一开始是在 cur, s = stack[p] 之后才检测 cur 是否满足条件。后来我就改成了在加入 stack 之前检测 new 就过了。

class Solution:
    def minDays(self, grid: List[List[int]]) -> int:

        def conv(arr):
            ans = 0
            for n in arr:
                ans = 2 * ans + n
            return ans

        init = tuple(conv(arr) for arr in grid)
        n, m = len(grid), len(grid[0])

        def conv_r(v):
            ans = []
            for _ in range(m):
                ans.append(v & 1)
                v //= 2
            return ans

        def floodfill(grid, i, j):
            for x, y in [(i+1, j), (i-1,j), (i, j+1), (i, j-1)]:
                if x < 0 or y < 0 or x >= n or y >= m or grid[x][y] == 0:
                    continue
                grid[x][y] = 0
                floodfill(grid, x, y)

        def count(arr):
            grid = [conv_r(v) for v in arr]
            ans = 0
            for i in range(n):
                for j in range(m):
                    if grid[i][j] == 1:
                        ans += 1
                        if ans > 1:
                            return ans
                        grid[i][j] = 0
                        floodfill(grid, i, j)
            return ans

        if count(init) != 1:
            return 0
        p = 0
        stack = [(init, 0)]
        visited = {init}
        while p < len(stack):
            cur, s = stack[p]

            for i in range(n):
                for j in range(m):
                    if (cur[i] >> j) & 1:
                        v = cur[i] ^ (1 << j)
                        new = cur[:i] + (v, ) + cur[i+1:]
                        if new not in visited:
                            if count(new) != 1:
                                return s + 1
                            visited.add(new)
                            stack.append((new, s+1))
            p += 1
        return -1

第四题Number of Ways to Reorder Array to Get Same BST

给定一个从1到n的排列，问有多少种其他排列跟这个排列构成的二分查找树是一样的。

排列组合的题目。第一次提交 WA 是因为我错误地计算了 C(a, b)。我一开始为了中间过程不会出现超级大的数就提前 mod M 了（注意看 C(a, b) 我注释掉的错误代码）。问题出在计算 C(a, b) 有除法，所以不能在中间过程中 mod M。如果不想出现超级大的数，那么我们要用 mod M 将除法变成乘法。或者用杨辉三角来算。

想法就是将数组中第一个数后面的数分成比第一个数大和小的两个数组。小的一定是左子树，大的是右子树。然后递归算出他们的方法

class Solution:
    def numOfWays(self, nums: List[int]) -> int:

        M = 10 ** 9 + 7

        def C(a, b):
            ans = 1
            for k in range(1, b + 1):
                ans *= (a - k + 1)
                ans //= k
                #ans %= M
            return ans % M

        def f(nums):
            n = len(nums)
            if n <= 2:
                return 1

            smaller = [v for v in nums[1: ] if v < nums[0]]
            bigger = [v for v in nums[1: ] if v > nums[0]]

            left = f(smaller)
            right = f(bigger)

            return left * right * C(len(smaller) + len(bigger), len(smaller)) % M

        return f(nums) - 1
leetcode contest