当前位置: 首页 > news >正文

面试热点题:回溯算法 递增子序列与全排列 II

前言:
如果你一点也不了解什么叫做回溯算法,那么推荐你看看这一篇回溯入门,让你快速了解回溯算法的基本原理及框架

递增子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

来源:力扣(LeetCode)递增子序列
在这里插入图片描述
由题意可得下面两点要求:

  • 递增的子序列,且元素数量大于2
  • 子序列与子序列不能相同
  • 可使用重复出现的数字

像这种需要依次取元素,然后将元素存储起来汇成总集合,期间可能还需要回退取不一样集合的题目,我们第一个想到的可以使用回溯法,那么该如何回溯呢?且看下图分析:我们使用[ 4,7,6,7 ]举例
在这里插入图片描述
在这里插入图片描述

  1. 回溯收集子集条件
    根据题意可以得知,我们只要子序列的数量大于等于2就可以
  2. 回溯终止条件
    终止条件就是达到nums.size()
  3. 单层搜索逻辑
    我们由图可以得知,虽然序列里面可能有重复的数字,但是单层我们不能取相同的数字,如果我们取了相同的数字,那么必定会存在相同的子集,所以我们单层需要去重

单层去重我们这里使用一个标记的容器 unordered_set< int > use存放已经出现过的数字


代码如下:

class Solution {
public:vector<vector<int>> arr;vector<int> _arr;void BackTracking(vector<int>& nums,int begin){if(_arr.size()>=2)//只要数据>=2就存储,我们这里不需要return{arr.push_back(_arr);}unordered_set<int> use;//标记容器for(int i=begin;i<nums.size();i++){//如果是空直接存放,然后判断别的关系if((!_arr.empty() && _arr.back()>nums[i]) || use.find(nums[i])!=use.end()){continue;}_arr.push_back(nums[i]);use.insert(nums[i]);BackTracking(nums,i+1);//不能重复使用单个数据,所以我们需要i+1_arr.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {BackTracking(nums,0);return arr;}
};

全排列 II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

来源:力扣(LeetCode)全排列 II

本题是全排列的进阶版,之前是没有重复元素,现在有重复元素,我们该如何解决呢?

在这里插入图片描述
这个题与上一题递增子序列相差不多,也是需要单层去重,且看下图:
在这里插入图片描述
相较于之前的收集元素,排列我们需要将每个元素都使用到,所以我们每次循环开始条件都为0,但是为了不使用一个使用过的元素,我们需要设置一个标记的数组,使用过一个标记一个,单层去重,是因为同一层使用相同的元素没有意义,使用相同元素,相当于递归两遍相同数据,导致出现相同子集

