当前位置: 首页 > 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;要保证不…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...