首页 > 代码库 > Leetcode: N-Queens II C++

Leetcode: N-Queens II C++

2024-07-15 06:50:12   215人阅读

class Solution {public:    int totalNQueens(int n) {        //initialize chessboard        vector<vector<bool>> boardconf;        vector<bool> orig_row;        orig_row.assign(n,false);        boardconf.assign(n,orig_row);        int totalNum = 0;        for(int j = 0; j < n; j++){            totalNum+= NQueens(boardconf,0,j,n);        }        return totalNum;            }    int NQueens(vector<vector<bool>> cb, int i, int j,int n){        if(i == n-1){            if(not_attack(cb,i,j,n)) return 1;            else return 0;        }else{            if(not_attack(cb,i,j,n)){                int tmp = 0;                for(int k = 0; k < n; k++){                    tmp = NQueens(cb,i+1,k,n);                }                return tmp;            }else return 0;        }    }    bool not_attack(vector<vector<bool>> cb, int row, int col,int n){        int i = 0;        while(i < row){            if(cb[i][col]) return false;            i++;        }        i = row - 1;        int j = col - 1;        while(i >= 0 && j >= 0){            if(cb[i][j]) return false;            i--;            j--;        }        i = row - 1;        j = col + 1;        while(i >= 0 && j < n){            if(cb[i][j]) return false;            i--;            j++;        }        return true;    }};

上面的答案是我提交的第一个版本，提交后显示“Time Limit Exceed”。"Time Limit Exceed" 一般意味着算法复杂度太高，所以我首先检查是否是所用递归方法的问题。我看了一些网上关于此题的解答，都是递归的思路，所以排除了递归是造成超时的主要原因。继而我对所用数据结构分析，上面的解法要维护一个n*n的chessboad configuration，并且递归每深入一层都要copy上一层的chessboard configuration。这是很耗时间的。其实在判断某个位置是否可以放Queen时，我们并不需要维护一个完整的chessboard，因为我们只用判断(i,j)所处的主对角线、反对角线、列是否已经有Queen，所以我们可以用三个数组分别记录对应的主对角线、反对角线、列是否已经有Queen即可。

不过里面有个小trick需要注意，当i层的递归结束之后，我们需要把记录主对角线、反对角线、列的三个数组复原。

class Solution {public:    int totalNQueens(int n) {        this->columns = vector<bool>(n,false);        this->main_diag = vector<bool>(2*n-1,false);        this->anti_diag = vector<bool>(2*n-1,false);        int totalNum = 0;        for(int j = 0; j < n; j++){            totalNum+= NQueens(0,j,n);        }        return totalNum;            }    int NQueens(int i, int j,int n){        if(i == n-1){            if(!(columns[j]||main_diag[i-j+n-1]||anti_diag[i+j]))                return 1;            else return 0;        }else{            if(!(columns[j]||main_diag[i-j+n-1]||anti_diag[i+j])){                columns[j]=true;                main_diag[i-j+n-1]=true;                anti_diag[i+j]=true;                int tmp = 0;                for(int k = 0; k < n; k++){                    tmp += NQueens(i+1,k,n);                }                columns[j]=false;                main_diag[i-j+n-1]=false;                anti_diag[i+j]=false;                return tmp;            }else return 0;        }    }private:    vector<bool> columns;    vector<bool> main_diag;    vector<bool> anti_diag;    };

 


联系
我们