忏悔

今天因台风停课通知冲击大脑, 懈怠了, 我有罪

热题 100 题

岛屿数量

入门dfs, bfs, 太久没写了, 康复训练

# 丑陋的一版 dfs
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        g = [(1, 0), (-1, 0), (0, -1), (0, 1)] # 方便遍历移动可能
        ans = 0

        def dfs(x, y):
            # 终止条件
            if grid[x][y] == '0':
                return
            else:
                # 防止重复遍历, 把走过的点设为 '0'
                grid[x][y] = '0'
                # 遍历四个方位
                for x_nxt, y_nxt in g:
                    x1, y1 = x + x_nxt, y + y_nxt
				  # 防止越界
                    if 0 <= x1 < len(grid) and 0 <= y1 < len(grid[0]):
                        dfs(x1, y1)

        # 遍历
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if grid[x][y] == '1':
                    dfs(x, y)
                    ans += 1

        return ans

# 稍微改进一下逻辑和代码简洁度
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        g = [(1, 0), (-1, 0), (0, -1), (0, 1)]
        n, m = len(grid), len(grid[0])
        ans = 0

        def dfs(i, j):
            grid[i][j] = '0'

            for dx, dy in g:
                x, y = i + dx, j + dy
                # 有个两个非常简单的判断 x 小于 n 还是 m, 一是看的遍历时候的边界, 二是看[x][y], 还是[y][x]
                if 0 <= x < n and 0 <= y < m and grid[x][y] == '1':
                    dfs(x, y)
    
        # 是的就是这里
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    ans += 1
                    dfs(i, j)   

        return ans
  
# bfs 版本
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        ans = 0
        q = deque()

        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    ans += 1
                    # 标记为已访问
                    grid[i][j] = '0'
                    q.append((i, j))

                    while q:
                        x, y = q.popleft()
                        for dx, dy in d:
                            x1, y1 = x + dx, y + dy

                            if 0 <= x1 < n and 0 <= y1 < m and grid[x1][y1] == '1':
                                # 因为还在循环找下一层, 我们得入队就设置为 0, 防止多次入队
                                grid[x1][y1] = '0'
                                q.append((x1, y1))

        return ans

腐烂橘子

非常非常经典的多源bfs计数, 同样类似的还有岛屿着火等等, 我给出我的两种写法, 一种按照bfs层数计数, 一种使用带有时间戳的队列计数

# 记录循环层写法
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        n, m = len(grid), len(grid[0])
        cur = time = 0
        q = deque()
    
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    cur += 1
                elif grid[i][j] == 2:
                    q.append((i, j))
    
        if cur == 0:
            return 0
		# 避免没有新鲜橘子时队列没有空导致结果多 1, bfs前序检验现在的新鲜橘子数量
        while q and cur:
            size = len(q) # 不会随着当前 q 的改变而改变
            for _ in range(size):
                x, y = q.popleft()
                for dx, dy in d:
                    nx, ny = x + dx, y + dy

                    if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        cur -= 1
                        q.append((nx, ny))
        
            time += 1
    
        return -1 if cur else time
# 时间戳写法
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        n, m = len(grid), len(grid[0])
        cur = time = 0
        q = deque()
    
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    cur += 1
                elif grid[i][j] == 2:
                    q.append((i, j, 0)) # 引入一个腐烂时间戳
    
        if cur == 0:
            return 0
                
        while q and cur:
            x, y, t = q.popleft()
        
            for dx, dy in d:
                nx, ny = x + dx, y + dy

                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    cur -= 1
                    q.append((nx, ny, t + 1))
                    time = t + 1
    
        return -1 if cur else time

课程表

初看就是一个图内成环问题, 使用了并查集, 然后发现不对, 这是个拓扑排序, 需要判断的是有没有形成循环(贪吃蛇), 并不是单纯的成环就false

# 初版(错误的版本!!!)
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 课程从 0 开始, 非常友好
        fa = [i for i in range(numCourses)]
		# 路径压缩的查找
        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])

            return fa[x]

        # 其实这里可以做一个小树合到大树的优化, 但是这题数据量不大, 就没必要了
        def union(u, v):
            if find(u) != find(v):
                fa[find(u)] = find(v)
                return True

            return False
  
        for u, v in prerequisites:
            if not union(u, v):
                return False
  
        return True
# 三色标记法dfs
# 0 代表尚未学习. 1 代表学习中(递归栈), 2 代表学习完了
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if not prerequisites:
            return True

        grid = [[] for _ in range(numCourses)]

        for u, v in prerequisites:
            grid[v].append(u)
		# 刚开始都没有学习
        check = [0] * numCourses

        def dfs(cur):
            # 递归到了学习中的课程, 也就成环了(还没学完就被拉去当前置条件)
            if check[cur] == 1:
                return False
            # 已经学习完了, 可以跳出递归
            if check[cur] == 2:
                return True
            # 标记当前学习着的课程
            check[cur] = 1
            for v in grid[cur]:
                # 前置课程无法正常学完, 遗憾败北
                if not dfs(v):
                    return False
            # 递归结束, 学完了前置课程, 也就可以学完当前课程了
            check[cur] = 2
            return True

        for i in range(numCourses):
            if not dfs(i):
                return False

        return True
  
# 入度角度的 bfs
# 我们可以这样思考, 从入度为 0 的节点开始往后删除, 连带着边一起删除, 就像一层一层的往里推进, 如果存在循环, 循环圈永远不可能入度为 0, 不会被删除, 所以我们只要比较删除的节点数和总课程数是否相等就好
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        grid = [[] for _ in range(numCourses)]
        cnt = [0] * numCourses
        # v是前置课程, 也就是 v -> u, 正向建图
        for u, v in prerequisites:
            grid[v].append(u)
            cnt[u] += 1
  
        # 把第一层的节点放入初始化队列
        q = deque([i for i in range(numCourses) if cnt[i] == 0])
        ans = 0 # 删除的节点数

        while q:
            u = q.popleft()
            ans += 1
            # 删除掉所有出边
            for v in grid[u]:
                cnt[v] -= 1
                # 出现新的 0 入度节点, 火速加入生死簿
                if cnt[v] == 0:
                    q.append(v)
  
        return ans == numCourses
# 还有出度角度的逆向做法，只是建图反着建就好, 其他没有太大区别

贴一张图(学艺不精, 不会做动图), 如果没有环就会一层一层删除掉所有节点

468 周赛

第一题.偶数的按位或运算

数据量很小, 直接线性遍历就好(时间O(n), 空间O(1))

class Solution:
    def evenNumberBitwiseORs(self, nums: List[int]) -> int:
        ans = 0
        for i in nums:
            if i % 2 == 0:
                ans |= i
  
        return ans 

第二题.最大字数组总值(一)

难以理解这玩意为什么示例这么抽象, 题目明确

同一个子数组（相同的 l 和 r）可以 被选择超过一次。

直接 最大最小的差 * k 就好了, 难点(竟然是中等题)在于示例吓唬人?

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        return k * (max(nums) - min(nums))