拼夕夕要双休，不少员工强烈反对。。。

大家好，我是吴师兄。

一眨眼，国庆节已经过去大半，犹如平时的周末，一眨眼又是周一要上班。

如果是大小周或者单休，一年到头可能就指望着国庆或者过年那几天能够好好休息了，在互联网公司里面，还是有不少公司是执行大小周或者单休的放假安排，哪怕公司层面想要替换为双休，可能都会遭遇不小的阻力。

比如最近，网传拼夕夕要开启双休模式，就遭到了员工强烈反对，原因很简单： 很多员工的高薪就是靠周六那一天的“加班”给拉上去的，如果执行双休制度，那么意味着年收入相当于降薪 10% 左右 。

这种情况或许和调休一事有共性，舆论上很多人都反对调休，在总假期不变的情况下，对于沉默的大多数人来说，调休是难得的一个休息的假期。

...

继续回归我们公众号的主题。

给大家分享 8 个模式，掌握它可以解决 80% 的 Leetcode 问题。

以下是 8 个常见的模式和它们在 LeetCode 中的应用案例，学会这些模式，你就能轻松应对 80% 的 LeetCode 问题。

1、滑动窗口：优化子数组和子字符串问题

滑动窗口是一种常用的技巧，特别适合解决子数组和子字符串相关的问题。滑动窗口的核心思想是在一个可变大小的窗口中维护一些信息，并通过窗口的移动来缩小问题的范围。

一般来说，可以通过三问三答的形式进行思考：

1、对于每一个右指针 right 所指的元素 ch ，做什么操作？

2、什么时候要令左指针 left 右移？left对应的元素做什么操作？【循环不变量】

3、什么时候进行ans的更新？

这三个问题，本质上对应了滑窗问题需要考虑的三个基本要素：

1、right 指针以及所对应的元素 ch

2、left 指针以及所对应的元素 left_ch

3、ans 答案变量

题目1：LeetCode 3. 无重复字符的最长子串

class Solution:
  def lengthOfLongestSubstring（self,s: str） -> int：
    ans = 0
    hash_set = set()
    left = 0

    for right, ch in enumerate(s) :
      # Q1：对于每一个右指针 right 所指的元素ch，做什么操作？
      # A1：若 ch 不在哈希集合中，将ch 加入哈希集合
      if ch not in hash_set：
        hash_set.add（ch）
        #Q3：什么时候进行ans的更新？
        # A3：若 ch 不在哈希集合中，ans 更新
        ans = max（ans,right-left+1）
      else:
        # Q2：什么时候要令左指针 left 右移？
        # left对应的元素做什么操作？【循环不变量】
        # A2: ch 在哈希集合中，left右移直到 ch 不在哈希集合中
        while（ch in hash_set）：
          left_ch = s[left]
          hash_set.remove(left_ch)
          left += 1
        # A1：若 ch 在哈希集合中，left 右移完毕后，将ch 加入哈希集
        hash_set.add(ch)
     return ans

题目2：LeetCode 76. 最小覆盖子串

给定两个字符串 s 和 t ，找到 s 中包含 t 所有字母的最小子串。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""
        
        dict_t = Counter(t)
        required = len(dict_t)
        left, right = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None
        
        while right             char = s[right]
            window_counts[char] = window_counts.get(char, 0) + 1
            
            if char in dict_t and window_counts[char] == dict_t[char]:
                formed += 1
            
            while left <= right and formed == required:
                char = s[left]
                
                if right - left + 1 0]:
                    ans = (right - left + 1, left, right)
                
                window_counts[char] -= 1
                if char in dict_t and window_counts[char]                     formed -= 1
                
                left += 1
            
            right += 1
        
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

题目3：LeetCode 567. 字符串的排列

给定两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。

class




    
 Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        s1_count = Counter(s1)
        window_count = Counter()
        
        for i in range(len(s2)):
            window_count[s2[i]] += 1
            
            if i >= len(s1):
                if window_count[s2[i - len(s1)]] == 1:
                    del window_count[s2[i - len(s1)]]
                else:
                    window_count[s2[i - len(s1)]] -= 1
            
            if window_count == s1_count:
                return True
        
        return False

题目4：LeetCode 438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p ，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        p_count = Counter(p)
        s_count = Counter()
        
        for i in range(len(s)):
            s_count[s[i]] += 1
            
            if i >= len(p):
                if s_count[s[i - len(p)]] == 1:
                    del s_count[s[i - len(p)]]
                else:
                    s_count[s[i - len(p)]] -= 1
            
            if s_count == p_count:
                res.append(i - len(p) + 1)
        
        return res

