前言

使用语言 Python, 只针对 LC Medium 和 Hard 题, 面向面试刷题
Note: 除非你面前端 (加上 JS) , 否则统一使用 Python 进行刷题

知识点

  • Python 用 collections.deque 当 queue，先进先出（FIFO）

基本操作

# 创建
from collections import deque

q = deque()

# 入队（右边）
q.append(item)

# 出队（左边）
q.popleft()

# 查看队首（不弹出）
q[0]

# 查看队尾
q[-1]

# 判断是否为空
if q:        # 有元素
if not q:    # 空
len(q) == 0  # 空
q = deque()

q.append(1)      # [1]
q.append(2)      # [1, 2]
q.append(3)      # [1, 2, 3]

q[0]             # 1（队首）
q.popleft()      # 1，q 变成 [2, 3]
q.popleft()      # 2，q 变成 [3]

双端队列操作

q = deque()

# 左边操作
q.appendleft(item)  # 从左边入队
q.popleft()         # 从左边出队

# 右边操作
q.append(item)      # 从右边入队
q.pop()             # 从右边出队

标准 BFS 模板

from collections import deque

def bfs(root):
    if not root:
        return []
    
    q = deque()
    q.append(root)
    result = []
    
    while q:
        level_size = len(q)  # 这一层有几个
        level = []
        
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        
        result.append(level)
    
    return result

BFS 求最短路

  • 找最短路用 BFS，因为 BFS 一层一层扩展，第一次到达就是最短
def shortestPath(grid):
    m, n = len(grid), len(grid[0])
    q = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    
    while q:
        r, c, dist = q.popleft()
        
        if r == m - 1 and c == n - 1:
            return dist
        
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc, dist + 1))
    
    return -1

Grid 版 DFS

def dfs(grid, row, col):
    m, n = len(grid), len(grid[0])
    
    if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] != '1':
        return
    
    grid[row][col] = '0'  # 标记为已访问
    
    dfs(grid, row + 1, col)
    dfs(grid, row - 1, col)
    dfs(grid, row, col + 1)
    dfs(grid, row, col - 1)

Grid 版 BFS

from collections import deque

def bfs(grid, start_row, start_col):
    m, n = len(grid), len(grid[0])
    q = deque([(start_row, start_col)])
    visited = {(start_row, start_col)}
    
    while q:
        row, col = q.popleft()
        
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            nr, nc = row + dr, col + dc
            if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc))

BFS + 入度（拓扑排序）

from collections import defaultdict, deque

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * numCourses
    
    # 建图
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    
    # 入度为 0 的节点入队
    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    count = 0
    
    while q:
        node = q.popleft()
        count += 1
        
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    
    return count == numCourses

DFS + 环检测（三色标记法）

from collections import defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    
    # 0=未访问, 1=正在访问, 2=已完成
    state = [0] * numCourses
    
    def hasCycle(node):
        if state[node] == 1:  # 正在访问，说明有环
            return True
        if state[node] == 2:  # 已完成，无环
            return False
        
        state[node] = 1  # 标记为正在访问
        for neighbor in graph[node]:
            if hasCycle(neighbor):
                return True
        state[node] = 2  # 标记为已完成
        return False
    
    for i in range(numCourses):
        if hasCycle(i):
            return False
    return True

题目

LC 102

LC 994

属于必会题，多源 BFS 按层扩散: 把所有腐烂橘子当作起点，每一层扩散代表 1 分钟，直到无法再感染新鲜橘子

grid = [
  [2,1,1],
  [1,1,0],
  [0,1,1]
]

第 0 分钟：2 在 (0,0)
第 1 分钟：感染相邻的新鲜橘子
第 2 分钟：继续扩散
最终 fresh = 0 → 答案 = 2

LC 200

经典必会题

LC 695

经典必会题

LC 827

先用 DFS 给每个岛编号并记录面积，再尝试把每个 0 变成 1，把相邻不同岛的面积相加取最大

grid = [
  [1,0],
  [0,1]
]

编号岛屿：
岛 2 面积 = 1
岛 3 面积 = 1

把 (0,1) 变 1 → 连接岛 2 + 岛 3
最大面积 = 1 + 1 + 1 = 3

LC 489

用 DFS + 回溯遍历所有可达格子：每走一步就标记已访问，四个方向尝试，走不通就原路退回并恢复朝向

起点 S，机器人尝试：上 → 右 → 下 → 左
走到新格子：clean + 标记 visited
撞墙 / 走过：回退一步 + 转回原方向
直到所有可达格子都访问完