• 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的地方)

    1. class Solution {
    2. public:
    3. vectorint>> res;
    4. vectorint>> permute(vector<int>& nums) {
    5. vector<int> track;//记录路径
    6. vector<bool> used(nums.size(),false);
    7. backTrack(nums,track,used);
    8. return res;
    9. }
    10. void backTrack(vector<int>& nums,vector<int>& track,vector<bool>& used)
    11. {
    12. if(track.size()==nums.size())//触发结束条件
    13. {
    14. res.push_back(track);
    15. return ;
    16. }
    17. for(int i=0;isize();i++)
    18. {
    19. if(used[i])//排除不合法的选择
    20. {
    21. continue;
    22. }
    23. //前序遍历,做选择
    24. track.push_back(nums[i]);
    25. used[i]=true;
    26. backTrack(nums,track,used);
    27. //后序遍历,取消选择
    28. track.pop_back();
    29. used[i]=false;
    30. }
    31. }
    32. };

    51.N皇后

    按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    输入:n = 4
    输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    解释:如上图所示,4 皇后问题存在两个不同的解法。

    思路:回溯算法

    从上到下、从左到右遍历棋盘的每一格,做出“此位置是否可以放置皇后”的选择

    回溯算法形成的决策树中,row代表决策树的一层col代表决策树的一个结点衍生出的分支

     以四皇后为例,回溯的决策树如下:

     

    1. class Solution {
    2. public:
    3. vector> res;
    4. vector> solveNQueens(int n) {
    5. vector broad(n,string(n,'.'));//初始化一个全为空的棋盘
    6. backTrack(broad,0);
    7. return res;
    8. }
    9. // 路径:board 中小于 row 的行都已经成功放置了皇后
    10. // 选择列表:第 row 行的所有列(0<=col<=n-1)都是放置皇后的选择
    11. // 结束条件:row 超过 board 的最后一行
    12. void backTrack(vector& broad,int row)
    13. {
    14. //触发结束条件
    15. if(row==broad.size())
    16. {
    17. res.push_back(broad);
    18. return ;
    19. }
    20. for(int col=0;colsize();col++)
    21. {
    22. if(!canPutQ(broad,row,col))//排除不合法的选择
    23. {
    24. continue;
    25. }
    26. broad[row][col]='Q';//做选择
    27. backTrack(broad,row+1);//进入下一行的决策
    28. broad[row][col]='.';//撤销选择
    29. }
    30. }
    31. //是否可以在 board[row][col] 放置皇后
    32. bool canPutQ(vector& broad,int row,int col)
    33. {
    34. for(int i=0;i<=row;i++)//检查上方的格子
    35. {
    36. if(broad[i][col]=='Q')//有冲突
    37. return false;
    38. }
    39. for(int i=row-1,j=col+1;i>=0&&jsize();i--,j++)//检查右上方的格子
    40. {
    41. if(broad[i][j]=='Q')//有冲突
    42. return false;
    43. }
    44. for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)//检查左上方的格子
    45. {
    46. if(broad[i][j]=='Q')//有冲突
    47. return false;
    48. }
    49. return true;
    50. }
    51. };
  • 相关阅读:
    飞行器动力学和控制项目(Matlab代码实现)
    经典论文《Efficient Estimation of Word Representations in Vector Space》学习笔记
    Redis 非关系型数据库学习(三)---- Redis 基础知识
    对vue的mixin的理解,有什么应用场景?面试题!!!
    HTML标签---表格
    币圈必备资讯插件
    【IEEE出版顺利申请中】2024年第四届电子信息工程与计算机科学国际会议(EIECS 2024)
    【C++的OpenCV】第十四课-OpenCV基础强化(二):访问单通道Mat中的值
    Kubernetes PDB
    如何解决d3dcompiler_43.dll丢失问题?d3dcompiler_43.dll丢失修复方法
  • 原文地址:https://blog.csdn.net/weixin_50437588/article/details/126613000