题目5：LeetCode 30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words，返回所有串联形成的子串在 s 中的起始位置。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        
        word_len = len(words[0])
        num_words = len(words)
        total_len = word_len * num_words
        word_count = Counter(words)
        res = []
        
        for i in range(word_len):
            left = i
            sub_dict = Counter()
            count = 0
            
            for j in range(i, len(s) - word_len + 1, word_len):
                word = s[j:j + word_len]
                if word in word_count:
                    sub_dict[word] += 1
                    count += 1
                    
                    while sub_dict[word] > word_count[word]:
                        left_word = s[left:left + word_len]
                        sub_dict[left_word] -= 1
                        count -= 1
                        left += word_len
                    
                    if count == num_words:
                        res.append(left)
                else:
                    sub_dict.clear()
                    count = 0
                    left = j + word_len
        
        return res

2、二分查找：寻找分割点

二分查找是一种高效的查找方法，特别适合用于有序数组或具有一定规律的数据结构中。二分查找的核心思想是每次将搜索区间缩小一半，以此快速逼近答案。

一般来说，可以通过三问三答的形式进行思考：

1. 对于每个中间点 mid，我们应该如何处理？
2. 如何调整左右指针 left 和 right 以缩小搜索范围？
3. 在什么条件下可以直接返回答案？

这三个问题，本质上对应了二分查找问题需要考虑的三个基本要素：

1. mid 指针以及所对应的元素 mid_val
2. 左右指针 left 和 right 及其变化
3. 返回答案的条件

