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

数据结构刷题(二十二):90子集II、491递增子序列、46全排列

1.子集II

题目链接

思路:这是一道标准的组合问题+数组排序+去重。依然是使用回溯。

注意:去重代码只需要判断同一树层上是否有重复,同组合总和II(https://blog.csdn.net/xiaomingming99/article/details/129396344

解法:

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {// 记得数组排序Arrays.sort(nums);back(nums, 0);return res;}private void back(int[] nums, int startIndex) {res.add(new ArrayList<>(path));for (int i = startIndex; i < nums.length; i++){// 去重if (i > startIndex && nums[i] == nums[i - 1])continue;path.add(nums[i]);back(nums, i + 1);path.removeLast();  // 回溯}}
}

2.递增子序列

题目链接

思路:回溯+数组去重;

回溯三部曲:

  • 返回参数:startindex和数组nums。 全局变量path(记录单个结果)和res(记录结果集合)

  • 终止条件:本题要求递增子序列大小至少为2,所以要判断path.size()>=2

  • 单层逻辑:for循环中,需要判断path的最后一个元素是否大于当前nums[i],且还需要添加代码实现同一父节点下的同层上使用过的元素就不能再使用

注意:

1.&&和||同时出现时,&&优先级更高,先执行&&

2.在90.子集II (opens new window)中是通过排序原数组,判断同一树层元素是否重复来达到去重。

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

class Solution {private  LinkedList<Integer> path = new LinkedList<>();private  List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums,0);return res;}private void backtracking (int[] nums, int start) {// path的size必须大于等于2  且不需要return,因为后面可能还有更长的符合条件的序列if (path.size() >= 2) {res.add(new ArrayList<>(path));}// 标记数组  用于去重  // 比如[4,6,7,7] 使用这个数组就可以只出现一次[4,6,7] 标记6使用过int[] used = new int[201];for (int i = start; i < nums.length; i++) {// 先执行&&,判断path的最后一个元素是否大于当前值,如果是则说明不符合递增// 后执行|| 判断当前元素是否被使用过if (!path.isEmpty() && nums[i] < path.getLast()  ||(used[nums[i] + 100] == 1)) continue;used[nums[i] + 100] = 1; // 记录这个元素在本层用过了,本层后面不能再用了path.add(nums[i]);backtracking(nums, i + 1);path.removeLast();}}
}

3.全排列

题目链接

思路:回溯的排列问题。

回溯三部曲:

  • 递归函数参数:参数只需要nums。不需要startIndex参数,因为排列问题,每次都要从头开始搜索。全局变量path(记录单个结果)和res(记录结果集合)

  • 递归终止条件:只需要收集元素的数组path大小达到和nums数组一样大,说明到达叶子结点,可以返回

  • 单层搜索的逻辑:for循环中需要判断当前元素是否已经在path中,若在直接continue。

注意: 首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,区别于组合问题。

解法:

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {back(nums);return res;}private void back(int[] nums) {// 终止条件if (path.size() == nums.length){res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++){// 判断path中是否含有遍历元素if (path.contains(nums[i]))continue;path.add(nums[i]);back(nums);path.removeLast();}}
}

相关文章:

数据结构刷题(二十二):90子集II、491递增子序列、46全排列

1.子集II题目链接思路&#xff1a;这是一道标准的组合问题数组排序去重。依然是使用回溯。注意&#xff1a;去重代码只需要判断同一树层上是否有重复&#xff0c;同组合总和II&#xff08;https://blog.csdn.net/xiaomingming99/article/details/129396344&#xff09;解法&…...

AI+人类,实现高效网络安全

导语 聊天机器人和生成式人工智能&#xff08;如 ChatGPT&#xff09;突然成为主流让很多人感到担忧。很多人开始担忧&#xff0c;人工智能取代人的时代已经到来。 幸运的是&#xff0c;事实并非如此。 更有可能的情况是&#xff0c;人类将与 AI 合作创建工作角色的混合模型。…...

牛客小白月赛68【A-E】

文章目录A.Tokitsukaze and New Operation【模拟】B.Tokitsukaze and Order Food Delivery【模拟、特判】C.Tokitsukaze and Average of Substring【暴力、前缀】D.Tokitsukaze and Development Task【记忆化搜索】E.Tokitsukaze and Colorful Chessboard【预处理&#xff0c;二…...

WIFI P2P架构

WI-FI P2P定义架构3个组件组织结构技术标准P2P DiscoveryDevice Discovery&#xff08;扫描&#xff09;流程p2p probe 管理帧Group Formation&#xff08;组网&#xff09;GO Negotiation&#xff08;GON&#xff09;流程P2P Public Action管理帧Provision Discovery&#xff…...

架构师之中台思维_系统发展之路_结果和抽象之间平衡的艺术

父文章 如何成为一名架构师,架构师成长之路_golang架构师成长之路_个人渣记录仅为自己搜索用的博客-CSDN博客 任何系统的发展都是如此. 1. 业务增长 2. 烟囱增长 _ 结果优先 _ 太快去抽象抽象不好 3. 太多的烟囱, 3.1 抽象复用为平台 3.2 面对更多新的业务,提供不同的枚举值…...

23届非科班选手秋招转码指南

1.秋招情况介绍 1.1自我介绍 我是一名23届非科班转码选手&#xff0c;本硕均就读于某211院校机械专业&#xff0c;秋招共计拿下12份offer&#xff0c;包括大疆创新、海康威视、联发科技、理想汽车、中电28、阳光电源等各行业、各种性质企业的意向。主要的投递岗位为嵌入式软件…...

《传感器技术》考试学习笔记

