[Lc]52N皇后II

题目

题解

这道题是51题的化简版，这里贴上51题的思路。唯一的区别就说不用统计所有的棋盘情况，而是遍历完一个分支就计数+1
这道题是很经典的一道题，思路就是dfs与回溯剪枝。这类回溯题的递归函数基本套路是这样的

判断是否终止并满足条件，满足了就加入res中
遍历每一种可能，在每一种可能中：
1. 先改变当前状态
2. 递归下一层
3. 回溯时再把状态变回去

这道题就是用的这种思想，用dfs遍历每一种情况，在放下一个皇后的时候判断该位置能否放皇后。能放的话递归下一层，有两种存储皇后的方式，用string直接存储和用数组标记每一行皇后的列数，后者在存储结果时要转化为字符串再存储，但其在判断能否放皇后的时候更加便捷。

1. string保存法

时间复杂度$O(n!)$，放置第1个皇后有n种可能的方法，放置两个皇后的方法不超过 $n(n-2)$ ，放置 3 个皇后的方法不超过 $n(n-2)(n-4)$ ，以此类推。总体上，时间复杂度为 $\mathcal{O}(N!)$.
（摘自leetcode官方题解）
空间复杂度$O(n)$

class Solution {//两个方法。1.string保存法
    vector<vector<string>> res;//存最终结果
    vector<string> queens;//存当前棋盘
public:
    //检验当前位置放皇后是否符合要求
    bool check(vector<string> queens, int row, int col, int n){
        for(int i=1; i<=row; ++i){//这里的i与row的差距，从row的上一行到第0行
            if(queens[row-i][col] == 'Q') return false;//若当前列有皇后，报错
            if(col-i>=0 && queens[row-i][col-i]=='Q') return false;//若左上角有皇后，报错
            if(col+i<n && queens[row-i][col+i]=='Q') return false;//若右上角有皇后，报错
        }
        return true;//未报错返回true
    }
    //dfs与回溯，当递归超出最后一行时将当前棋盘加入结果
    void dfs(int row, int n){
        if(row>=n){
            res.push_back(queens);
            return ;
        }
        //在当前行的每一列尝试放棋子
        for(int i=0; i<n; ++i){
            if(check(queens, row, i, n)){
                queens[row][i] = 'Q';//在row行i列放棋子
                dfs(row+1, n);//递归下一行
                queens[row][i] = '.';//回溯时将放的棋子变回'.'
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        queens = vector<string>(n,string(n,'.'));//先将棋盘均设置为空
        dfs(0, n);//从第0行开始递归
        return res;

    }
};

2. 数组保存法

这个方法用一个数组保存每个皇后所在的列，在递归完成的时候需要将结果转化为字符串，而这个方法在check的时候比较方便，只需要一句

class Solution {//两个方法。2. 数组保存法
    vector<vector<string>> res;//存最终结果
    vector<int> queensCol;//存当前棋盘每个皇后的列数
public:
    //检验当前位置放皇后是否符合要求
    bool check(vector<int> queensCol, int row, int col, int n){
        for(int i=0; i<row; ++i){//这里的i表示第i行
            //遇到同列的或者两个斜线的（斜线的按照正方形考虑，长宽一样）
            if(col == queensCol[i] || abs(row-i)==abs(col-queensCol[i])) return false;
        }
        return true;//未报错返回true
    }
    //dfs与回溯，当递归超出最后一行时将当前棋盘加入结果
    void dfs(int row, int n){
        //递归完成将结果转化为棋盘
        if(row>=n){
            vector<string> queens(n, string(n,'.'));
            for(int i=0; i<queensCol.size(); ++i){
                queens[i][queensCol[i]] = 'Q';
            }
            res.push_back(queens);
            return ;
        }
        //在当前行的每一列尝试放棋子
        for(int i=0; i<n; ++i){
            if(check(queensCol, row, i, n)){
                queensCol[row] = i;//在row行i列放棋子
                dfs(row+1, n);//递归下一行
                queensCol[row] = -1;//回溯时将放的棋子变回-1
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        queensCol = vector<int>(n,-1);//先将棋盘均设置为空
        dfs(0, n);//从第0行开始递归
        return res;

    }
};

2. 数组保存法

这个方法用一个数组保存每个皇后所在的列，在递归完成的时候需要将结果转化为字符串，而这个方法在check的时候比较方便，只需要一句

class Solution {//两个方法。2.数组保存法
    int res;//存最终结果
    vector<int> queensCol;//存当前棋盘
public:
    //检验当前位置放皇后是否符合要求
    bool check(vector<int> queensCol, int row, int col, int n){
        for(int i=0; i<row; ++i){//这里的i与row的差距，从row的上一行到第0行
            if(queensCol[i]==col || abs(row-i)==abs(col-queensCol[i])) return false;
        }
        return true;//未报错返回true
    }
    //dfs与回溯，当递归超出最后一行时将当前棋盘加入结果,结果+1
    void dfs(int row, int n){
        if(row>=n){
            res++;
            return ;
        }
        //在当前行的每一列尝试放棋子
        for(int i=0; i<n; ++i){
            if(check(queensCol, row, i, n)){
                queensCol[row] = i;//在row行i列放棋子
                dfs(row+1, n);//递归下一行
                queensCol[row] = -1;//回溯时将放的棋子变回'.'
            }
        }
    }

    int totalNQueens(int n) {
        queensCol = vector<int>(n,-1);//先将棋盘均设置为空
        dfs(0, n);//从第0行开始递归
        return res;
    }
};

3. bitmap法

这个方法时间复杂度没有减少，但是用了位运算速度更快，来自这里

class Solution {//三种方法。3.bitmap法，时间复杂度是一样的，但是用位运算更快，还没看明白，明天再看
public:
    int totalNQueens(int n) {
        //最开始所有位置都可以放
        dfs(n, 0, 0, 0, 0);
        
        return this->res;
    }
    
    void dfs(int n, int row, int col, int ld, int rd) {
        if (row >= n) { res++; return; }
        
        // 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
        //col:表示当前列的上面是否有皇后
        //ld:表示左上是否有皇后
        //rd:表示右上是否有皇后
        //以上都是1表示有
        //&之前是当前行能放皇后的地方，之后是总共皇后的位数
        //因为取反之后之超出n的0也变成1了，后半部分要保证位数
        int bits = ~(col | ld | rd) & ((1 << n) - 1);
        //当bits中还有1的时候继续遍历
        while (bits > 0) {
            int pick = bits & -bits; // 注: x & -x的作用是取最后一个1
            //更新col，为下一列这个位置放1；ld，下一列左边放1；rd，下一列右边放1
            dfs(n, row + 1, col | pick, (ld | pick) << 1, (rd | pick) >> 1);
            bits &= bits - 1; // 注: x & (x - 1)，将最后一个1变为0
        }
    }

private:
    int res = 0;
};

Contents

题目

题解

1. string保存法

2. 数组保存法

2. 数组保存法

3. bitmap法