题目1：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findFirst




    
(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                # Q1：对于每个中间点 mid，我们应该如何处理？
                # A1：如果 mid_val 大于等于目标值，右边界收缩
                if nums[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
            # Q3：返回条件
            # A3：返回左指针，代表第一个满足条件的位置
            return left
        
        def findLast(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right

题目2：LeetCode 33. 搜索旋转排序数组

在一个升序排列的数组中，数组中的元素进行了部分旋转，找到指定的目标值的位置，如果不存在则返回 -1。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            
            # Q1：对于每个中间点 mid，我们应该如何处理？
            # A1：判断 mid 所在的部分是否有序
            if nums[left] <= nums[mid]:
                # Q2：如何调整左右指针 left 和 right 以缩小搜索范围？
                # A2：如果 target 在有序部分中，调整右指针，否则调整左指针
                if nums[left] <= target                     right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid]                     left = mid + 1
                else:
                    right = mid - 1
        
        return -1

题目3：LeetCode 74. 搜索二维矩阵

在一个矩阵中，每行的元素从左到右排序，每列的元素从上到下排序，判断是否存在一个目标值。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            mid_val = matrix[mid // n][mid % n]
            
            # Q1：对于每个中间点 mid，我们应该如何处理？
            # A1：将矩阵映射为一维数组，比较中间值
            if mid_val == target:
                return True
            elif mid_val                 left = mid + 1
            else:
                right = mid - 1
        
        return False

题目4：LeetCode 81. 搜索旋转排序数组 II

这是一个包含重复元素的旋转排序数组，要求找到目标值的位置，如果不存在则返回 -1。

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            # Q1：对于每个中间点 mid，我们应该如何处理？
            # A1：首先检查中间值是否为目标值
            if nums[mid] == target:
                return True
            
            # Q2：如何调整左右指针 left 和 right 以缩小搜索范围？
            # A2：处理边界值相等的情况，通过收缩左右指针来跳过重复值
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] <= nums[mid]:
                if nums[left] <= target                     right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid]                     left = mid + 1
                else:
                    right = mid - 1
        
        return False

题目5：LeetCode 153. 寻找旋转排序数组中的最小值

在一个旋转排序数组中找到最小值，数组中不存在重复元素。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while




    
 left             mid = left + (right - left) // 2
            
            # Q1：对于每个中间点 mid，我们应该如何处理？
            # A1：判断 mid 是否位于右侧有序部分
            if nums[mid] > nums[right]:
                # Q2：如何调整左右指针 left 和 right 以缩小搜索范围？
                # A2：如果 mid 位于右侧，最小值在右侧
                left = mid + 1
            else:
                # 否则最小值在左侧
                right = mid
        
        # Q3：返回左指针，此时 left 和 right 会指向相同元素
        return nums[left]

3、堆：寻找 top-k 元素

堆是一种适合解决 top-k 问题的数据结构。通过维护一个 k 大小的堆，可以高效地找到数组中的前 k 个最大或最小元素。

一般来说，可以通过三问三答的形式进行思考：

1. 如何初始化堆？
2. 如何处理新的元素以维护堆的性质？
3. 如何从堆中提取最终答案？

这三个问题，本质上对应了堆问题需要考虑的三个基本要素：

1. 堆的初始化
2. 堆的维护操作
3. 结果的提取

题目1：LeetCode 215. 数组中的第 K 个最大元素

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Q1：如何初始化堆？
        # A1：构建一个最小堆，初始时包含前 k 个元素
        heap = nums[:k]
        heapq.heapify(heap)

        # Q2：如何处理新的元素以维护堆的性质？
        # A2：对于剩余元素，如果大于堆顶，则替换堆顶并重新调整堆
        for num in nums[k:]:
            if num > heap[0]:
                heapq.heapreplace(heap, num)
        
        # Q3：如何从堆中提取最终答案？
        # A3：堆顶即为第 k 大的元素
        return heap[0]

题目2：LeetCode 347. 前 K 个高频元素

找到一个数组中出现频率最高的 k 个元素。

import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        # Q1：如何初始化堆？
        # A1：用堆存储频率最高的 k 个元素
        heap = heapq.nlargest(k, count.keys(), key=count.get)
        
        return heap

题目3：LeetCode 973. 最接近原点的 K 个点

给定一个平面上的点列表，找到离原点最近的 k 个点。

import heapq

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # Q1：如何初始化堆？
        # A1：将前 k 个点的距离与点一起存入最大堆
        heap = [(-self.distance(p), p) for p in points[:k]]
        heapq.heapify(heap)
        
        # Q2：如何处理新的元素以维护堆的性质？
        # A2：如果新点的距离比堆顶元素小，则替换堆顶
        for p in points[k:]:
            dist = -self.distance(p)
            if dist > heap[0][0]:
                heapq.heapreplace(heap, (dist, p))
        
        # Q3：如何从堆中提取最终答案？
        # A3：堆中存储的点即为结果
        return [p for _, p in heap]
    
    def distance(self, point):
        return point[0]**2 + point[1]**2

题目4：LeetCode 658. 找到 K 个最接近的元素

找到一个数组中最接近目标值的 k 个元素。

import heapq

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # Q1：如何初始化堆？
        # A1：使用一个最大堆存储前 k 个元素及其与 x 的距离
        heap = [(-abs(arr[i] - x), -arr[i]) for i in range(k)]
        heapq.heapify(heap)
        
        # Q2：如何处理新的元素以维护堆的性质？
        # A2：如果新元素比堆顶更接近 x，则替换堆顶
        for i in range(k, len(arr)):
            dist = -abs(arr[i] - x)
            if dist > heap[0][0]:
                heapq.heapreplace(heap, (dist, -arr[i]))
        
        # Q3：如何从堆中提取最终答案？
        # A3：堆中存储的元素即为结果
        return sorted([-h[1] for h in heap])

题目5：LeetCode 295. 数据流的中位数

维护一个数据流，随时能够找到当前数据流的中位数。

import heapq

class MedianFinder:
    def __init__(self):
        # Q1：如何初始化堆？
        # A1：使用两个堆，一个最大堆存储较小的一半，一个最小堆存储较大的一半
        self.small = []  # max heap
        self.large = []  # min heap

    def addNum(self, num: int) -> None:
        # Q2：如何处理新的元素以维护堆的性质？
        # A2：先将新元素加入最大堆，然后平衡两个堆的大小
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        
        if len(self.small)             heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        # Q3：如何从堆中提取最终答案？
        # A3：如果两个堆的大小相同，中位数是两个堆顶的平均值，否则是最大堆的堆顶
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

4、深度优先搜索（DFS）：遍历图和树的基础

深度优先搜索（DFS）是一种遍历或搜索图、树结构的算法，常用于解决全路径、连通性等问题。

一般来说，可以通过三问三答的形式进行思考：

1. 如何处理当前节点？
2. 如何递归到子节点？
3. 如何处理递归返回后的结果？

这三个问题，本质上对应了 DFS 问题需要考虑的三个基本要素：

1. 当前节点的处理
2. 递归调用的处理
3. 递归返回后的结果处理

题目1：LeetCode 104. 二叉树的最大深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # Q1：如何处理当前节点？
        # A1：如果节点为空，直接返回 0
        if not root:
            return 0
        
        # Q2：如何递归到子节点？
        # A2：分别递归计算左子树和右子树的深度
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        # Q3：如何处理递归返回后的结果？
        # A3：返回左子树和右子树深度的较大者，再加 1 表示当前层级
        return max(left_depth, right_depth) + 1

题目2：LeetCode 543. 二叉树的直径

计算二叉树的直径，即任意两节点路径中，边的最大数目。

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0
        
        def depth(node):
            if not node:
                return 0
            
            # Q2：如何递归到子节点？
            # A2：计算左右子树的深度
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            
            # Q3：如何处理递归返回后的结果？
            # A3：更新最大直径为当前节点的左深度 + 右深度
            self.diameter = max(self.diameter, left_depth + right_depth)
            
            # 返回当前节点的深度
            return max(left_depth, right_depth) + 1
        
        depth(root)
        return self.diameter

题目3：LeetCode 130. 被围绕的区域

在二维矩阵中，如果被 ‘X’ 包围的 ‘O’ 被替换为 ‘X’。

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return
        
        m, n = len(board), len(board[0])
        
        def dfs(i, j):
            # Q1：如何处理当前节点？
            # A1：将边界或连通边界的 'O' 标记为 '*'
            if i 0 or i >= m or j 0 or j >= n or board[i][j] != 'O':
                return
            board[i][j] = '*'
            # Q2：如何递归到子节点？
            # A2：递归四个方向
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O' and (i in [0, m - 1] or j in [0, n - 1]):
                    dfs(i, j)
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '*':
                    board[i][j] = 'O'

题目4：LeetCode 200. 岛屿数量

计算二维矩阵中岛屿的数量，岛屿由相邻的陆地‘1’组成，水域为‘0’。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        count = 0
        
        def dfs(i, j):
            # Q1：如何处理当前节点？
            # A1：将当前陆地标记为已访问
            if i 0 or i >= m or j 0 or j >= n or grid[i][j] != '1':
                return
            grid[i][j] = '0'
            # Q2：如何递归到子节点？
            # A2：递归四个方向
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)
        
        return count

