46.全排列 | 51.N皇后
46.全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1]
输出:[[1]]
回溯算法解题套路框架 :: labuladong的算法小抄 (gitee.io)
回溯算法,在for循环中(无法遍历到根结点)做选择和取消选择,其实是在处理决策树的树枝
DFS,在for循环外做选择和取消选择,其实是在处理决策树的结点
决策树
在for循环遍历的过程中,需要利用used数组,避免重复遍历 (下图打x的地方)
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> track;//记录路径
vector<bool> used(nums.size(),false);
backTrack(nums,track,used);
return res;
}
void backTrack(vector<int>& nums,vector<int>& track,vector<bool>& used)
{
if(track.size()==nums.size())//触发结束条件
{
res.push_back(track);
return ;
}
for(int i=0;i<nums.size();i++)
{
if(used[i])//排除不合法的选择
{
continue;
}
//前序遍历,做选择
track.push_back(nums[i]);
used[i]=true;
backTrack(nums,track,used);
//后序遍历,取消选择
track.pop_back();
used[i]=false;
}
}
};
51.N皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
思路:回溯算法
从上到下、从左到右遍历棋盘的每一格,做出“此位置是否可以放置皇后”的选择
回溯算法形成的决策树中,row代表决策树的一层,col代表决策树的一个结点衍生出的分支
以四皇后为例,回溯的决策树如下:
class Solution {
public:
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
vector<string> broad(n,string(n,'.'));//初始化一个全为空的棋盘
backTrack(broad,0);
return res;
}
// 路径:board 中小于 row 的行都已经成功放置了皇后
// 选择列表:第 row 行的所有列(0<=col<=n-1)都是放置皇后的选择
// 结束条件:row 超过 board 的最后一行
void backTrack(vector<string>& broad,int row)
{
//触发结束条件
if(row==broad.size())
{
res.push_back(broad);
return ;
}
for(int col=0;col<broad.size();col++)
{
if(!canPutQ(broad,row,col))//排除不合法的选择
{
continue;
}
broad[row][col]='Q';//做选择
backTrack(broad,row+1);//进入下一行的决策
broad[row][col]='.';//撤销选择
}
}
//是否可以在 board[row][col] 放置皇后
bool canPutQ(vector<string>& broad,int row,int col)
{
for(int i=0;i<=row;i++)//检查上方的格子
{
if(broad[i][col]=='Q')//有冲突
return false;
}
for(int i=row-1,j=col+1;i>=0&&j<broad.size();i--,j++)//检查右上方的格子
{
if(broad[i][j]=='Q')//有冲突
return false;
}
for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)//检查左上方的格子
{
if(broad[i][j]=='Q')//有冲突
return false;
}
return true;
}
};