网站优化关键词排名公司,赤壁网站建设,做网站如何不被忽悠,西安企业家名单Leetcode 51. N皇后
题目链接#xff1a;51 N皇后 题干#xff1a;按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整…Leetcode 51. N皇后
题目链接51 N皇后 题干按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 思考回溯法。先定义结果集result再考虑回溯函数
函数参数含义 参数含义n题目给定皇后个数chessboard当前棋盘摆放情况row当前处理行数 终止条件如果当前处理行数row等于n时说明皇后已全部摆放完毕将当前棋盘摆放情况chessboard存放到结果集result中。
单层搜索逻辑从下标0开始循环处理每个二维坐标位置若当前行row当前列col存放皇后合法则摆放皇后递归处理最后回溯。
验证row行col列摆放皇后合法性参数当前行列值当前棋盘以及皇后个数。三处标准判断合法性不能同行每次处理都是不同行故此标准不用验证、不能同列、不能同斜线 45度和135度角。
判断同列当前row行前面的所以行对应的col列是否摆放过皇后判断45°线当前row行col列45°斜方向是否摆放过皇后判断135°线当前row行col列135°斜方向是否摆放过皇后
代码
class Solution {
public:vectorvectorstring result;//n : 皇后个数 chessboard : 当前棋盘摆放情况 row : 当前处理行数void backtracking(const int n, vectorstring chessboard, int row) {if (row n) {result.push_back(chessboard);return;}for (int col 0; col n; col) {if (isValid(n, chessboard, row, col)) {chessboard[row][col] Q; //摆放皇后backtracking(n, chessboard, row 1);chessboard[row][col] .; //回溯}}}//判断row行col列摆放皇后是否合法bool isValid(const int n, vectorstring chessboard, int row, int col) {//检查此行是否摆放过皇后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;}vectorvectorstring solveNQueens(int n) {result.clear();vectorstring chessboard(n, string(n, .));backtracking(n, chessboard, 0);return result;}
};
回溯法专题总结 熟悉回溯法代码整体框架。把回溯问题抽象为树形结构其搜索的过程for循环横向遍历递归纵向遍历回溯不断调整结果集。确定是否使用startIndex。对于组合问题如果是一个集合来求组合的话就需要startIndex如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex。熟悉同层去重两种方式。排序后相邻元素比较以及set容器记录使用情况。了解到节点去重但未归纳。明确在树形结构中子集问题是要收集所有节点的结果而组合问题是收集叶子节点的结果。