题目5：LeetCode 39. 组合总和

找到所有和为目标值的组合，元素可重复使用。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        
        def dfs(path, start, target):
            # Q1：如何处理当前节点？
            # A1：当目标值为0时，将路径添加到结果集
            if target == 0:
                res.append(path)
                return
            # Q2：如何递归到子节点？
            # A2：从当前元素开始，尝试使用每个元素
            for i in range(start, len(candidates)):
                if candidates[i] <= target:
                    dfs(path + [candidates[i]], i, target - candidates[i])
        
        dfs([], 0, target)
        return res

5、拓扑排序：任务调度与依赖

拓扑排序用于解决具有依赖关系的任务排序问题，通常在有向无环图（DAG）中应用。

一般来说，可以通过三问三答的形式进行思考：

1. 如何构建图和入度数组？
2. 如何处理入度为 0 的节点？
3. 如何更新其他节点的入度？

这三个问题，本质上对应了拓扑排序问题需要考虑的三个基本要素：

1. 图的构建
2. 入度为 0 的节点处理
3. 入度更新

题目1：LeetCode 207. 课程表

from collections import deque, defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Q1：如何构建图和入度数组？
        # A1：构建邻接表和入度数组
        graph = defaultdict(list)
        in_degree = [0] * numCourses
        
        for dest, src in prerequisites:
            graph[src].append(dest)
            in_degree[dest] += 1
        
        # Q2：如何处理入度为 0 的节点？
        # A2：将所有入度为 0 的节点入队列，并开始遍历
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        completed_courses = 0
        
        while queue:
            course = queue.popleft()
            completed_courses += 1
            
            # Q3：如何更新其他节点的入度？
            # A3：减少邻接节点的入度，如果入度变为 0，加入队列
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        return completed_courses == numCourses

题目2：LeetCode 210. 课程表 II

这题是在课程表问题的基础上，要求返回完成所有课程的顺序。

from collections import deque, defaultdict

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        in_degree = [0] * numCourses
        
        for dest, src in prerequisites:
            graph[src].append(dest)
            in_degree[dest] += 1
        
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        order = []
        
        while queue:
            course = queue.popleft()
            order.append(course)
            
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        return order if len(order) == numCourses else []

题目3：LeetCode 329. 矩阵中的最长递增路径

在一个整数矩阵中，找到从任意单元格出发的最长递增路径。

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        def dfs(x, y):
            if not dp[x][y]:
                val = matrix[x][y]
                dp[x][y] = 1 + max(
                    dfs(x + dx, y + dy) 
                    for dx, dy in




    
 dirs
                    if 0 <= x + dx and 0 <= y + dy and matrix[x + dx][y + dy] > val
                )
            return dp[x][y]
        
        return max(dfs(i, j) for i in range(m) for j in range(n))

