回溯算法|491.递增子序列

力扣题目链接

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;
    }
};

这题要在理解的“子集II”这题的基础上写会好很多~

代码随想录 (programmercarl.com)

思路

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。

这又是子集,又是去重,是不是不由自主的想起了刚刚讲过的90.子集II (opens new window)。

就是因为太像了,更要注意差别所在,要不就掉坑里了!

在90.子集II (opens new window)中我们是通过排序,再加一个标记数组来达到去重的目的。

而本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。

所以不能使用之前的去重逻辑!

本题给出的示例,还是一个有序数组 [4, 6, 7, 7],这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比,我用[4, 7, 6, 7]这个数组来举例,抽象为树形结构如图:

491. 递增子序列1

#回溯三部曲

  • 递归函数参数

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

代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex)

  • 终止条件

本题其实类似求子集问题,也是要遍历树形结构找每一个节点,所以和回溯算法:求子集问题! (opens new window)一样,可以不加终止条件,startIndex每次都会加1,并不会无限递归。

但本题收集结果有所不同,题目要求递增子序列大小至少为2,所以代码如下:

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

  • 单层搜索逻辑

491. 递增子序列1

 在图中可以看出,同一父节点下的同层上使用过的元素就不能再使用了

那么单层搜索代码如下:

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();
}

对于已经习惯写回溯的同学,看到递归函数上面的uset.insert(nums[i]);,下面却没有对应的pop之类的操作,应该很不习惯吧

这也是需要注意的点,unordered_set<int> uset; 是记录本层元素是否重复使用,新的一层uset都会重新定义(清空),所以要知道uset只负责本层!

自己理解的思路:

知识点:

unordered_set和unorder_map很类似,内部都是无序的!
unordered_set是一种无序集合,其底层实现基于hashtable,因此具有快速的查找和删除,添加的优点,因此在需要多次查找和删除的场景里可以用unordered_set来存储数据!

那个去重部分的代码还是不好理解,自己还没完全掌握。

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

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

相关文章

[计算机知识] TCP/IP网络模型、MySQL的结构

TCP/IP网络模型 应用层 给用户提供应用功能&#xff0c;如HTTP, DNS 应用层处于用户态&#xff0c;传输层及以下处于内核态 传输层 给应用层提供网络支持&#xff0c;如TCP, UDP TCP提供稳定、面向连接的网络传输协议 应用层的数据可能会太大&#xff0c;就需要进行拆分…

【GAMES101】Lecture08 09 Shading 3 (Texture Mapping cont.) 纹理映射 续集

目录 0 引言1 如何在三角形内进行插值&#xff1a;重心坐标1.1 为什么要在三角形内插值1.2 重心坐标1.3 使用重心坐标做三角形内颜色插值 2 应用纹理2.1 简单的纹理映射&#xff1a;漫反射2.2 问题&#xff1a;纹理放大&#xff08;采用插值解决&#xff09;2.2 点查询和范围查…

Qt主窗口 之:停靠/悬浮窗口(QDockWidget)

一、QDockWidget概述 QDockWidget 是 Qt 中的一个窗口部件&#xff0c;用于创建可停靠的窗口&#xff0c;通常用于构建多文档接口&#xff08;MDI&#xff09;或可定制的用户界面。QDockWidget 允许用户将窗口停靠在应用程序的主窗口周围&#xff0c;或将其拖动到独立的浮动窗…

STM32

GPIO通用输入输出口 GPIO:8种输入输出模式 浮空输入可读取引脚电平&#xff0c;若引脚悬空&#xff0c;电平不确定上拉输入可读取引脚电平&#xff0c;内部接上拉电阻&#xff0c;悬空时默认为高电平下拉输入可读取引脚电平&#xff0c;内部接下拉电阻&#xff0c;悬空时默认…

视频编辑的瑞士军刀,MoviePy库的详解与应用示例

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir&#xff0c;关注领取python编程资料 在数字媒体的时代&#xff0c;视频内容的创作和编辑变得越来越重要。无论是社交媒体上的短视频&…

【数据结构】初识数据结构与复杂度总结

前言 C语言这块算是总结完了&#xff0c;那从本篇开始就是步入一个新的大章——数据结构&#xff0c;这篇我们先来认识一下数据结构有关知识&#xff0c;以及复杂度的相关知识 个人主页&#xff1a;小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1.什么是数据结构 2.…

原创【matcap材质在ue4中的实现办法】

matcap材质在ue4中的实现办法 2023-08-29 15:34 https://www.bilibili.com/video/BV1GR4y1b76n/?spm_id_from333.337.search-card.all.click&vd_sourced76b773892c830a157c0ccc97ba78411 评论(0)

