周赛笔记254

一、作为子字符串出现在单词中的字符串数目

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        return sum([1 for p in patterns if p in word])

二、构造元素不等于两相邻元素平均值的数组

1. 数组

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()

        l, r = nums[n//2:],nums[:n//2]

        ans = []
        for i in range(len(r)):
            ans.append(l[i])
            ans.append(r[i])

        if n%2:
            ans.append(l[-1])

        return ans

三、数组元素的最小非零乘积

1. 数学

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        n = 2**p
        m = (n-1)//2
        mod = 10**9 +7
        return pow(n-2,m,mod)*(n-1)%mod

# 麻掉了，数学根本不会

四、你能穿过矩阵的最后一天

1. DFS，超时

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        n = len(cells)
        grid = [[0]*col for _ in range(row)]

        def check():
            def dfs(i,j):
                if j == col-1: 
                    return True
                for x,y in [(i,j+1),(i-1,j+1),(i+1,j+1),(i-1,j),(i+1,j),(i-1,j-1),(i+1,j-1),(i-1,j-1)]:
                    if 0<=x<row and 0<=y<col and grid[x][y]==1 and (x,y) not in vis:
                        vis.add((i,j))
                        if dfs(x,y):
                            return True
                return False

            for i in range(row):
                if grid[i][0]==1:
                    vis = set()
                    if dfs(i,0):
                        return True
            return False

        for day in range(1, n+1):
            grid[cells[day-1][0]-1][cells[day-1][1]-1] = 1
            #print(day,check(),grid)
            if check():
                return day-1

#麻掉了，知道这种连通性问题用DFS会超时，还写DFS
#主要是并查集不熟...

2. 并查集 + 倒序

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        f = {}
        def find(x):
            f.setdefault(x,x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x,y):
            f[find(x)] = find(y)

        n = row*col
        grid = [[0]*col for _ in range(row)]
        ans = 0
        for d in range(n-1,-1,-1):
            i, j = cells[d][0]-1, cells[d][1]-1
            grid[i][j] = 1
            idx1 = i*col + j
            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if 0<=x<row and 0<=y<col and grid[x][y]:
                    idx2 = x*col + y
                    union(idx1, idx2)
            if i == 0:
                union(idx1, n)
            if i == row-1:
                union(idx1, n+1)
            if find(n) == find(n+1):
                ans = d
                break
        return ans

更多并查集，参考：
每日一题（1月）（并查集）
1631.最小体力消耗路径

3. 二分 + BFS

# 对天数进行二分查找
class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        l, r = 0, row*col
        day = 0
        while l <= r:
            mid = (l+r)//2
            grid = [[1]*col for _ in range(row)]
            for x,y in cells[:mid]:
                grid[x-1][y-1] = 0

            q = deque()
            for i in range(col):
                if grid[0][i] == 1:
                    q.append((0,i))
                    grid[0][i] = 0

            found = False
            while q:
                i,j = q.popleft()
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0<=x<row and 0<=y<col and grid[x][y]:
                        if x == row-1:
                            found = True
                            break
                        q.append((x,y))
                        grid[x][y] = 0
            if found:
                day = mid
                l = mid + 1
            else:
                r = mid - 1
        return day