7.13N皇后(LC51-H)

2024-01-02 14:05:55

算法:

N皇后是回溯的经典题

画树:

假设N=3

皇后们的约束条件:

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

回溯三部曲:

1.确定函数参数和返回值

返回值:void

参数:

int n:题目给出,N皇后的个数,棋盘大小nxn

int row:用row来记录当前遍历到棋盘的第几层了

char[][] chessboard:二维字符数组,表示棋盘。每个`chessboard[i]`?都是一个字符数组,而`chessboard[i][j]`?则表示二维数组中特定位置?`(i, j)`?处的字符值。

2.确定终止条件

row==n

当递归到棋盘最底层(也就是叶子节点)的时候,就可以收集结果并返回了。

3.单层递归逻辑(for循环)

每次都是要从新的一行的起始位置开始搜,所以都是从0开始。

for (int col = 0;col < n; col++) {
            if (isValid (row, col, n, chessboard)) {
                // 验证合法就可以放
                chessboard[row][col] = 'Q';
                //递归
                backTrack(n, row+1, chessboard);
                //回溯,撤销皇后
                chessboard[row][col] = '.';
            }
        }

验证棋盘是否合法

isValid:先判错

按照如下标准去重:

  1. 不能同行
  2. 不能同列
  3. 不能同斜线 (45度和135度角)

同列

for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }

同行(其实可以不放,因为在单层搜索的过程中,每一层递归,只会选for循环(也就是同一行)里的一个元素,所以不用去重了。)

for (int j = 0; i < col; j++) { // 这是一个剪枝
        if (chessboard[row][j] == 'Q') {
            return false;
        }
    }

同斜线(45度)

for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }

同斜线(135度)

 for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }

正确代码:

class Solution {
    List<List<String>> result = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
    char[][] chessboard2 = new char[n][n];
    for (char[] c:chessboard2){
        Arrays.fill(c,'.');
    }
    backtracking(n, 0, chessboard2);
    return result;
    }
    void backtracking (int n, int row, char[][] chessboard){
        if (row == n) {
            result.add (Array2List(chessboard));
            return;
        }
        for (int col=0; col<n; col++){
        if (isValid(col, row, n, chessboard)) {
        chessboard[row][col] = 'Q';
        backtracking(n, row+1, chessboard);
        chessboard[row][col] = '.';
        }
        }
    }

    boolean isValid(int col, int row, int n, char[][] chessboard){
    //同列
    for (int i=0; i<row; i++){
        if (chessboard[i][col] == 'Q')  return false;
        
    }
    //同行
    for (int i=0; i<col; i++){
        if (chessboard[row][i] == 'Q') return false;
        
    }
    //45度
    for (int i=row-1, j= col-1 ; i>=0 && j>=0; i--, j--){
        if (chessboard[i][j] == 'Q') return false;
        
    }   
    //135度
    for (int i=row-1, j= col+1;  i>=0 && j<n; i--, j++){
        if (chessboard[i][j] == 'Q') return false;
        
    } 
    return true; 
    }

    List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

}

注意:

(1)想要将二维字符数组转换为 List<List<String>> 的格式。需要编写一个方法(Array2List)来实现这一转换。

(2)在 Java 中,字符的比较应该使用单引号而不是双引号。因此,应该使用单引号`'Q'`和`'.'`来比较而不是`"Q"``"."`

时间空间复杂度:

文章来源:https://blog.csdn.net/m0_50696252/article/details/135332415
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。