LeetCode51

LeetCode51

目录

• 题目描述
• 示例
• 思路分析
• 代码段
• 代码逐行讲解
• 复杂度分析
• 总结的知识点
• 整合
• 总结

题目描述

N 皇后问题：将 n 个皇后放置在 n x n 的棋盘上，使得皇后彼此之间不能相互攻击（即任何两个皇后不能在同一行、同一列或同一斜线上）。

返回所有不同的解决方案。每个解决方案包含一个明确的 n x n 的棋盘布局，其中 'Q' 表示皇后，'.' 表示空位。

示例

示例 1

输入:

n = 4

输出:

[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解释:

• 4 皇后问题有两个不同的解决方案。

示例 2

输入:

n = 1

输出:

[["Q"]]

解释:

• 1 皇后问题只有一个解决方案。

思路分析

问题核心

我们需要在 n x n 的棋盘上放置 n 个皇后，使得它们互不攻击。皇后可以攻击同一行、同一列或同一斜线上的其他皇后。

思路拆解

1. 回溯算法：
   • 使用回溯算法逐行放置皇后，并在每一行中尝试所有可能的列。
2. 冲突检测：
   • 使用三个布尔数组分别记录列、左斜线和右斜线的冲突情况。
   • 列冲突：ca[j] 表示第 j 列是否被占用。
   • 左斜线冲突：cb[i + j] 表示左斜线是否被占用。
   • 右斜线冲突：cc[n - 1 - (i - j)] 表示右斜线是否被占用。
3. 递归终止条件：
   • 如果成功放置了 n 个皇后，则将当前棋盘布局加入结果列表。
4. 回溯：
   • 在递归返回时，撤销当前皇后的放置，并恢复冲突数组的状态。

代码段

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        boolean[] ca = new boolean[n]; 
        boolean[] cb = new boolean[2 * n - 1]; 
        boolean[] cc = new boolean[2 * n - 1];
        char[][] table = new char[n][n]; 
        for (int i = 0; i < n; i++) {
            Arrays.fill(table[i], '.'); 
        }
        dfs(0, n, table, ca, cb, cc, ans); 
        return ans;
    }

    static void dfs(int i, int n, char[][] table,
            boolean[] ca,
            boolean[] cb,
            boolean[] cc,
            List<List<String>> ans) {
        if (i == n) { 
            List<String> solution = new ArrayList<>();
            for (char[] chars : table) {
                solution.add(new String(chars)); 
            }
            ans.add(solution);
            return;
        }
        for (int j = 0; j < n; j++) { 
            if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
                continue;
            }
            table[i][j] = 'Q';
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true; 
            dfs(i + 1, n, table, ca, cb, cc, ans); 
            table[i][j] = '.'; 
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false;        }
    }
}

代码逐行讲解

1. 初始化结果列表

List<List<String>> ans = new ArrayList<>();

• ans 用于存储所有合法的棋盘布局。

2. 初始化冲突数组

boolean[] ca = new boolean[n]; // 列冲突
boolean[] cb = new boolean[2 * n - 1]; // 左斜线冲突
boolean[] cc = new boolean[2 * n - 1]; // 右斜线冲突

• ca 记录每一列是否被占用。
• cb 记录每一条左斜线是否被占用。
• cc 记录每一条右斜线是否被占用。

3. 初始化棋盘

char[][] table = new char[n][n];
for (int i = 0; i < n; i++) {
    Arrays.fill(table[i], '.'); // 初始化棋盘
}

• table 表示棋盘，初始化为 '.'。

4. 调用 DFS

dfs(0, n, table, ca, cb, cc, ans);

• 从第 0 行开始递归放置皇后。

5. DFS 函数

static void dfs(int i, int n, char[][] table,
        boolean[] ca,
        boolean[] cb,
        boolean[] cc,
        List<List<String>> ans) {

• DFS 函数的定义，用于递归放置皇后。

6. 找到一个解

if (i == n) {
    List<String> solution = new ArrayList<>();
    for (char[] chars : table) {
        solution.add(new String(chars));
    }
    ans.add(solution);
    return;
}

• 如果成功放置了 n 个皇后，则将当前棋盘布局加入结果列表。

7. 尝试放置皇后

for (int j = 0; j < n; j++) {

• 在第 i 行的每一列尝试放置皇后。

8. 冲突检测

if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
    continue;
}

• 如果当前列、左斜线或右斜线有冲突，则跳过。

9. 放置皇后

table[i][j] = 'Q';
ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true;

• 放置皇后，并标记冲突。

10. 递归

dfs(i + 1, n, table, ca, cb, cc, ans);

• 递归放置下一行的皇后。

11. 回溯

table[i][j] = '.';
ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false;

• 回溯时撤销皇后的放置，并恢复冲突数组的状态。

复杂度分析

时间复杂度

• 最坏情况下需要遍历所有可能的放置方式，时间复杂度为 O(n!)。

空间复杂度

• 需要存储所有合法的棋盘布局，空间复杂度为 O(n^2 * n!)。
• 递归栈的深度为 n，因此额外空间复杂度为 O(n)。

总结的知识点

1. 回溯算法

• 使用回溯算法逐行放置皇后，并在递归返回时撤销操作。

2. 冲突检测

• 使用布尔数组记录列、左斜线和右斜线的冲突情况。

3. 递归与回溯

• 通过递归实现深度优先搜索，并通过回溯撤销操作。

4. 棋盘表示

• 使用二维字符数组表示棋盘，并用 'Q' 和 '.' 分别表示皇后和空位。

整合

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>(); // 结果列表
        boolean[] ca = new boolean[n]; // 列冲突
        boolean[] cb = new boolean[2 * n - 1]; // 左斜线冲突
        boolean[] cc = new boolean[2 * n - 1]; // 右斜线冲突
        char[][] table = new char[n][n]; // 棋盘
        for (int i = 0; i < n; i++) {
            Arrays.fill(table[i], '.'); // 初始化棋盘
        }
        dfs(0, n, table, ca, cb, cc, ans); // DFS
        return ans;
    }

    static void dfs(int i, int n, char[][] table,
            boolean[] ca,
            boolean[] cb,
            boolean[] cc,
            List<List<String>> ans) {
        if (i == n) { // 找到一个解
            List<String> solution = new ArrayList<>();
            for (char[] chars : table) {
                solution.add(new String(chars)); // 将棋盘布局加入解
            }
            ans.add(solution); // 将解加入结果列表
            return;
        }
        for (int j = 0; j < n; j++) { // 尝试在第 i 行的每一列放置皇后
            if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) { // 冲突检测
                continue;
            }
            table[i][j] = 'Q'; // 放置皇后
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true; // 标记冲突
            dfs(i + 1, n, table, ca, cb, cc, ans); // 递归
            table[i][j] = '.'; // 回溯
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false; // 撤销冲突标记
        }
    }
}

总结

通过回溯算法和冲突检测，能够高效地解决 N 皇后问题。