文章目录一、选择题二、简答题1.什么是传感器&#xff1f;传感器的共性是哪些&#xff1f;2.差动变气隙式传感器电感传感器的灵敏度推导过程是什么&#xff08;推导公式&#xff09;&#xff1f;与单极性进行比较它们的优缺点是哪些&#xff1f;3.霍尔传感器如何进行微位移测量…...

第十五章 opengl之高级OpenGL(模板测试)

OpenGL模板测试模板函数物体轮廓模板测试 当片段着色器处理完一个片段后&#xff0c;模板测试就会开始执行。类似于深度测试&#xff0c;模板测试也可能会丢弃片段。被保留的片段会进入深度测试&#xff0c;可能会丢弃更多的片段。 模板测试是根据模板缓冲来进行的。一个模板缓…...

【C语言蓝桥杯每日一题】—— 单词分析

【C语言蓝桥杯每日一题】—— 单词分析&#x1f60e;前言&#x1f64c;单词分析&#x1f64c;总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右铭&#xff1a;全神贯注的上吧&#xff01;&#xff01;&#xff01; &#x1f60a;作者…...

Web2:Tomcat

二.Web2&#xff1a;Tomcat 1.Tomcat的配置 2.Tomcat的工作方式 3.Tomcat服务器的虚拟映射 4.Tomcat部署到IDEA中使用 二.Web2&#xff1a;Tomcat 1.Tomcat的配置 ①安装下载Tomcat 配置好JAVA_HOME启动时保证端口号8080不被占用 ②下载后的目录结构 bin 启动或关闭to…...

C++语法规则2(C++面向对象)

继承 面向对象程序设计中最重要的一个概念是继承。继承允许我们依据另一个类来定义一个类&#xff0c;这使得创建和维护一个应用程序变得更容易。这样做&#xff0c;也达到了重用代码功能和提高执行效率的效果。 当创建一个类时&#xff0c;您不需要重新编写新的数据成员和成…...

第八批国家药品集中采购-(附药品集采目录明细下载)

2023年3月2日&#xff0c;‘国家组织药品联合采购办公室’发出了《全国药品集中采购文件》&#xff0c;宣告了第八批国家组织药品集中采购工作正式开展&#xff0c;其公告中还包含三个附表分别为‘采购品种目录’、‘各地区首年约定采购量’、‘各采购品种首年约定采购量’&…...

政府工作报告连提9年科技创新 企业研发如何“又快又好”

今年的政府工作报告&#xff0c; “科技创新” 这一描述连续出现7次&#xff0c;这也是自2015年开始&#xff0c; “科技创新” 这一概念在全国“两会”政府工作报告中连续九年被提到。政府工作报告指出&#xff0c;科技政策要聚焦自立自强&#xff0c;完善新型举国体制&#x…...

GM8773C 是一款 1:2 DSI 桥接芯片,可实现 4 路进 8 路出转换器功能、视频分离器功能。

GM8773C 是一款 1&#xff1a;2 DSI 桥接芯片&#xff0c;可实现 4 路进 8 路出转换器功能、视频分离器功能。芯片内集成了一个 4 路单一链路的 MIPI DSI 接收器和 8 路双链路 MIPI DSI 发送器。 接 收 器 每 路 可 以 支 持 到 2.0Gbps/lane &#xff0c; 可 以 最 高 支 持 到…...

Java常用包名和说明

包名主要功能java.applet提供了创建applet需要的所有类java.awt.*提供了创建用户界面以及绘制和管理图形、图像的类java.beans.*提供了开发Java Beans需要的所有类java.io提供了通过数据流、对象序列以及文件系统实现的系统输入、输出java.lang.*Java编程语言的基本类库java.ma…...

dva01-初识

背景 React 本身只是一个 DOM 的抽象层&#xff0c;使用组件构建虚拟 DOM。如果开发大应用&#xff0c;还需要解决一个问题。 通信&#xff1a;React 只提供了一种传参手段&#xff0c;后续数据变化非常麻烦&#xff0c;无法适用于大应用。数据流&#xff1a;每次要更新数据&…...

信捷 XDH Ethercat A_WRITE指令

本指令修改指令轴的当前位置。 什么时候需要用本指令呢&#xff1f;换句话说&#xff0c;用本指令后&#xff0c;坐标原点修改了偏移了。如果在回原点后&#xff0c;往前走了一段距离x,如果是用绝对模式执行把位置修改成0&#xff0c;那么下一次开始每次做绝对运动A_MOVEA&…...

Spring Cloud ( Eureka集群的搭建 )

操作步骤&#xff1a; 添加主机映射创建Eureka服务 导入依赖编写启动类编写yml复制服务实例测试一、添加主机映射 以 Windows系统为例&#xff0c;如果要构建集群&#xff0c;需要修改 hosts 文件&#xff0c;为其添加主机名的映射。 打开C:\Windows\System32\drivers\etc\h…...

Python re 模块

正则表达式是一种小型、高度专业化的编程语言。适用于任何语言&#xff0c;在 Python 中通过 re 模块实现。正则模式被编译成一系列的字节码&#xff0c;然后由 C 语言编写的匹配引擎执行。给字符串模糊匹配 正则用于匹配字符串&#xff0c;匹配字符串可以完全匹配和模糊匹配&…...

为什么越来越多的人开始学习大数据

因为根据国内的发展形势&#xff0c;大数据未来的发展前景会非常好&#xff0c;前景好需求高&#xff0c;自然会吸引越来越多的人进入大数据行业 我国市场环境处于急需大数据人才但人才不足的阶段&#xff0c;所以未来大数据领域会有很多的就业机遇。 2022年春季&#xff0c;…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...