PS从入门到精通视频各类教程整理全集,包含素材、作业等(8)复发

PS从入门到精通视频各类教程整理全集&#xff0c;包含素材、作业等 最新PS以及插件合集&#xff0c;可在我以往文章中找到 由于阿里云盘有分享次受限制和文件大小限制&#xff0c;今天先分享到这里&#xff0c;后续持续更新 B站-PS异闻录&#xff1a;萌新系统入门课课程视频 …

Golang学习系列1-pprof性能调优

1. pprof 简述 一位亦师亦友的话让我记忆犹新&#xff0c;他说“学习一个新事务&#xff0c;应该从三个方面入手what,why,how;且三者的重要程度应该是递减”。所以在本文的第一部分先叙述下pprof的what & why。 1.1 What&#xff1f; pprof是golang自身提供的一种性能分…

基于顺序表的学生成绩管理系统

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

【Flink技术原理构造及特性】

1、Flink简介 Flink是一个批处理和流处理结合的统一计算框架&#xff0c;其核心是一个提供了数据分发以及并行化计算的流数据处理引擎。它的最大亮点是流处理&#xff0c;是业界最顶级的开源流处理引擎。 Flink最适合的应用场景是低时延的数据处理&#xff08;Data Processin…

算法练习—day1

title: 算法练习—day1 date: 2024-04-03 21:49:55 tags: 算法 categories:LeetCode typora-root-url: 算法练习—day1 网址&#xff1a;https://red568.github.io 704. 二分查找 题目&#xff1a; 题目分析&#xff1a; 左右指针分别为[left,right]&#xff0c;每次都取中…

练习 19 Web [BJDCTF2020]Easy MD5

如果你是第一批做这个题的&#xff0c;这道题一点也不easy 打开在前端代码里面看到&#xff0c;输入框输入的内容实际是’password’ 随意输入内容&#xff0c;查看响应header中的内容有一句SQL代码&#xff0c;可知我们要让password在md5后返回值为true 然后尬住&#xff…

区间DP模型

目录 环形石子合并思路代码实现 能量项链代码实现 加分二叉树思路代码实现 凸多边形的划分代码实现 棋盘分割题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 佬的题解代码实现 环形石子合并 题目描述&#xff1a; 将 n n n 堆石子绕圆形操场排放&#xff0c;现要将…

前端(动态雪景背景+动态蝴蝶)

1.CSS样式 <style>html, body, a, div, span, table, tr, td, strong, ul, ol, li, h1, h2, h3, p, input {font-weight: inherit;font-size: inherit;list-style: none;border-spacing: 0;border: 0;border-collapse: collapse;text-decoration: none;padding: 0;margi…

C++从入门到精通——入门知识

1. C关键字(C98) C总计63个关键字&#xff0c;C语言32个关键字 2. 命名空间 在C/C中&#xff0c;变量、函数和后面要学到的类都是大量存在的&#xff0c;这些变量、函数和类的名称都将存在于全局作用域中&#xff0c;可能会导致很多冲突。使用命名空间的目的就是对标识符的名…

43.1k star, 免费开源的 markdown 编辑器 MarkText

43.1k star, 免费开源的 markdown 编辑器 MarkText 分类 开源分享 项目名: MarkText -- 简单而优雅的开源 Markdown 编辑器 Github 开源地址&#xff1a; https://github.com/marktext/marktext 官网地址&#xff1a; MarkText 支持平台&#xff1a; Linux, macOS 以及 Win…

中文Mistral模型介绍(Chinese-Mistral)——中文大语言模型

中文Mistral简介 Chinese-Mistral由清华大学地学系地球空间信息科学实验室开发。 该模型基于Mistral发布的Mistral-7B-v0.1训练得到。首先进行中文词表扩充&#xff0c;然后采用实验室提出的PREPARED训练框架&#xff08;under review&#xff09;在中英双语语料上进行增量预训…

C++Date类的实现

目录 前言&#xff1a; 1.显示日期 2.构造函数与获取某年某月的日期的函数 3.日期比较 4.日期加减天数 5.日期减日期 6.前置后置与-- 7.完整代码 8.测试 总结&#xff1a; 感谢支持&#xff01; 前言&#xff1a; 结合了前面的内容的学习&#xff0c;本篇来对之前的…

面试篇:杂乱篇

String s " "; 1. String类的常用方法有哪些&#xff1f; s.length()&#xff1a; 返回字符串长度s.substring()&#xff1a; 截取字符串s.split()&#xff1a; 分割字符串s.equlas()&#xff1a; 字符串比…