LeetCode 200. 岛屿数量
字数 3169 2025-12-10 10:01:52

LeetCode 200. 岛屿数量

你已经列出了“LeetCode 200. 岛屿数量”，所以根据你的要求，我不能讲解这个题目。让我从搜索算法领域为你随机选择另一个未被列出的经典算法题目。

LeetCode 51. N 皇后

题目描述

N 皇后问题是在一个 N×N 的棋盘上放置 N 个皇后，使得皇后之间不能相互攻击。在国际象棋中，皇后可以攻击同一行、同一列、以及两个对角线方向上的任意距离棋子。题目要求你找出所有不同的解决方案。每个解决方案是一个 N×N 的棋盘布局，其中 ‘Q’ 代表一个皇后，‘.’ 代表一个空格。解决方案之间，皇后放置的具体位置是不同的。

解题过程循序渐进讲解

  1. 问题核心与约束分析
    我们需要在 N×N 的棋盘上放置 N 个皇后。每个皇后能攻击其所在的行、列和两个方向的对角线。这意味着，在任何一个有效的解决方案中，每一行、每一列、每一条主对角线（左上到右下方向）和每一条副对角线（右上到左下方向）上，最多只能有一个皇后。

  2. 总体思路：回溯搜索
    这是一个经典的组合问题，需要探索所有可能的放置方式，并从中筛选出有效的解决方案。由于 N 可能较大（题目中 1 <= N <= 9），我们不能简单地枚举所有 C(N^2, N) 种组合，必须进行剪枝。回溯算法 是解决此类问题的标准方法。其核心思想是：我们一行一行地放置皇后。在尝试当前行的每一列时，都检查这个位置是否会被之前已经放置好的皇后攻击。如果是安全的，我们就在此放置一个皇后，然后递归地去放置下一行的皇后。如果最终我们成功放置了所有 N 个皇后，就记录下这个棋盘布局。无论成功与否，我们在递归返回（回溯）时，都需要将当前位置的皇后移除，然后尝试当前行的下一个可能位置。

  3. 关键实现细节

    • 棋盘表示：我们通常使用一个一维数组 queens 来记录每行皇后的列位置。queens[row] = col 表示第 row 行的皇后放在了第 col 列。这天然保证了每行只有一个皇后。
    • 攻击冲突检测：我们需要快速判断在 (row, col) 位置放置皇后是否安全。这意味着：
      1. 列冲突：检查所有之前行 i （从0到 row-1）的 queens[i] 是否等于当前列 col。
      2. 主对角线冲突：主对角线上，行索引与列索引的差值是常数（row - col 是定值）。检查所有之前行 i 是否有 i - queens[i] == row - col。
      3. 副对角线冲突：副对角线上，行索引与列索引的和是常数（row + col 是定值）。检查所有之前行 i 是否有 i + queens[i] == row + col。
    • 递归函数设计：设计一个递归函数 backtrack(row)，其含义是“尝试放置第 row 行及之后的所有皇后”。
    • 终止条件：当 row == N 时，意味着我们已经成功放置了前 N 行（即所有行）的皇后，找到了一个有效解。此时，根据 queens 数组生成一个棋盘字符串列表（例如 [“.Q..”, “…Q”, “Q…”, “..Q.”]），并加入到最终答案列表中。

  4. 逐步推演（以 N=4 为例）

    • 初始化：queens = [0, 0, 0, 0]，答案列表 solutions = []。从第0行开始调用 backtrack(0)。
    • 尝试放置第0行 (row=0)：
      • 尝试 col=0：安全（因为前面没有皇后）。设置 queens[0]=0。递归调用 backtrack(1)。
    • 尝试放置第1行 (row=1)：
      • 尝试 col=0：不安全（和第0行皇后同列）。跳过。
      • 尝试 col=1：不安全（和第0行皇后在副对角线上，0+0 == 1+1? 不相等，但检查主对角线：0-0 == 1-1? 相等！冲突）。跳过。
      • 尝试 col=2：安全。设置 queens[1]=2。递归调用 backtrack(2)。
    • 尝试放置第2行 (row=2)：
      • 尝试 col=0 到 col=3，你会发现没有一列是安全的（col=0与row=0同列，col=1与row=1在副对角线上，col=2与row=1同列，col=3与row=1在主对角线上）。因此，backtrack(2) 无法成功，函数返回。
    • 回溯到第1行 (row=1)：我们将 queens[1] 复原（虽然这里会被覆盖），并尝试下一个位置。
      • 尝试 col=3：安全。设置 queens[1]=3。递归调用 backtrack(2)。
    • 再次尝试放置第2行 (row=2)：
      • 尝试 col=0：不安全（同列检查失败于row=0）。跳过。
      • 尝试 col=1：安全。设置 queens[2]=1。递归调用 backtrack(3)。
    • 尝试放置第3行 (row=3)：
      • 尝试 col=0：不安全（同列检查失败于row=0）。跳过。
      • 尝试 col=1：不安全（同列检查失败于row=2）。跳过。
      • 尝试 col=2：不安全（主对角线检查失败于row=1，因为1-3 == 2-2? 1-3=-2, 2-2=0，不相等。等等，副对角线检查：row=0的0+0=0，当前3+2=5，不冲突。row=1的1+3=4，3+2=5，不冲突。row=2的2+1=3，3+2=5，不冲突。实际上col=2是安全的吗？我们需要仔细检查：
        1. 列冲突：queens[0]=0, queens[1]=3, queens[2]=1，都不等于2，安全。
        2. 主对角线冲突：row-col分别为：0-0=0, 1-3=-2, 2-1=1。当前3-2=1，与row=2的2-1=1冲突！所以不安全。）
      • 尝试 col=3：不安全（同列检查失败于row=1）。跳过。
      • 因此，backtrack(3) 无法成功，返回。
    • 回溯到第2行 (row=2)：继续尝试剩下的位置。
      • col=2, col=3 尝试完，都不安全。backtrack(2) 返回。
    • 回溯到第1行 (row=1)：所有位置（col=0,1,2,3）都已尝试。backtrack(1) 返回。
    • 回溯到第0行 (row=0)：我们之前只尝试了 col=0。现在尝试下一个位置。
      • 尝试 col=1：安全。设置 queens[0]=1。调用 backtrack(1)。
    • 按照同样的逻辑继续探索，最终我们会找到 N=4 的两个有效解，分别对应 queens = [1, 3, 0, 2] 和 queens = [2, 0, 3, 1]。

  5. 总结
    解决 N 皇后问题的回溯算法框架非常清晰：

    1. 定义一个递归函数，参数是当前要放置皇后的行号 row。
    2. 如果 row == N，说明所有皇后都已放置好，记录一个有效解。
    3. 否则，遍历当前行的每一列 col：
      • 如果位置 (row, col) 是安全的（不与之前任何皇后冲突）：
        • 放置皇后：queens[row] = col。
        • 递归调用函数，尝试放置下一行：backtrack(row + 1)。
        • （回溯步骤隐含在函数返回后，继续循环尝试下一列。数组的赋值操作会在下一次循环中被覆盖，这就是回溯“撤销”的过程。）

    这个算法系统地探索了整个解空间，并通过约束检查（剪枝）极大地减少了无效的搜索路径，从而高效地找到了所有可能的解。