题目4：LeetCode 444. 序列重建

根据子序列判断是否能够唯一地重建原始序列。

from collections import defaultdict, deque

class Solution:
    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
        if not seqs:
            return False
        
        graph = defaultdict(list)
        in_degree = defaultdict(int)
        nodes = set()
        
        for seq in seqs:
            for i in range(len(seq)):
                nodes.add(seq[i])
                if i > 0:
                    graph[seq[i-1]].append(seq[i])
                    in_degree[seq[i]] += 1
        
        if nodes != set(org):
            return False
        
        queue = deque([x for x in org if in_degree[x] == 0])
        idx = 0
        
        while queue:
            if len(queue) > 1:
                return False
            
            node = queue.popleft()
            if org[idx] != node:
                return False
            idx += 1
            
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        return idx == len(org)

题目5：LeetCode 802. 找到最终的安全状态

在一个有向图中，找到所有能够到达终点的安全节点。

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        reverse_graph = [[] for _ in range(n)]
        out_degree = [0] * n
        safe_nodes = []
        
        for i in range(n):
            for j in graph[i]:
                reverse_graph[j].append(i)
            out_degree[i] = len(graph[i])
        
        queue = deque([i for i in range(n) if out_degree[i] == 0])
        
        while queue:
            node = queue.popleft()
            safe_nodes.append(node)
            
            for parent in reverse_graph[node]:
                out_degree[parent] -= 1
                if out_degree[parent] == 0:
                    queue.append(parent)
        
        return sorted(safe_nodes)

6、广度优先搜索（BFS）：层级遍历与最短路径

广度优先搜索（BFS）是一种层级遍历算法，特别适合用于搜索最短路径或进行层级遍历的问题。

一般来说，可以通过三问三答的形式进行思考：

1. 如何处理当前层的节点？
2. 如何扩展到下一层的节点？
3. 如何确定搜索是否完成？

这三个问题，本质上对应了 BFS 问题需要考虑的三个基本要素：

1. 当前层节点的处理
2. 扩展到下一层的处理
3. 搜索完成的条件

题目1：LeetCode 102. 二叉树的层序遍历

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not




    
 root:
            return []
        
        # Q1：如何处理当前层的节点？
        # A1：使用队列存储当前层的所有节点
        queue = deque([root])
        result = []
        
        while queue:
            level_size = len(queue)
            level = []
            
            # Q2：如何扩展到下一层的节点？
            # A2：遍历当前层所有节点，将其子节点加入队列
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Q3：搜索完成的条件
            # A3：将当前层结果加入最终结果集
            result.append(level)
        
        return result

题目2：LeetCode 111. 二叉树的最小深度

找出二叉树的最小深度，即从根节点到最近的叶子节点的最短路径。

from collections import deque

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        queue = deque([(root, 1)])
        
        while queue:
            node, depth = queue.popleft()
            
            if not node.left and not node.right:
                return depth
            
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))
        
        return 0

题目3：LeetCode 752. 打开转盘锁

给定一个只包含 0 到 9 的四位密码锁，找到解锁的最小步数。

from collections import deque

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        queue = deque([('0000', 0)])
        visited = set('0000')
        
        while queue:
            node, steps = queue.popleft()
            
            if node == target:
                return steps
            if node in dead:
                continue
            
            for

 i in range(4):
                for d in (-1, 1):
                    new_digit = (int(node[i]) + d) % 10
                    new_node = node[:i] + str(new_digit) + node[i+1:]
                    if new_node not in visited:
                        visited.add(new_node)
                        queue.append((new_node, steps + 1))
        
        return -1

题目4：LeetCode 127. 单词接龙

给定两个单词，找到从第一个单词到第二个单词的最短转换序列，每次只能改变一个字母，且每一步必须是一个有效单词。

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        
        queue = deque([(beginWord, 1)])
        
        while queue:
            word, length = queue.popleft()
            
            if word == endWord:
                return length
            
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in word_set:
                        word_set.remove(new_word)
                        queue.append((new_word, length + 1))
        
        return 0

题目5：LeetCode 200. 岛屿数量

计算二维矩阵中岛屿的数量，岛屿由相邻的陆地‘1’组成，水域为‘0’。这个题目既可以用DFS解决，也可以用BFS。

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        count = 0
        
        def bfs(i, j):
            queue = deque([(i, j)])
            grid[i][j] = '0'
            
            while queue:
                x, y = queue.popleft()
                
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0