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

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...