LeetCode 200. 岛屿数量 你已经列出了“LeetCode 200. 岛屿数量”，所以根据你的要求，我不能讲解这个题目。让我从搜索算法领域为你随机选择另一个未被列出的经典算法题目。 LeetCode 51. N 皇后 题目描述 N 皇后问题是在一个 N×N 的棋盘上放置 N 个皇后，使得皇后之间不能相互攻击。在国际象棋中，皇后可以攻击同一行、同一列、以及两个对角线方向上的任意距离棋子。题目要求你找出所有不同的解决方案。每个解决方案是一个 N×N 的棋盘布局，其中 ‘Q’ 代表一个皇后，‘.’ 代表一个空格。解决方案之间，皇后放置的具体位置是不同的。 解题过程循序渐进讲解 问题核心与约束分析 我们需要在 N×N 的棋盘上放置 N 个皇后。每个皇后能攻击其所在的行、列和两个方向的对角线。这意味着，在任何一个有效的解决方案中，每一行、每一列、每一条主对角线（左上到右下方向）和每一条副对角线（右上到左下方向）上，最多只能有一个皇后。 总体思路：回溯搜索 这是一个经典的 组合问题 ，需要探索所有可能的放置方式，并从中筛选出有效的解决方案。由于 N 可能较大（题目中 1 <= N <= 9），我们不能简单地枚举所有 C(N^2, N) 种组合，必须进行 剪枝 。 回溯算法 是解决此类问题的标准方法。其核心思想是：我们一行一行地放置皇后。在尝试当前行的每一列时，都检查这个位置是否会被之前已经放置好的皇后攻击。如果是安全的，我们就在此放置一个皇后，然后递归地去放置下一行的皇后。如果最终我们成功放置了所有 N 个皇后，就记录下这个棋盘布局。无论成功与否，我们在递归返回（回溯）时，都需要将当前位置的皇后移除，然后尝试当前行的下一个可能位置。 关键实现细节 棋盘表示 ：我们通常使用一个一维数组 queens 来记录每行皇后的列位置。 queens[row] = col 表示第 row 行的皇后放在了第 col 列。这天然保证了每行只有一个皇后。 攻击冲突检测 ：我们需要快速判断在 (row, col) 位置放置皇后是否安全。这意味着： 列冲突 ：检查所有之前行 i （从0到 row-1）的 queens[i] 是否等于当前列 col 。 主对角线冲突 ：主对角线上，行索引与列索引的 差值是常数 （ row - col 是定值）。检查所有之前行 i 是否有 i - queens[i] == row - col 。 副对角线冲突 ：副对角线上，行索引与列索引的 和是常数 （ row + col 是定值）。检查所有之前行 i 是否有 i + queens[i] == row + col 。 递归函数设计 ：设计一个递归函数 backtrack(row) ，其含义是“尝试放置第 row 行及之后的所有皇后”。 终止条件 ：当 row == N 时，意味着我们已经成功放置了前 N 行（即所有行）的皇后，找到了一个有效解。此时，根据 queens 数组生成一个棋盘字符串列表（例如 [“.Q..”, “…Q”, “Q…”, “..Q.”] ），并加入到最终答案列表中。 逐步推演（以 N=4 为例） 初始化 ： queens = [0, 0, 0, 0] ，答案列表 solutions = [] 。从第0行开始调用 backtrack(0) 。 尝试放置第0行 ( row=0 )： 尝试 col=0 ：安全（因为前面没有皇后）。设置 queens[0]=0 。递归调用 backtrack(1) 。 尝试放置第1行 ( row=1 )： 尝试 col=0 ：不安全（和第0行皇后同列）。跳过。 尝试 col=1 ：不安全（和第0行皇后在副对角线上，0+0 == 1+1? 不相等，但检查主对角线：0-0 == 1-1? 相等！冲突）。跳过。 尝试 col=2 ：安全。设置 queens[1]=2 。递归调用 backtrack(2) 。 尝试放置第2行 ( row=2 )： 尝试 col=0 到 col=3 ，你会发现没有一列是安全的（ col=0 与 row=0 同列， col=1 与 row=1 在副对角线上， col=2 与 row=1 同列， col=3 与 row=1 在主对角线上）。因此， backtrack(2) 无法成功，函数返回。 回溯到第1行 ( row=1 )：我们将 queens[1] 复原（虽然这里会被覆盖），并尝试下一个位置。 尝试 col=3 ：安全。设置 queens[1]=3 。递归调用 backtrack(2) 。 再次尝试放置第2行 ( row=2 )： 尝试 col=0 ：不安全（同列检查失败于 row=0 ）。跳过。 尝试 col=1 ：安全。设置 queens[2]=1 。递归调用 backtrack(3) 。 尝试放置第3行 ( row=3 )： 尝试 col=0 ：不安全（同列检查失败于 row=0 ）。跳过。 尝试 col=1 ：不安全（同列检查失败于 row=2 ）。跳过。 尝试 col=2 ：不安全（主对角线检查失败于 row=1 ，因为1-3 == 2-2? 1-3=-2, 2-2=0，不相等。等等，副对角线检查： row=0 的0+0=0，当前3+2=5，不冲突。 row=1 的1+3=4，3+2=5，不冲突。 row=2 的2+1=3，3+2=5，不冲突。实际上 col=2 是安全的吗？我们需要仔细检查： 列冲突 ： queens[0]=0 , queens[1]=3 , queens[2]=1 ，都不等于2，安全。 主对角线冲突 ： row-col 分别为：0-0=0, 1-3=-2, 2-1=1。当前 3-2=1 ，与 row=2 的 2-1=1 冲突 ！所以不安全。） 尝试 col=3 ：不安全（同列检查失败于 row=1 ）。跳过。 因此， backtrack(3) 无法成功，返回。 回溯到第2行 ( row=2 )：继续尝试剩下的位置。 col=2 , col=3 尝试完，都不安全。 backtrack(2) 返回。 回溯到第1行 ( row=1 )：所有位置（ col=0,1,2,3 ）都已尝试。 backtrack(1) 返回。 回溯到第0行 ( row=0 )：我们之前只尝试了 col=0 。现在尝试下一个位置。 尝试 col=1 ：安全。设置 queens[0]=1 。调用 backtrack(1) 。 按照同样的逻辑继续探索 ，最终我们会找到 N=4 的两个有效解，分别对应 queens = [1, 3, 0, 2] 和 queens = [2, 0, 3, 1] 。 总结 解决 N 皇后问题的 回溯算法 框架非常清晰： 定义一个递归函数，参数是当前要放置皇后的行号 row 。 如果 row == N ，说明所有皇后都已放置好，记录一个有效解。 否则，遍历当前行的每一列 col ： 如果位置 (row, col) 是安全的（不与之前任何皇后冲突）： 放置皇后： queens[row] = col 。 递归调用函数，尝试放置下一行： backtrack(row + 1) 。 （回溯步骤隐含在函数返回后，继续循环尝试下一列。数组的赋值操作会在下一次循环中被覆盖，这就是回溯“撤销”的过程。） 这个算法系统地探索了整个解空间，并通过约束检查（剪枝）极大地减少了无效的搜索路径，从而高效地找到了所有可能的解。