DAY25|回溯算法Part04|LeetCode:491.递增子序列、46.全排列、47.全排列 II

server/2024/11/14 2:01:28/

目录

LeetCode:491.递增子序列

基本思路

C++代码

LeetCode:46.全排列

基本思路

C++代码

LeetCode:47.全排列 II

基本思路

C++代码


LeetCode:491.递增子序列

力扣代码链接

文字讲解:LeetCode:491.递增子序列

视频讲解:回溯算法精讲,树层去重与树枝去重

基本思路

        这个题目和90.子集II很像,但是不同在于90.子集II中我们是通过排序,再加一个标记数组来达到去重的目的,而本题中是不能对原数组进行排序的,排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑!

        以示例1为例,抽象为树形结构如图所示:

  • 递归函数参数

        这里依然是定义两个全局变量,二维数组result存放结果集,数组path存放符合条件的结果。

        参数:本题求子序列,很明显一个元素不能重复使用,所以需要startIndex,调整下一层递归的起始位置。

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex)
  • 递归终止条件

        题目要求递增子序列大小至少为2,而且不会无限递归,可以不加终止条件,startIndex每次都会加1,for循环结束即会终止。

if (path.size() > 1) {result.push_back(path);// 注意这里不要加return,因为要取树上的所有节点
}
  • 单层搜索逻辑

       如上图所示,显然同一父节点下的同层上使用过的元素就不能再使用了。

unordered_set<int> uset; // 使用set来对本层元素进行去重
for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end()) {continue;}uset.insert(nums[i]); // 记录这个元素在本层用过了,本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();
}

C++代码

// 版本一
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);// 注意这里不要加return,要取树上的节点}unordered_set<int> uset; // 使用set对本层元素进行去重for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end()) {continue;}uset.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;}
};

LeetCode:46.全排列

力扣代码链接

文字讲解:LeetCode:46.全排列

视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?

基本思路

        以例一为例,抽象树形结构如下所示:

  • 递归函数参数

        首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组,标记已经选择的元素,如图橘黄色部分所示:

vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used)
  • 递归终止条件

        可以看出叶子节点,就是收割结果的地方。当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。

// 此时说明找到了一组
if (path.size() == nums.size()) {result.push_back(path);return;
}
  • 单层搜索的逻辑

        排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次

for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素,直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;
}

C++代码

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking (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] == true) continue; // path里已经收录的元素,直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

LeetCode:47.全排列 II

力扣代码链接

文字讲解:LeetCode:47.全排列 II

视频讲解:回溯算法求解全排列,如何去重?

基本思路

        这个题目和上一题的区别在于给定一个可包含重复数字的序列,要返回所有不重复的全排列。显然需要进行去重,但是应该对树层进行去重还是树枝呢?抽象树形结构如下所示:

        图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}

C++代码

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {// used[i - 1] == true,说明同一树枝nums[i - 1]使用过// used[i - 1] == false,说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == false) {used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

http://www.ppmy.cn/server/141732.html

相关文章

React融合css

单纯使用tsx文件生成的页面比较单一&#xff0c;可以考虑结合css进行使用&#xff0c;需要说明的是&#xff0c;本人水平有限&#xff0c;仅对接触过的几种方式进行说明 内联样式 内联样式也有多种写法&#xff0c;此处仅列举两种比较简单的写法 写法一 import React from …

网络安全-蓝队基础

声明 学习视频来自 B 站UP主泷羽sec&#xff0c;如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 ✍&#x1f3fb;作者简介&#xff1a;致…

CentOS下如何安装Nginx

1、下载nginx 官方网站 http://nginx.org 下载链接&#xff1a;http://nginx.org/download/ 下载完成后的安装包&#xff1a; 2、使用解压命令进行解压 tar -zxvf nginx-1.13.7.tar.gz3、在安装所需的安装环境 安装gcc环境 yum install gcc-c安装第三方开发包 - PCRE(P…

OpenEuler 下 Docker 安装、配置与测试实例

文章目录 前言1. 环境准备2. 下载 Docker3.配置服务文件4.配置加速器加速下载docker镜像5. 验证 Docker 安装 前言 Docker 安装大致分为包管理器安装、脚本安装、离线手动安装、容器编排工具安装、桌面版安装等&#xff0c;每种安装各有特点&#xff0c;但涉及知识面不少&…

导航栏小案例

实现类似于这样的效果 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>导航栏</title><style>*{margin: 0;padding: 0;}.div1{width: 100%;height: 60px;/* border: 1px solid blue; */background-color:rgb(…

Spring Boot中的自动装配机制

文章目录 1. 什么是自动装配&#xff1f;2. 自动装配是如何工作的&#xff1f;3. 如何开启自动装配&#xff1f;4. 自动装配的注意事项5. 结语推荐阅读文章 在Spring Boot的世界里&#xff0c;自动装配&#xff08;Auto-configuration&#xff09;就像春风拂面&#xff0c;轻轻…

Spring Boot——日志介绍和配置

1. 日志的介绍 在前面的学习中&#xff0c;控制台上打印出来的一大堆内容就是日志&#xff0c;可以帮助我们发现问题&#xff0c;分析问题&#xff0c;定位问题&#xff0c;除此之外&#xff0c;日志还可以进行系统的监控&#xff0c;数据采集等 2. 日志的使用 在程序中获取日…

原生 JavaScript基本内容和常用特性详解

原生 JavaScript&#xff08;也称为 Vanilla JS&#xff09;指的是不依赖于任何框架或库的纯 JavaScript。以下是原生 JavaScript 的一些基本内容和常用特性详解。 目录 1. 数据类型 2. 变量声明 3. 控制结构 4. 函数 5. 对象和数组 6. 事件处理 7. DOM 操作 8. Promi…