( 回溯算法) 491. 递增子序列 ——【Leetcode每日一题】

news/2024/2/27 21:48:33

❓491. 递增子序列

难度:中等

给你一个整数数组 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]]

提示:

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

💡思路:回溯

本题可以使用回溯求解,可以将本问题切割成很多个小部分,只考虑其中一个数,然后将剩余的数往下递归处理,可以理解成好多层,每层只加一个元素:

  • 定义一个数组 tmp 保存递增子序列,由于递增子序列中 至少有两个元素,所以只要递增子序列的长度如果大于 1 ,则是一种可能;
  • 还要考虑去重的情况,可以使用 哈希表 或者 使用数组(元素范围为[-100, 100])保存进行去重,这里使用数组:
    • 新的一层 used 都会重新定义(清空),所以要知道 used 只负责本层!

在这里插入图片描述

🍁代码:(Java、C++)

Java

class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> tmp = new ArrayList<>();private void backtracking(int[] nums, int startIndex){if(tmp.size() > 1){//如果长度大于1就是一种可能ans.add(new ArrayList<>(tmp));}int[] used = new int[201];//使用数组对本层元素进行去重for(int i = startIndex; i < nums.length; i++){if((!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1)) || (used[nums[i] + 100] == 1)){//排除较小的数和已经使用过的数continue;}used[nums[i] + 100] = 1;// 记录这个元素在本层用过了,本层后面不能再用了tmp.add(nums[i]);backtracking(nums, i + 1);tmp.remove(tmp.size() - 1);//回溯,弹出最后一个元素,继续遍历其他可能}}public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return ans;}
}

C++

class Solution {
private:vector<vector<int>> ans;vector<int> tmp;void backtracking(vector<int>& nums, int startIndex){if(tmp.size() > 1){//如果长度大于1就是一种可能ans.push_back(tmp);}int used[201] = {0}; //使用数组对本层元素进行去重for(int i = startIndex; i < nums.size(); i++){if((!tmp.empty() && nums[i] < tmp.back()) || used[nums[i] + 100] == 1){//排除较小的数和已经使用过的数continue;}used[nums[i] + 100] = 1;// 记录这个元素在本层用过了,本层后面不能再用了tmp.push_back(nums[i]);backtracking(nums, i + 1);tmp.pop_back();//回溯,弹出最后一个元素,继续遍历其他可能}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums, 0);return ans;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ∗ 2 n ) O(n * 2^n) O(n2n),这里枚举所有子序列的时间代价是 O ( 2 n ) O(2^n) O(2n),每次检测序列是否合法和获取哈希值的时间代价都是 O ( n ) O(n) O(n),故渐近时间复杂度为 O ( n ∗ 2 n ) O(n * 2^n) O(n2n)
  • 空间复杂度 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/77638.html

相关文章

day82【Leetcode】

文章目录 前言一、检查替换后的词是否有效&#xff08;力扣1003&#xff09;二、有效的括号&#xff08;力扣20&#xff09;【1003类似题目】每日一题&#xff1a;数青蛙&#xff08;力扣1419&#xff09; 前言 1、检查替换后的词是否有效 2、有效的括号 3、数青蛙 一、检查替…

【008】C++数据类型之重要关键字详解

C数据类型之重要关键字详解 引言一、const修饰普通变量重点说明 二、register修饰寄存器变量三、volatile强制访问内存四、sizeof测试类型的大小五、typedef关键字总结 引言 &#x1f4a1; 作者简介&#xff1a;专注于C/C高性能程序设计和开发&#xff0c;理论与代码实践结合&a…

OA系统开发能结合人工智能打造全新体系吗?

先来说一说OA系统的 项目背景&#xff1a; 某公司是一个拥有500名员工的中等规模企业&#xff0c;其业务范围涵盖销售、生产、研发等领域。随着公司规模的不断扩大&#xff0c;日常办公流程变得越来越复杂&#xff0c;员工之间的协作需求也日益增加。为了提高办公效率&#xff…

idea 调试远程docker中的spring boot 项目

开发环境 idea-2023&#xff08;放心&#xff0c;旧版本也可以远程调试&#xff09; Java版本&#xff1a;17 生产环境 docker版本&#xff1a;23.0.3 Java版本1&#xff1a;openjdk:17.0.2&#xff08;基于Java17的项目&#xff09; Java版本2&#xff1a;adoptopenjdk:…

本地项目上传到Git(Gitee)仓库

一、步骤解答&#xff08;详细图解步骤见第二大点&#xff09; 1、打开我们的项目所在文件夹&#xff0c;我们发现是不存在.git文件 2、在你的项目文件夹外层【鼠标右击】弹出菜单&#xff0c;在【鼠标右击】弹出的菜单中&#xff0c;点击【Git Bash Here】&#xff0c;弹出运…

〖Python网络爬虫实战㉘〗- Selenium案例实战(二)

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;目前专栏免费订阅&#xff0c;在转为付费专栏前订阅本专栏的&#xff0c;可以免费订阅付…

小航助学GESP_C++一级模拟测试试卷(含题库答题软件账号)

GESP在线模拟训练系统请点击 电子学会-全国青少年编程等级考试真题Scratch一级&#xff08;2019年3月&#xff09;在线答题_程序猿下山的博客-CSDN博客_小航答题助手 答案:A 第1题人们在使用计算机时所提到的 Windows 通常指的是&#xff08;&#xff09;。 A、操作系统B、多…

ChatGPT 的议论文究竟写的怎么样?111 位高中教师告诉你答案

夕小瑶科技说 原创 作者 | 小戏、Python 在 OpenAI GPT-4 发布时发布的《GPT-4 Technical Report》中&#xff0c;其中很吸引人眼球的一部分是 GPT-4 应用于教育领域的出色表现&#xff0c;通过让 GPT-4 去完成美国的 AP 课程及考试&#xff0c;来评估 GPT-4 在多个学科中的性…

Git忽略文件的几种方法,以及.gitignore文件的忽略规则

Git忽略文件的几种方法&#xff0c;以及.gitignore文件的忽略规则 .gitignore文件定义Git全局的.gitignore文件Git 忽略规则Git忽略规则的优先级.gitignore文件忽略规则常用匹配示例&#xff1a; 关于.gitignore规则不生效的问题 不忽略没有后缀名的文件搜索电脑里没有后缀的文…

NIST安全隐私框架(云安全)

目录 导言 定义 NIST隐私框架基本特征 NIST隐私框架有三个要素 导言 没有为隐私进行设计会对个人和社会层面产生直接的负面影响,影响组织的品牌,换句话说,他们的产品或服务的价值主张,组织的财务底线和未来的增长前景。 由于侵犯隐私造成的主要和次要损失可能是巨大的…

棋盘覆盖问题

文章目录 棋盘覆盖程序设计程序分析棋盘覆盖 【问题描述】 在一个2k x 2k ( 即:2^k x 2^k )个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方…

NetApp 数据存储系统 AFF A 系列的优势及应用行业

AFF A 系列阵列&#xff1a;云集成、性能极强、蓄势待发 需要小幅&#xff08;或大幅&#xff09;提升您的关键业务应用程序的性能吗&#xff1f;我们的 AFF A 系列阵列具备屡获殊荣的速度和响应能力&#xff0c;能满足性能敏感型工作负载的需求 为什么选择 NetApp AFF A 系列…

Jetpack StartUp

在翻看Android文档的时候看到jetpack有个StartUp组件&#xff0c;好奇就查了下它的用途 App的初始化 我们现在很多初始化sdk库的方式一般为&#xff1a; class App: Application() {override fun onCreate(){ASDK.init()BSDK.init()CSDK.init(this) } }还有一种初始化sdk的…

手动搭建一个简单的MVVMLight框架的方法

本章讲述&#xff1a;手动搭建一个简单的MVVMLight框架步骤&#xff1a; 1、下载MVVMLight所需要的dll库文件 主要文件包括&#xff1a;CommonServiceLocator.dll、GalaSoft.MvvmLight.dll、GalaSoft.MvvmLight.Extras.dll、GalaSoft.MvvmLight.Platform.dll、System.Windows.…

希望计算机专业同学都知道这些博主

湖科大教书匠——计算机网络 “宝藏老师”、“干货满满”、“羡慕湖科大”…这些都是网友对这门网课的评价&#xff0c;可见网课质量之高&#xff01;最全面的面试网站 湖南科技大学《计算机网络》微课堂是该校高军老师精心制作的视频课程&#xff0c;用简单的语言描述复杂的…

【学习随笔】

2022/11/13 HTML :讲完了 css&#xff1a;讲完了 作业&#xff1a;编写登陆界面、整理一下sql优化,对于mybatis不熟练的继续练习 关于MySQL优化的问题? 思路总结&#xff1a;主要考虑数据库优化与SQL语句优化。 1&#xff0c;数据库优化&#xff0c;包括存储引擎的优化&…

为了流量,何同学做了个“假B站”?

何同学是B站知名数码博主&#xff0c;凭借优秀的视频制作能力&#xff0c;内容创新获得广大年轻用户的喜欢。 2021年的时候&#xff0c;UP主老师好我叫何同学就发布了一条制作AirDesk的视频&#xff0c;随后迅速在社交媒体中引发了大量关注。 当时&#xff0c;该视频为B站全站…

解析XML文件

什么是XML&#xff1f; xml指可扩展语言(extendsible Markup Language)&#xff0c;标准通用标记语言的子集&#xff0c;是一种用于标记电子文件使其具有结构性的标记语言。 xml被设计用来传输和存储数据。 xml是一套定义语义标记的规则&#xff0c;这些标记将文档分成许多部件…

只需6步,就能让你的 React +Tailwind.css站点实现暗黑功能

欢迎回来&#xff0c;开始一次新的编码之旅吧&#xff01;今天&#xff0c;我们将进入神秘的世界&#xff0c;探索如何在你的React.js网站中使用Tailwind.css实现暗黑模式。Tailwind.css 是你编码工具中的强大助手&#xff0c;结合React.js使用&#xff0c;你可以创造出令人惊叹…

Elasticsearch 7.x 基本操作 (CRUD)

1.概述 Elasticsearch 是一个流行的开源搜索引擎&#xff0c;用于存储、搜索和分析数据。下面是 Elasticsearch 7.x 版本的基本操作&#xff08;CRUD&#xff09;&#xff1a; 1、创建索引&#xff1a; PUT /index_name {"settings": {"number_of_shards"…
最新文章