  • 先排序所有元素
  • 标记数组
  • 单层去重

代码如下:

class Solution {
public:vector<vector<int>> arr;vector<int> _arr;void BackTracking(vector<int>& nums,vector<bool>& use){if(_arr.size()==nums.size()){arr.push_back(_arr);return;}for(int i=0;i<nums.size();i++){//单层去重,及判断元素是否使用过if(i>0 && nums[i]==nums[i-1] && use[i-1]==false){continue;}if(use[i]==false){use[i]=true;_arr.push_back(nums[i]);BackTracking(nums,use);_arr.pop_back();use[i]=false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());//需要排序,为去重做准备vector<bool> use(nums.size(),false);BackTracking(nums,use);return arr;}
};

相关文章:

面试热点题:回溯算法 递增子序列与全排列 II

前言&#xff1a; 如果你一点也不了解什么叫做回溯算法&#xff0c;那么推荐你看看这一篇回溯入门&#xff0c;让你快速了解回溯算法的基本原理及框架 递增子序列 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两…...

怎么找回回收站删除的文件

我们都知道&#xff0c;电脑文件都是放在桌面上的&#xff0c;单独存放或者一起存放在文件夹里。但总会有已用完或者是没用的文件&#xff0c;这让我们不得不对其进行清理。而清空回收站也是不可避免的。如果出现了清空文件中还有我们需要的文件&#xff0c;怎么找回回收站删除…...

dp-打家劫舍

你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入&#xff0c;系统会自动报警。给定一个代表每个房屋存放金额的非…...

C++预处理连接

目录定义常量字符串前缀定义枚举类型Boost C库中常常使用预处理连接来定义宏和模板类Google开源的C单元测试框架gtest&#xff0c;使用预处理连接技术创建测试用例和测试方法C预处理连接&#xff08;Preprocessor Concatenation&#xff09;是一种宏定义技巧&#xff0c;用于将…...

3、DRF实战总结:基于类的视图APIView, GenericAPIView和GenericViewSet视图集(附源码)

前面介绍了什么是符合RESTful规范的API接口&#xff0c;以及使用了基于函数的视图(FBV)编写了对文章进行增删查改的API。在本篇文章将使用基于类的视图(Class-based View, CBV)重写之前的接口。 参考&#xff1a; 1、Django开发总结&#xff1a;Django MVT与MVC设计模式&…...

AutoSAR PduR -AutoSAR PDU常用的使用方式【发送,接收,网关】

总目录链接==>> AutoSAR入门和实战系列总目录 @学前问答: AutoSAR PDU在哪里全局定义的? AutoSAR PDU涉及到哪些模块? AutoSAR PDU网关怎么使用? 文章目录 1 AutoSAR PDU发送2 AutoSAR PDU接收3 AutoSAR PDU网关转发4 答疑解析AutoSAR PDU 怎么样通过PduR 实现与其…...

瑟瑟发抖吧~OpenAI刚刚推出王炸——引入ChatGPT插件,开启AI新生态

5分钟学会使用ChatGPT 插件&#xff08;ChatGPT plugins&#xff09;——ChatGPT生态建设的开端ChatGPT插件是什么OpenAI最新官方blog资料表示&#xff0c;已经在ChatGPT中实现了对插件的初步支持。插件是专门为以安全为核心原则的语言模型设计的工具&#xff0c;可帮助ChatGPT…...

脉诊(切脉、诊脉、按脉、持脉)之法——入门篇

认识脉诊何谓脉诊&#xff1f;脉诊的渊源脉诊重要吗&#xff1f;脉诊确有其事&#xff0c;还是故弄玄虚&#xff1f;中医科学吗&#xff1f;如何脉诊&#xff1f;寸口脉诊法何谓脉诊&#xff1f; 所谓脉诊&#xff0c;就是通过把脉来诊断身体健康状况的一种必要手段。 …...

【十二天学java】day09常用api介绍

1.API 1.1API概述 什么是API API (Application Programming Interface) &#xff1a;应用程序编程接口 java中的API 指的就是 JDK 中提供的各种功能的 Java类&#xff0c;这些类将底层的实现封装了起来&#xff0c;我们不需要关心这些类是如何实现的&#xff0c;只需要学习这…...

软件测试 - 测试用例常见面试题

1.测试用例的要素测试用例是为了实施测试而向被测试的系统提供的一组集合, 这组集合包含 : 测试环境, 操作步骤, 测试数据, 预期结果等要素.例如 : 在 B 站输入框输入一个空格, 检查结果测试用例标题 : 输入框输入空格测试环境 : Windows 系统, 谷歌浏览器-版本 111.0.5563.65&…...

几种常见的API接口分页方案

文章目录1 概述2 分页方案2.1 基于偏移量2.2 基于游标3 重复数据处理3.1 基于时间3.2 基于热度3.3 基于推荐1 概述 列表是互联网产品中很常见的一种内容排列形式&#xff0c;而且列表的数据集往往成千上万&#xff0c;一次性返回全量数据集的场景几乎不存在&#xff0c;所以出…...

【Object 类的方法】

在 Java 中&#xff0c;所有类都继承了 Object 类&#xff0c;因此 Object 类中的方法可以在所有 Java 对象中使用。下面是 Object 类中的一些常用方法介绍&#xff1a; equals(Object obj): 用于判断两个对象是否相等。默认情况下&#xff0c;该方法比较的是两个对象的地址是…...

留用户、补内容,在线音乐暗战不停

在线音乐在人们的日常生活中扮演着愈发重要的角色&#xff0c;尤其是在面临巨大压力时&#xff0c;人们往往更倾向于通过倾听一段音乐来缓解内心的紧张与焦虑。而随着在线音乐用户数量的增长以及付费意愿的增强&#xff0c;在线音乐行业也实现了稳步发展。 经过多年的发展&…...

python--exec

在Python中&#xff0c;eval和exec都是用来执行动态代码的内置函数&#xff0c;但它们的作用和使用方式有所不同。 eval(): 将字符串作为Python表达式进行求值&#xff0c;并返回结果。 exec(): 将字符串作为Python语句进行执行&#xff0c;没有返回值。 eval()的使用范围通常限…...

干货分享!这6个高效率办公软件,总有一个值得你收藏!

分享6款高效办公软件&#xff0c;可以解决你很多需求&#xff0c;职场人一定要知道。每一款都是精挑细的&#xff0c;可能有的已经很大众了&#xff0c;但肯定还有小伙伴不知道&#xff0c;废话不多说&#xff0c;直接看&#xff01;&#xff01; 1、Flomo笔记&#xff1a;记录…...

代码随想录刷题-链表总结篇

文章目录链表理论基础单链表双链表循环链表其余知识点链表理论基础单链表双链表循环链表其余知识点移除链表元素习题我的解法虚拟头结点解法设计链表习题我的解法代码随想录代码反转链表习题双指针递归两两交换链表中的节点习题我的解法代码随想录解法删除链表的倒数第N个节点习…...

C++:指针:什么是野指针

野指针目录1&#xff1a;定义2&#xff1a;野指针常见情形2.1 &#xff1a;未初始化的野指针2.2 所指的对象已经消亡2.3 指针释放之后未置空3&#xff1a;避免野指针1&#xff1a;定义 指向非法的内存地址的指针叫做野指针&#xff08;Wild Pointer&#xff09;&#xff0c;也…...

一线大厂高并发Redis缓存架构

文章目录高并发缓存架构设计架构设计思路完整代码开发规范与优化建议键值设计命令使用客户端的使用扩展布隆过滤器redis的过期键的清除策略高并发缓存架构设计 架构设计思路 首先是一个基础的缓存架构&#xff0c;对于新增、修改操作set会对缓存更新&#xff0c;对于查询操作…...

剑指offer-二维数组中的查找

文章目录题目描述题解一 无脑暴力循环题解二 初始二分法&#x1f315;博客x主页&#xff1a;己不由心王道长&#x1f315;! &#x1f30e;文章说明&#xff1a;剑指offer-二维数组中的查找&#x1f30e; ✅系列专栏&#xff1a;剑指offer &#x1f334;本篇内容&#xff1a;对剑…...

怎么设计一个秒杀系统

1、系统部署 秒杀系统部署要单独区别开其他系统单独部署&#xff0c;这个系统的流量肯定很大&#xff0c;单独部署。数据库也要单独用一个部署的数据库或者集群&#xff0c;防止高并发导致整个网站不可用。 2、防止超卖 100个库存&#xff0c;1000个人买&#xff0c;要保证不…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...