网站模板兼容手机端,最近很火的营销事件,wordpress加首页,网站开发开源代码题意
给定一个数字 n n n#xff0c;形成n*n的棋盘#xff0c;棋盘上放n个皇后#xff0c;确保皇后之间不会相互吃#xff08;皇后可以直线吃#xff0c;斜线吃#xff09;
链接
https://leetcode.com/problems/n-queens/description/
思考
这道题只能暴力枚举所有的…题意
给定一个数字 n n n形成n*n的棋盘棋盘上放n个皇后确保皇后之间不会相互吃皇后可以直线吃斜线吃
链接
https://leetcode.com/problems/n-queens/description/
思考
这道题只能暴力枚举所有的位置但是如果直接在二维矩阵上做空间复杂度比较高可以降维度
题解
dfs枚举所有可以放n皇后的地方。构造一个数组pos, p o s [ i ] pos[i] pos[i]代表在第i行第pos[i]列放一个皇后。 结束条件为当pos数组长度为n根据pos数组构造二维的答案 传入参数u表示当前pos数组添加到第几个元素实际上是第u行皇后应该放在什么位置遍历这个元素所有的可能性0-n 列并且判断新放入皇后是否和前面所有的皇后列数相同是否和前面所有的皇后在同一个对角线上如果不在那么第u位就选了要选择第u1位元素注意回溯。
对角线性质 class Solution {
public:vectorvectorstring res; vectorvectorstring solveNQueens(int n) {//pos保证所有的n queens不可能在同一行所以循环中只需要check//是不是同一列或者斜对角就可以vectorint pos;dfs(0, pos, n);return res;}void dfs(int u, vectorint pos, int n) {if( u n ) {vectorstring str(n, string(n, .));for(int i 0; i n; i) {str[i][pos[i]] Q;}res.push_back(str);return;}for(int i 0; i n; i) {if(isValid(pos,u, i)) {pos.push_back(i);dfs(u1, pos, n);pos.pop_back();}}}bool isValid(vectorint pos, int row, int col) {int m pos.size();for(int i 0; i m; i) {int preRow i;int preCol pos[i];if(col preCol) return false;if(abs(row-preRow) abs(col - preCol)) return false;}return true;}
};时间复杂度 O ( N 2 ∗ N ! ) O(N^2* N!) O(N2∗N!) 空间复杂度 O ( N ) O(N) O(N)
N Queens II是统计所有不同的方案数一样的解法
class Solution {
public:int cnt 0;int totalNQueens(int n) {vectorint pos;dfs(0, pos, n);return cnt;}void dfs(int u, vectorint pos, int n) {if( u n) {cnt;return;}static vectorbool col(n, false);static vectorbool diag(2*n-1, false);static vectorbool udiag(2*n-1, false); for(int i 0; i n; i) {int r u;int c i;if(!col[c] !diag[rc] !udiag[r-cn-1]) {pos.push_back(i);col[c] diag[rc] udiag[r-cn-1] true;dfs(u1, pos, n);col[c] diag[rc] udiag[r-cn-1] false;pos.pop_back();}}}
};时间复杂度 O ( N 2 ∗ N ! ) O(N^2* N!) O(N2∗N!) 空间复杂度 O ( N ) O(N) O(N)
