【回溯+剪枝】优美的排列 N皇后(含剪枝优化)
文章目录
- 526. 优美的排列
- 解题思路：回溯 + 剪枝
- 51. N 皇后
- 解题思路：回溯 + 剪枝
- 剪枝的优化
526. 优美的排列
526. 优美的排列
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
perm[i]能够被i整除i能够被perm[i]整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
示例 1：
输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 15
解题思路：回溯 + 剪枝
首先这道题我一开始就掉进一个坑，代码基本是正确的，但是因为题目漏了细节：只要满足优美排列的条件之一即可！我以为两个条件都得满足，导致花费了很长时间思考，所以审题很重要……
其实这道题并不难，是一个排列问题，就是要我们找到不同顺序的满足 n 个元素的数组，判断它是否为优美的排列，如果我们是到了叶子节点，然后遍历排列结果去判断是否为优美的排列的话，其实是非常麻烦的，所以我们可以考虑 边遍历边判断！
就是当我们遍历到一个元素的时候，此时我们只要有当前构造到数组的尾部下标的话，就可以判断是否满足优美的排序，如果不是的话直接跳过该元素的选择即可达到剪枝的效果，所以我们 需要在递归函数中多加一个参数 tail 表示当前构造到数组的尾部下标，它从下标 1 开始计算！而其实有了这个下标，我们边遍历边判断的话，其实就可以省略数组空间来存放叶子节点了，因为我们在遍历途中已经完成了判断！
然后因为是排列问题，所以 需要有一个 used 数组来标记哪个元素已经走过了，防止重复，我们还是老样子，将其设为全局变量即可！
剩下的就是递归函数出口问题，当我们构造的数组下标超过 n 个的时候，此时因为前面已经是筛选过满足要求的元素了，现在还超过了 n 个，说明这是满足要求的结果，则让 ret++ 然后进行返回即可！
class Solution {
private:
int ret; // 结果集
bool used[16]; // 标记哪个元素已经走过，防止重复
public:
int countArrangement(int n) {
dfs(n, 1);
return ret;
}
// tail表示当前构造到数组的尾部下标，从1开始
void dfs(int n, int tail)
{
// 递归函数出口
if(tail > n)
{
ret++;
return;
}
for(int i = 1; i <= n; ++i)
{
// 剪枝
if((used[i] == true) || ((i % tail != 0) && (tail % i != 0)))
continue;
used[i] = true;
dfs(n, tail + 1);
used[i] = false;
}
}
};
51. N 皇后
51. 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
解题思路：回溯 + 剪枝
我们之前都是在一维的角度去看待这个回溯问题的，比如说组合问题的 [1, 2, 2] 等等，但是这道题很明显是一个二维问题，一个棋盘既有行又有列，这一下子让我们有点不知从何下手，但是其实我们分析一下还是可以发现，我们之前将的回溯的树形结构其实也是一个类似二维的情况，对于本题来说只不过是空间变成了二维而已！
首先来看⼀下皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树，下面用一个 4*4 的棋牌，将搜索过程抽象为一颗树，如图：
可以发现只要我们用皇后们的约束条件，来回溯搜索这颗树，期间发现不满足要求的就可以直接剪枝跳过，而一旦搜索到了树的叶子节点，说明就找到了皇后们的合理位置了，就将其加入结果集！
- 函数头的设计：
- 还是一样，定义一个全局变量二维数组
ret来记录最终结果。然后用n表示棋盘的宽和高，用row来记录当前遍历到棋盘的第几层了，还有一个一维字符串数组也就相当于一个二维数组board作为当前棋盘。
- 还是一样，定义一个全局变量二维数组
- 递归函数出口：
- 很可以看出，只有到棋盘最下沿也就是叶子节点的时候，我们才能得到这个有效的棋盘，也就是
row == n的时候，进行结果集的添加以及返回！
- 很可以看出，只有到棋盘最下沿也就是叶子节点的时候，我们才能得到这个有效的棋盘，也就是
- 函数体的内容：
- 首先需要判断当前这个棋盘中该位置摆放后，它的行、列、斜线上是否已经存在皇后了，存在的话则直接
continue跳过该位置。 - 然后该位置如果摆放是合法的话，则直接将该位置的字符改为
Q，然后继续递归，最后回溯要将字符改为.即可。
- 首先需要判断当前这个棋盘中该位置摆放后，它的行、列、斜线上是否已经存在皇后了，存在的话则直接
另外我们还得做其它的工作就是判断棋盘是否合法：
- 不能同行
- 不能同列
- 不能同斜线 （
45度和135度角）
但其实我们并 不需要进行同行的判断，因为在单层搜索的过程中，每一层递归，只会选 for 循环（也就是同一行）里的一个元素，所以不用行去重了。除此之外，对于就是 在判断列和斜线的时候，我们其实只需要判断到当前行的上方部分即可，因为当前递归的时候，说明还没递归到下一层！
class Solution {
private:
vector<vector<string>> ret; // 存放结果集
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.')); // 进行棋盘初始化
dfs(board, n, 0);
return ret;
}
void dfs(vector<string>& board, int n, int row)
{
// 递归函数出口
if(row >= n)
{
ret.push_back(board);
return;
}
for(int col = 0; i < col; ++i)
{
// 先判断当前下棋位置是否符合要求，不符合直接跳过，相当于剪枝
if(validate(board, n, row, col) == false)
continue;
// 回溯三部曲
board[row][col] = 'Q';
dfs(board, n, row + 1);
board[row][col] = '.';
}
}
// 检查当前位置是否符合规则（不需要检查行，因为上面的dfs迭代已经进行了回溯操作）
bool validate(vector<string>& board, int n, int x, int y)
{
// 检查列
for(int i = 0; i < x; ++i)
if(board[i][y] == 'Q')
return false;
// 检查斜线
for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; --i, --j)
if(board[i][j] == 'Q')
return false;
for(int i = x - 1, j = y + 1; i >= 0 && j < n; --i, ++j)
if(board[i][j] == 'Q')
return false;
return true;
}
};
剪枝的优化
其实对于剪枝操作，我们是可以进行优化的，上面我们的剪枝操作，其实是直接遍历棋盘中对应的列、斜线上是否有出现过棋子，但其实可以不用每次都去遍历这些位置，而是 通过布尔值类型的数组，记录下当前斜线、列是否出现过棋子，出现过的话就直接跳过即可，这个判断速度是很快的，就是 O(1) 级别的，就是哈希的思想，用空间换时间！
对于列的判断其实还好说，就是个简单的一维数组 col_used，其中 col_used[i] 为 true 就表示第 i 列已经存在元素了，则此时直接跳过即可，要做到这个设置并不难，因为我们下棋是往下走的，所以往下走的时候就可以顺便进行 col_used[i] 的设置了！
但是对于斜线上来判断是否存在就不好搞了，这里就要借用我们学过的一次函数，一次函数中斜率为 -1 和 1 的时候，其实就可以对应为矩阵中的主对角线和副对角线，如下图所示：
对于副对角线来说，因为 y = x + b，可以得到 y - x = b，所以截距其实就是一个定值，根据这个定制，我们就能固定一条对角线上无论 y 和 x 怎么变化都能找出固定的截距，也就是一个参照值，用来记录当前对角线是否存在棋子！
但是副对角线的下三角部分的截距小于零了，会造成数组越界，所以我们统一让等式两边都加上棋盘的宽度，最后得到 y - x + n = b + n。
也就是说我们 只需要判断副对角线数组 minor_diag[y - x + n] 是否为 true，为 true 表示存在元素，然后别忘了这个对角线数组因为加了 n，所以 在开辟的时候大小是 2*n。
对于主对角线也是如此，不过因为主对角线最小截距为一，所以不需要关心越界问题，但是因为其等式为 y = -x + b，得到 y + x = b，那么我们判断的依据就是 判断主对角线数组 main_diag[y + x] 是否为 true，是的话则直接跳过，但是此时如果 x 或者 y 大于 n 的话也是会越界，所以同样 也需要让主对角线数组 main_diag 在开辟的时候大小是 2*n！
class Solution {
private:
vector<vector<string>> ret; // 存放结果集
bool col_used[10]; // 表示列是否有棋子
bool main_diag[20]; // 表示主对角线是否有棋子
bool minor_diag[20]; // 表示次对角线是否有棋子
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.')); // 进行棋盘初始化
dfs(board, n, 0);
return ret;
}
void dfs(vector<string>& board, int n, int row)
{
// 递归函数出口
if(row >= n)
{
ret.push_back(board);
return;
}
for(int col = 0; col < n; ++col)
{
// 进行剪枝处理，判断是否位置有效
if(col_used[col] == true ||
main_diag[row + col] == true ||
minor_diag[row - col + n] == true)
continue;
// 回溯三部曲
board[row][col] = 'Q';
col_used[col] = main_diag[row + col] = minor_diag[row - col + n] = true;
dfs(board, n, row + 1);
col_used[col] = main_diag[row + col] = minor_diag[row - col + n] = false;
board[row][col] = '.';
}
}
};