• 训练营第二十七天 | 491.递增子序列46.全排列47.全排列 II332.重新安排行程51. N皇后

    491.递增子序列

    力扣题目链接(opens new window)

    给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

    示例:

    • 输入: [4, 6, 7, 7]
    • 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

    说明:

    • 给定数组的长度不会超过15。
    • 数组中的整数范围是 [-100,100]。
    • 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

    思路：

    1. class Solution {
    2. private:
    3.     vectorint>> result;
    4.     vector<int> path;
    5.     void backtracking(vector<int>& nums, int startindex) {
    6.         if (path.size() > 1) result.push_back(path);
    7.         for (int i = startindex; i < nums.size(); i++) {
    8.             if (i > startindex && nums[i] == nums[i - 1]) continue;  
    9.             // 跳过重复元素
    10.             if (path.empty() || nums[i] >= path.back()) {  
    11.                 // 确保递增顺序
    12.                 path.push_back(nums[i]);
    13.                 backtracking(nums, i + 1);
    14.                 path.pop_back();
    15.             }
    16.         }
    17.     }
    18. public:
    19.     vectorint>> findSubsequences(vector<int>& nums) {
    20.         result.clear();
    21.         path.clear();
    22.         backtracking(nums, 0);
    23.         return result;
    24.     }
    25. };

    初始代码：

    没有正确处理重复元素的情况。如果输入数组中有重复元素，直接跳过重复的元素，这样会遗漏一些合法的递增子序列。

    为了正确处理重复元素，需要在每一层递归中使用一个集合（如 unordered_set）来记录当前层中已经使用过的元素，以确保每个元素在每一层递归中只使用一次，但在不同的递归路径中可以使用相同的元素。

    unordered_set used;  // 使用集合来记录当前层使用过的元素

    if (used.find(nums[i]) != used.end()) continue;  // 当前层已经使用过的元素跳过

    if (path.empty() || nums[i] >= path.back()) {  // 确保递增顺序

    改正后的代码：

    1. class Solution {
    2. private:
    3.     vectorint>> result;
    4.     vector<int> path;
    5.     void backtracking(vector<int>& nums, int startindex) {
    6.         if (path.size() > 1) result.push_back(path);
    7.         unordered_set<int> used;  // 使用集合来记录当前层使用过的元素
    8.         for (int i = startindex; i < nums.size(); i++) {
    9.             if (used.find(nums[i]) != used.end()) continue;  // 当前层已经使用过的元素跳过
    10.             if (path.empty() || nums[i] >= path.back()) {  // 确保递增顺序
    11.                 used.insert(nums[i]);  // 记录当前元素
    12.                 path.push_back(nums[i]);
    13.                 backtracking(nums, i + 1);
    14.                 path.pop_back();
    15.             }
    16.         }
    17.     }
    18. public:
    19.     vectorint>> findSubsequences(vector<int>& nums) {
    20.         result.clear();
    21.         path.clear();
    22.         backtracking(nums, 0);
    23.         return result;
    24.     }
    25. };

    46.全排列

    力扣题目链接(opens new window)

    给定一个 没有重复 数字的序列，返回其所有可能的全排列。

    示例:

    • 输入: [1,2,3]
    • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

    思路：

    该题在回溯法的基础上加了一个used数组，存储数组对应元素是否使用过，以此作为条件判断是否将该数加入path。

    1.             if (used[i]) continue;
    2.             used[i] = true;
    3.             path.push_back(nums[i]);
    4.             backtrack(nums, used);
    5.             path.pop_back();
    6.             used[i] = false;

    同时，该题不需要startindex，因为每次循环都是将未加入path的所有元素依次遍历加入path。而是用used代替了，作为参数值传入backtrack函数。

    1. class Solution {
    2. private:
    3.     vectorint>> result;
    4.     vector<int> path; // 全局变量
    5.  
    6.     void backtrack(vector<int>& nums, vector<bool>& used) {
    7.         if (path.size() == nums.size()) {
    8.             result.push_back(path);
    9.             return;
    10.         }
    11.         for (int i = 0; i < nums.size(); i++) {
    12.             if (used[i]) continue;
    13.             used[i] = true;
    14.             path.push_back(nums[i]);
    15.             backtrack(nums, used);
    16.             path.pop_back();
    17.             used[i] = false;
    18.         }
    19.     }
    20.  
    21. public:
    22.     vectorint>> permute(vector<int>& nums) {
    23.         result.clear();
    24.         path.clear();
    25.         vector<bool> used(nums.size(), false);
    26.         backtrack(nums, used);
    27.         return result;
    28.     }
    29. };

    47.全排列 II

    力扣题目链接(opens new window)

    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

    示例 1：

    • 输入：nums = [1,1,2]
    • 输出： [[1,1,2], [1,2,1], [2,1,1]]

    示例 2：

    • 输入：nums = [1,2,3]
    • 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    提示：

    • 1 <= nums.length <= 8
    • -10 <= nums[i] <= 10

    思路：

    该题就多了一个去重操作。先给数组排序，然后还是使用used的方式递归。

    其中特别注意：if (i > 0 && nums[i] == nums[i - 1]&& !used[i - 1]) continue;中不要忘记“!used[i - 1]”。!used[i - 1]：确保在当前层级中，前一个相同元素没有被使用。如果前一个相同元素没有被使用，则跳过当前元素。这一步的目的是避免在同一层级中选择相同的元素，从而防止生成重复的排列。如果used[i - 1] == true。则同一树枝重复，是被允许的。

    1. class Solution {
    2.     private:
    3.     vectorint>> result;
    4.     vector<int> path;
    5.     void backtrack(vector<int>& nums, vector<bool>& used) {
    6.         if (path.size() == nums.size()) {
    7.             result.push_back(path);
    8.             return;
    9.         }
    10.         for (int i = 0; i < nums.size(); i++){
    11.             if (used[i]) continue;           
    12.             if (i > 0 && nums[i] == nums[i - 1]&& !used[i - 1]) continue;
    13.             used[i] = true;
    14.             path.push_back(nums[i]);
    15.             backtrack(nums, used);
    16.             path.pop_back();
    17.             used[i] = false;
    18.         }
    19.     }
    20. public:
    21.     vectorint>> permuteUnique(vector<int>& nums) {
    22.         vector<bool> used(nums.size(), false);
    23.         sort(nums.begin(), nums.end());
    24.         backtrack(nums, used);
    25.         return result;
    26.     }
    27. };

    332.重新安排行程

    力扣题目链接(opens new window)

    给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

    提示：

    • 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
    • 所有的机场都用三个大写字母表示（机场代码）。
    • 假定所有机票至少存在一种合理的行程。
    • 所有的机票必须都用一次 且 只能用一次。

    示例 1：

    • 输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
    • 输出：["JFK", "MUC", "LHR", "SFO", "SJC"]

    示例 2：

    • 输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    • 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
    • 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

    思路： 

    使用unordered_map> targets; 来记录航班的映射关系，定义为全局变量。参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。

    代码如下：

    1. // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    2. unordered_mapint>> targets;
    3. bool backtracking(int ticketNum, vector& result) {

    返回值用bool！

    因为只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，所以找到了这个叶子节点了直接返回。

    • 递归终止条件

    拿题目中的示例为例，输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。

    所以终止条件是：回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。

    • 单层搜索的逻辑

    在选择映射函数的时候，不能选择unordered_map> targets， 因为一旦有元素增删multiset的迭代器就会失效。

    可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。

    所以我选择了unordered_map> targets 来做机场之间的映射。

    1. class Solution {
    2. private:
    3. // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    4. unordered_mapint>> targets;
    5. bool backtracking(int ticketNum, vector& result) {
    6.     if (result.size() == ticketNum + 1) {
    7.         return true;
    8.     }
    9.     for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
    10.         if (target.second > 0 ) { // 记录到达机场是否飞过了
    11.             result.push_back(target.first);
    12.             target.second--;
    13.             if (backtracking(ticketNum, result)) return true;
    14.             result.pop_back();
    15.             target.second++;
    16.         }
    17.     }
    18.     return false;
    19. }
    20. public:
    21.     vector findItinerary(vector>& tickets) {
    22.         targets.clear();
    23.         vector result;
    24.         for (const vector& vec : tickets) {
    25.             targets[vec[0]][vec[1]]++; // 记录映射关系
    26.         }
    27.         result.push_back("JFK"); // 起始机场
    28.         backtracking(tickets.size(), result);
    29.         return result;
    30.     }
    31. };

    51. N皇后

    力扣题目链接(opens new window)

    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. class Solution {
    2. private:
    3.     vector> result;
    4.     
    5.     void backtrack(int n, int i, vectorchar>>& chessboard, vector<bool>& used) {
    6.         if (i == n) {
    7.             vector board;
    8.             for (const auto& row : chessboard) {
    9.                 board.push_back(string(row.begin(), row.end()));
    10.             }
    11.             result.push_back(board);
    12.             return;
    13.         }
    14.         for (int j = 0; j < n; j++) {
    15.             if (used[j] || !valid(i, j, chessboard, n)) continue;
    16.             chessboard[i][j] = 'Q'; // 放置皇后
    17.             used[j] = true;
    18.             backtrack(n, i + 1, chessboard, used);
    19.             chessboard[i][j] = '.'; // 回溯，撤销皇后
    20.             used[j] = false;
    21.         }
    22.     }
    23.  
    24.     bool valid(int i, int j, vectorchar>>& chessboard, int n) {
    25.         // 检查左上对角线
    26.         for (int k = i - 1, h = j - 1; k >= 0 && h >= 0; k--, h--) {
    27.             if (chessboard[k][h] == 'Q') return false;
    28.         }
    29.         // 检查右上对角线
    30.         for (int k = i - 1, h = j + 1; k >= 0 && h < n; k--, h++) {
    31.             if (chessboard[k][h] == 'Q') return false;
    32.         }
    33.         return true;
    34.     }
    35.  
    36. public:
    37.     vector> solveNQueens(int n) {
    38.         vectorchar>> chessboard(n, vector<char>(n, '.'));
    39.         vector<bool> used(n, false);
    40.         backtrack(n, 0, chessboard, used);
    41.         return result;
    42.     }
    43. };

    37. 解数独

    力扣题目链接(opens new window)

    编写一个程序，通过填充空格来解决数独问题。

    一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

    解数独

    一个数独。

    解数独

    答案被标成红色。

    提示：

    • 给定的数独序列只包含数字 1-9 和字符 '.' 。
    • 你可以假设给定的数独只有唯一解。
    • 给定数独永远是 9x9 形式的。

    思路：

    树枝是board的每一个空格，用双层for循环（行、列）遍历，如果等于‘.‘ ， 则填入数字。树层是每个空格可以填入的数字，可以设置一个辅助函数判断该数字是否符合要求， 若符合则继续填入下一个空格。其中特别注意，这个回溯函数是一个bool函数，因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

    找九宫格的时候，可以通过int startRow = (row / 3) * 3;找到特定位置。

    1. class Solution {
    2. private:
    3.     bool backtrack(vectorchar>>& board) {
    4.         for (int i = 0; i < 9; i++) {
    5.             for (int j = 0; j < 9; j++) {
    6.                 if (board[i][j] == '.') {
    7.                     for (char n = '1'; n <= '9'; n++) {
    8.                         if (valid(i, j, n, board)) {
    9.                             board[i][j] = n;
    10.                             if (backtrack(board)) {
    11.                                 return true;
    12.                             }
    13.                             board[i][j] = '.';
    14.                         }
    15.                     }
    16.                     return false;
    17.                 }
    18.             }
    19.         }
    20.         return true;
    21.     }
    22.  
    23.     bool valid(int row, int col, char val, vectorchar>>& board) {
    24.         for (int i = 0; i < 9; i++) {
    25.             if (board[row][i] == val) {
    26.                 return false;
    27.             }
    28.         }
    29.         for (int j = 0; j < 9; j++) {
    30.             if (board[j][col] == val) {
    31.                 return false;
    32.             }
    33.         }
    34.         int startRow = (row / 3) * 3;
    35.         int startCol = (col / 3) * 3;
    36.         for (int i = startRow; i < startRow + 3; i++) {
    37.             for (int j = startCol; j < startCol + 3; j++) {
    38.                 if (board[i][j] == val) {
    39.                     return false;
    40.                 }
    41.             }
    42.         }
    43.         return true;
    44.     }
    45.  
    46. public:
    47.     void solveSudoku(vectorchar>>& board) {
    48.         backtrack(board);
    49.     }
    50. };

  • 相关阅读:
    工作流编排引擎-Temporal
    分析每一段的代码的代码及代码运行的结果
    JavaScript（一）基本语法概念
    如何用架构的思维为云原生做减法？
    苹果对高通说：我4.45亿美元买下一个新园区，可能计划加快基带芯片自研
    Linux C语言进阶
    建造者模式
    C专家编程 第8章 为什么程序员无法分清万圣节和圣诞节 8.5 原型在什么地方会失败
    弘辽科技：抖音，正在抛弃张同学
    阿里云 linux tomcat 无法访问方法
  • 原文地址：https://blog.csdn.net/weixin_44824156/article/details/139383869