训练营第二十七天 | 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]。
  • 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

思路：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startindex) {
        if (path.size() > 1) result.push_back(path);
        for (int i = startindex; i < nums.size(); i++) {
            if (i > startindex && nums[i] == nums[i - 1]) continue;  
            // 跳过重复元素
            if (path.empty() || nums[i] >= path.back()) {  
                // 确保递增顺序
                path.push_back(nums[i]);
                backtracking(nums, i + 1);
                path.pop_back();
            }
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

初始代码：

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

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

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

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

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

改正后的代码：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startindex) {
        if (path.size() > 1) result.push_back(path);
        unordered_set<int> used;  // 使用集合来记录当前层使用过的元素
        for (int i = startindex; i < nums.size(); i++) {
            if (used.find(nums[i]) != used.end()) continue;  // 当前层已经使用过的元素跳过
            if (path.empty() || nums[i] >= path.back()) {  // 确保递增顺序
                used.insert(nums[i]);  // 记录当前元素
                path.push_back(nums[i]);
                backtracking(nums, i + 1);
                path.pop_back();
            }
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

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。

            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used);
            path.pop_back();
            used[i] = false;

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

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path; // 全局变量

    void backtrack(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtrack(nums, used);
        return result;
    }
};

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。则同一树枝重复，是被允许的。

class Solution {
    private:
    vector<vector<int>> result;
    vector<int> path;
    void backtrack(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++){
            if (used[i]) continue;           
            if (i > 0 && nums[i] == nums[i - 1]&& !used[i - 1]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, used);
        return result;
    }
};

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<string, map<string, int>> targets; 来记录航班的映射关系，定义为全局变量。参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。

代码如下：

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

返回值用bool！

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

  • 递归终止条件

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

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

  • 单层搜索的逻辑

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

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

所以我选择了unordered_map<string, map<string, int>> targets 来做机场之间的映射。

class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

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"]]

class Solution {
private:
    vector<vector<string>> result;
    
    void backtrack(int n, int i, vector<vector<char>>& chessboard, vector<bool>& used) {
        if (i == n) {
            vector<string> board;
            for (const auto& row : chessboard) {
                board.push_back(string(row.begin(), row.end()));
            }
            result.push_back(board);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (used[j] || !valid(i, j, chessboard, n)) continue;
            chessboard[i][j] = 'Q'; // 放置皇后
            used[j] = true;
            backtrack(n, i + 1, chessboard, used);
            chessboard[i][j] = '.'; // 回溯，撤销皇后
            used[j] = false;
        }
    }

    bool valid(int i, int j, vector<vector<char>>& chessboard, int n) {
        // 检查左上对角线
        for (int k = i - 1, h = j - 1; k >= 0 && h >= 0; k--, h--) {
            if (chessboard[k][h] == 'Q') return false;
        }
        // 检查右上对角线
        for (int k = i - 1, h = j + 1; k >= 0 && h < n; k--, h++) {
            if (chessboard[k][h] == 'Q') return false;
        }
        return true;
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<char>> chessboard(n, vector<char>(n, '.'));
        vector<bool> used(n, false);
        backtrack(n, 0, chessboard, used);
        return result;
    }
};

37. 解数独

力扣题目链接(opens new window)

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

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

解数独

一个数独。

解数独

答案被标成红色。

提示：

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

思路：

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

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

class Solution {
private:
    bool backtrack(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char n = '1'; n <= '9'; n++) {
                        if (valid(i, j, n, board)) {
                            board[i][j] = n;
                            if (backtrack(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool valid(int row, int col, char val, vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val) {
                return false;
            }
        }
        for (int j = 0; j < 9; j++) {
            if (board[j][col] == val) {
                return false;
            }
        }
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board);
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/683375.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

企业（园区）智慧能源双碳平台解决方案

企业（园区）智慧能源双碳平台解决方案

园区作为工业企业集聚区&#xff0c;在提供了大量基础设施和公共服务的同时也成为了碳排放的主要源头。工业园区的耗能约占全社会总耗能的69%&#xff0c;碳排放占全国总排放约31%。工业园区节能、减耗、提质、减碳工作的落实&#xff0c;是我国实现碳达峰碳中和目标的必然要求…
阅读更多...
关系代数与规范化

关系代数与规范化

本文是根据自己的理解&#xff0c;结合实践整理所得&#xff0c;有兴趣的可以参考学习。
阅读更多...
P3. 创建个人中心页面

P3. 创建个人中心页面

P3. 创建个人中心页面 0 概述Tips1 个人中心页面1.1 创建 Bot 表及 pojo, mapper1.2 实现 Bot 增删改查的 API1.3 实现个人中心页面前端 0 概述 主要介绍了一下添加一个表(类)&#xff0c;及其CRUD的前端和后端的实现方式&#xff0c;介绍的是通用的方法。 后端的CRUD很好写&am…
阅读更多...
TCP/IP协议介绍——三次握手四次挥手

TCP/IP协议介绍——三次握手四次挥手

TCP/IP&#xff08;Transmission Control Protocol/Internet Protocol&#xff0c;传输控制协议/网际协议&#xff09;是指能够在多个不同网络间实现信息传输的协议簇。TCP/IP协议不仅仅指的是TCP 和IP两个协议&#xff0c;而是指一个由FTP、SMTP、TCP、UDP、IP等协议构成的协议…
阅读更多...
Capture One Pro 23：专业 Raw 图像处理的卓越之选

Capture One Pro 23：专业 Raw 图像处理的卓越之选

在当今的数字摄影时代&#xff0c;拥有一款强大的图像处理软件至关重要。而 Capture One Pro 23 for Mac/Win 无疑是其中的佼佼者&#xff0c;为摄影师和图像爱好者带来了前所未有的体验。 Capture One Pro 23 以其出色的 Raw 图像处理能力而闻名。它能够精准地解析和处理各种…
阅读更多...
Priority_queue

Priority_queue

一、priority_queue的介绍和使用 1.1 priority_queue的介绍 1.优先队列是一种容器适配器&#xff0c;根据严格的弱排序标准&#xff0c;它的第一个元素总是它所包含的元素中最大的。 2.优先队列类似于堆&#xff0c; 在堆中可以随时插入元素&#xff0c; 并且只能检索最大堆…
阅读更多...
React中使用 ts 后，craco库配置别名时需要注意什么？

React中使用 ts 后，craco库配置别名时需要注意什么？

文章目录 前言编译报错如下解决方式总结 前言 我们都知道craco库可以用来覆盖react配置&#xff0c;如设置别名等。但是在项目使用 Typescript 后&#xff0c;我们需要额外配置&#xff0c;否则会造成编译报错。 详细craco配置可以查看之前文章&#xff1a; 项目初始化与配置…
阅读更多...
SpringBoot：SpringBoot中使用Redisson实现分布式锁

SpringBoot：SpringBoot中使用Redisson实现分布式锁

一、前言 Redisson是一个在Redis的基础上实现的Java驻内存数据网格&#xff08;In-Memory Data Grid&#xff09;。它不仅提供了一系列的分布式的Java常用对象&#xff0c;还提供了许多分布式服务。 刚好项目中需要使用到分布式锁&#xff0c;记录一下Redisson是如何使用分布式…
阅读更多...
PHP 页面报错Warning＜/b＞: Cannot modify header information - headers already sent by

PHP 页面报错Warning＜/b＞: Cannot modify header information - headers already sent by

先给出解决方案再解释&#xff0c;如果急着用就不用看解释了。 解决方案一&#xff1a;保存php文件编码为utf-8无BOM码&#xff0c;具体操作可以用notepad等编辑器完成&#xff0c;把 sesstion_start() 放在文档所有输出&#xff08;包括html标签和php的输出语句&#xff0c;具…
阅读更多...
场外个股期权标的有哪些？

场外个股期权标的有哪些？

今天带你了解场外个股期权标的有哪些&#xff1f;场外个股期权是一种金融衍生品&#xff0c;它不在交易所内进行交割&#xff0c;而是在交易所以外的场所进行交易的股票期权合约。 场外个股期权标的有哪些&#xff1f; 场外个股期权的标的通常包括A股市场上的融资融券标的&…
阅读更多...
掌握Django文件处理：一步步构建上传功能

掌握Django文件处理：一步步构建上传功能

创建模型 首先先进入我们的testsite项目下&#xff0c;打开members/models.py文件&#xff0c;先添加我们保存文件的数据模型&#xff1a; class Document(models.Model):name models.CharField(max_length255)file models.FileField(upload_touploads/) # uploads/ 是文件…
阅读更多...
批量提取 Word 文档中的全部图片

批量提取 Word 文档中的全部图片

步骤 1、打开 WinRAR 任选一个现成的压缩包双击打开 WinRAR &#xff0c;或从开始菜单打开 WinRAR 2、直接把要提取图片的 Word 文档拖入 WinRAR 菜单区域 1 → 2 → 3&#xff0c;WinRAR 资源管理目录中的 media 就是该 Word 文档所要提取的全部图片所在文件夹 按住&#x…
阅读更多...
【Vue】异步更新 $nextTick

【Vue】异步更新 $nextTick

文章目录 一、引出问题二、解决方案三、代码实现 一、引出问题 需求 编辑标题, 编辑框自动聚焦 点击编辑&#xff0c;显示编辑框让编辑框&#xff0c;立刻获取焦点 即下图上面结构隐藏&#xff0c;下面结构显示&#xff0c;并且显示的时候让它自动聚焦。 代码如下 问题 “…
阅读更多...
Vue3:eachars 折线图 数据不联动 和 tooltip: trigger: ‘axis‘ 不生效，不提示数据

Vue3:eachars 折线图 数据不联动 和 tooltip: trigger: ‘axis‘ 不生效，不提示数据

问题1&#xff1a; 点击折线图的头部数据&#xff08;Email、UnionAds等&#xff09; 下面数据线不联动问题 问题2&#xff1a;下图是没有提示数据的Demo 这是echars官网的提示数据图 3.解决办法 &#xff08;1&#xff09;检查是否设置&#xff1a;trigger&#xff1a;axi…
阅读更多...
SELinux深度解析：安全增强型Linux的探索与应用（下）

SELinux深度解析：安全增强型Linux的探索与应用（下）

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《Linux &#xff1a;从菜鸟到飞鸟的逆袭》&#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、SELinux的工作机制 1、SELinux的三种状态&#xff1a;Pe…
阅读更多...
在k8s中部署Kafka高可用集群超详细讲解

在k8s中部署Kafka高可用集群超详细讲解

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《数据流专家&#xff1a;Kafka探索》&#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、引言 1、Kafka简介 2、为什么在Kubernetes中部署Kafka 二、…
阅读更多...
决策树Decision Tree

决策树Decision Tree

目录 一、介绍发展优点缺点基本原理 二、熵1、熵2、条件熵3、信息增益4、信息增益率 三、基尼系数四、ID3算法1、建树过程2、优点3、缺点 五、C4.51、二分法处理连续变量1、流程&#xff1a;2、示例 2、缺点 六、CART1、连续数据处理2、离散数据处理3、CART回归原理1、均方误差…
阅读更多...
医学编码系统说明

医学编码系统说明

简介 流程说明 登录系统 在浏览器中访问FNEHR的站点&#xff0c;输入医院编号、用户和密码&#xff0c;选择“Other”&#xff0c;点击“Login”按钮&#xff0c;登录系统&#xff1a; 登录后&#xff0c;在左边显示系统的菜单&#xff1a; 系统设置 医院设置 点击左侧的“Acc…
阅读更多...
尚硅谷2024新版3小时速通Docker教程

尚硅谷2024新版3小时速通Docker教程

尚硅谷2024新版3小时速通Docker教程 百度网盘&#xff1a;https://pan.baidu.com/s/1SncgHbdJehvZspjcrrbLSw?pwd6c27
阅读更多...
【C语言】详解函数(下)（庖丁解牛版）

【C语言】详解函数(下)（庖丁解牛版）

文章目录 1. 前言2. 数组做函数形参3. 函数嵌套调用和链式访问3.1 嵌套调用3.2 链式访问 1. 前言 详解C语言函数(上)的链接&#xff1a;http://t.csdnimg.cn/EGsfe 经过对函数的初步了解之后,相信大家已经对C语言标准库里的函数已经有初步的认知了&#xff0c;并且还学会了如…
阅读更多...
最新文章

Copyright @ 2022~2023