深圳网站设计专家乐云seo品牌,深圳服装设计公司排名前十强,网站自适应手机代码,住房和城乡建设部建造师网站按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。
给你一个整数 n #xff0c;返回所有不同的 n 皇后问题 的解决方案。
每一种…按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
示例 1 输入n 4 输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]] 解释如上图所示4 皇后问题存在两个不同的解法。
示例 2
输入n 1 输出[[Q]]
提示
1 n 9已经不是第一次遇到 N 皇后问题了依稀记得三年前的暑假刚接触 c的自己看着 N 皇后别人 AC 掉的代码天书一般留下的知识满眼的钦佩
愿与君共勉
事实上现在看来N 皇后问题相比其他的回溯算法题hard点在于它使用的是二维数组回溯的思路是不变的
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}参数选择 - 回溯终止条件 - 单层处理logic
值得一提的是 每列棋子放置的合理性判别即 isValid的函数实现。 AC
/** lc appleetcode.cn id51 langcpp** [51] N 皇后*/// lc codestart
class Solution {
private:vectorvectorstring result;bool isValid(int row, int col, vectorstring chessboard, int n) {// 检查列for(int i 0; i row; i) {if(chessboard[i][col] 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;}void backtracking(int n, int row, vectorstring chessboard) {if(n row) {result.push_back(chessboard);return ;}for(int col 0; col n; col) {if(isValid(row, col, chessboard, n)) {chessboard[row][col] Q;backtracking(n, row 1, chessboard);chessboard[row][col] .;}}}
public:vectorvectorstring solveNQueens(int n) {result.clear();std::vectorstd::string chessboard(n, std::string(n, .));backtracking(n, 0, chessboard);return result;}
};
// lc codeend【补充】cpp 哈希表 C中哈希表可以分为以下几类
unordered_map 基于哈希表实现的 Key-Value 映射容器支持快速的插入、查找和删除操作。
下面是 unordered_map 常见的使用方式
#include unordered_map
#include string
using namespace std;int main() {// 创建一个空的unordered_mapunordered_mapstring, int umap;// 插入元素umap[apple] 10;umap.insert(make_pair(orange, 20));// 访问元素int apple_price umap[apple];int orange_price umap.at(orange);// 遍历元素for (auto it umap.begin(); it ! umap.end(); it) {cout it-first : it-second endl;}// 删除元素umap.erase(apple);umap.clear();return 0;
}unordered_set 基于哈希表实现的无序集合容器支持快速的插入、查找和删除操作。和 unordered_map 相似只是不需要存储键值对。
下面是 unordered_set 常见的使用方式
#include unordered_set
#include string
using namespace std;int main() {// 创建一个空的unordered_setunordered_setstring uset;// 插入元素uset.insert(apple);uset.insert(orange);// 查找元素if (uset.find(apple) ! uset.end()) {cout Found apple! endl;}// 遍历元素for (auto it uset.begin(); it ! uset.end(); it) {cout *it endl;}// 删除元素uset.erase(apple);uset.clear();return 0;
}unordered_multimap 基于哈希表实现的 Key-Value 映射容器支持插入重复的 Key每个 Key 对应多个 Value。和 unordered_map 相似只是可以插入重复 Key 和多个 Value。
下面是 unordered_multimap 常见的使用方式
#include unordered_map
#include string
using namespace std;int main() {// 创建一个空的unordered_multimapunordered_multimapstring, int umap;// 插入元素umap.insert(make_pair(apple, 10));umap.insert(make_pair(orange, 20));umap.insert(make_pair(apple, 30));// 访问元素auto range umap.equal_range(apple);for (auto it range.first; it ! range.second; it) {cout it-first : it-second endl;}// 遍历元素for (auto it umap.begin(); it ! umap.end(); it) {cout it-first : it-second endl;}// 删除元素umap.erase(apple);umap.clear();return 0;
}unordered_multiset 基于哈希表实现的无序集合容器支持插入重复的元素。和 unordered_set 相似只是可以插入重复元素。
下面是 unordered_multiset 常见的使用方式
#include unordered_set
#include string
using namespace std;int main() {// 创建一个空的unordered_multisetunordered_multisetstring uset;// 插入元素uset.insert(apple);uset.insert(orange);uset.insert(apple);// 查找元素if (uset.count(apple) 0) {cout Found apple! endl;}// 遍历元素for (auto it uset.begin(); it ! uset.end(); it) {cout *it endl;}// 删除元素uset.erase(apple);uset.clear();return 0;
}以上是哈希表的四种常见用法需要根据具体业务场景选择相应的容器。
