Leetcode：491. 递增子序列（C++）
创始人
2024-05-16 23:25:10
0次

目录

问题描述：

实现代码与解析：

回溯：

原理思路：

优化版：

原理思路：

问题描述：

        给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

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

实现代码与解析：

回溯：

class Solution {
public:vector path;//记录路径vector> result;//记录结果void backtracking(vector nums,int startIndex){//至少有两个元素if(path.size()>=2){result.push_back(path);}unordered_set used;//记录本层使用过的数，去重for(int i=startIndex;i> findSubsequences(vector& nums) {   backtracking(nums,0);return result;}
};

原理思路：

        首先就是保证得到结果递增，我们在非第一个数时判断是否大于等于前一个数即可，若小于则跳过此次循环，进行下一次循环。

        然后，此题与其他递归题不同的是，此题不能和其他回溯题一样来用排序去重，此题的顺序是规定不能变的，所以我们去重的话，就设置一个哈希表set来记录当前层用过的数，若发现已经用过，则跳过此层循环。

unordered_set used;//记录本层使用过的数，去重
//和上一个数比较,若小于，或与前面成功循环的数相同，则跳过此次循环，去重
if((!path.empty()&&nums[i]

        最后，注意一下要记录用过的数，还有这里要记录每一个结点的结果，不要在记录结果时就返回掉了。

//至少有两个元素
if(path.size()>=2)
{result.push_back(path);
}

优化版：

class Solution {
public:vector path;//记录路径vector> result;//记录结果void backtracking(vector nums,int startIndex){//至少有两个元素if(path.size()>=2){result.push_back(path);}int used[201]={0};//记录本层使用过的数，去重for(int i=startIndex;i> findSubsequences(vector& nums) {   backtracking(nums,0);return result;}
};

原理思路：

        就是把哈希表set换成了数组而已，因为这里给了数的范围，数少用数组会快一点。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：浅析一条SQL在mysql中是如何执行的

下一篇：java-List

相关内容

热门资讯

安卓子系统windows11,... 你知道吗？最近科技圈可是炸开了锅，因为安卓子系统在Windows 11上的兼容性成了大家热议的话题。...
电脑里怎么下载安卓系统,电脑端... 你有没有想过，你的电脑里也能装上安卓系统呢？没错，就是那个让你手机不离手的安卓！今天，就让我来带你一...
索尼相机魔改安卓系统,魔改系统... 你知道吗？最近在摄影圈里掀起了一股热潮，那就是索尼相机魔改安卓系统。这可不是一般的改装，而是让这些专...
安卓系统哪家的最流畅,安卓系统... 你有没有想过，为什么你的手机有时候像蜗牛一样慢吞吞的，而别人的手机却能像风一样快？这背后，其实就是安...
安卓最新系统4.42,深度解析... 你有没有发现，你的安卓手机最近是不是有点儿不一样了？没错，就是那个一直在默默更新的安卓最新系统4.4...
android和安卓什么系统最... 你有没有想过，你的安卓手机到底是用的是什么系统呢？是不是有时候觉得手机卡顿，运行缓慢，其实跟这个系统...
平板装安卓xp系统好,探索复古... 你有没有想过，把安卓系统装到平板上，再配上XP系统，这会是怎样一番景象呢？想象一边享受着安卓的便捷，...
投影仪装安卓系统,开启智能投影... 你有没有想过，家里的老式投影仪也能焕发第二春呢？没错，就是那个曾经陪你熬夜看电影的“老伙计”，现在它...
安卓系统无线车载carplay... 你有没有想过，开车的时候也能享受到苹果设备的便利呢？没错，就是那个让你在日常生活中离不开的iOS系统...
谷歌安卓8系统包,系统包解析与... 你有没有发现，手机更新换代的速度简直就像坐上了火箭呢？这不，最近谷歌又发布了安卓8系统包，听说这个新...
微软平板下软件安卓系统,开启全... 你有没有想过，在微软平板上也能畅享安卓系统的乐趣呢？没错，这就是今天我要跟你分享的神奇故事。想象你手...
coloros是基于安卓系统吗... 你有没有想过，手机里的那个色彩斑斓的界面，背后其实有着一个有趣的故事呢？没错，我要说的就是Color...
安卓神盾系统应用市场,一站式智... 你有没有发现，手机里的安卓神盾系统应用市场最近可是火得一塌糊涂啊！这不，我就来给你好好扒一扒，看看这...
黑莓平板安卓系统升级,解锁无限... 亲爱的读者们，你是否还记得那个曾经风靡一时的黑莓手机？那个标志性的全键盘，那个独特的黑莓体验，如今它...
安卓文件系统采用华为,探索高效... 你知道吗？最近安卓系统在文件管理上可是有了大动作呢！华为这个科技巨头，竟然悄悄地给安卓文件系统来了个...
深度系统能用安卓app,探索智... 你知道吗？现在科技的发展真是让人惊叹不已！今天，我要给你揭秘一个超级酷炫的话题——深度系统能用安卓a...
安卓系统的分区类型,深度解析存... 你有没有发现，你的安卓手机里藏着不少秘密？没错，就是那些神秘的分区类型。今天，就让我带你一探究竟，揭...
安卓系统铠无法兑换,揭秘无法兑... 最近是不是有很多小伙伴在玩安卓系统的游戏，突然发现了一个让人头疼的问题——铠无法兑换！别急，今天就来...
汽车安卓系统崩溃怎么刷,一键刷... 亲爱的车主朋友们，你是否曾遇到过汽车安卓系统崩溃的尴尬时刻？手机系统崩溃还能重启，但汽车系统崩溃了，...
miui系统可以刷安卓p系统吗... 亲爱的手机控们，你是否对MIUI系统情有独钟，同时又对安卓P系统的新鲜功能垂涎欲滴？今天，就让我带你...