【蓝桥杯速成】| 11.回溯 之 子集问题
题目一:子集
问题描述
78. 子集 - 力扣(LeetCode)
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums
中的所有元素 互不相同
解题步骤
根据前面的做题经验,这一题应该比较容易AC
有没有觉得数组所有可能的子集很像我们每一层遍历的结果,
所以关于子集问题,我们需要的结果不是叶子结点,而是所有结点
那么其它代码逻辑不变,我们只需要改一下收集结果的位置即可
把result.push_back(path);这行代码从终止条件中拿出来
就表示我们每一步都会执行这一句,
空集是所有集合的子集,那么刚调用这个backtracking函数我们就会先加入[]
后面就是遍历一下就加入一下,输出顺序是纵深的,因为这里用的递归调用
对于终止条件,即用完数组所有元素,
那么我们用于指向遍历元素的startindex必然大于等于nums.size()
但其实也可以不加终止条件,因为我们的for循环会让i<nums.size(),它已经结束了
完整代码如下!
code
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startindex){//返回的是每个结点result.push_back(path);if(startindex>=nums.size()){return;}for(int i=startindex;i<nums.size();i++){path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return result;}
};
题目二:子集②
问题描述
90. 子集 II - 力扣(LeetCode)
给你一个整数数组 nums
,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
解题步骤
这题与上一题的区别就在于nums数组中可能包含重复元素
那么这个关键点和我们之前做过的组合总和②是一样的处理
重点就在于去重
我们需要排掉所有在同一层上相同的结果
但同时保证纵向不会被误判,因为纵向取数产生的数字重复,并不意味着答案重复
纵向是不断把子集变长的过程,加进来的都是从数组中取出的,
取出动作并不存在重复,哪怕数字一样但它不是从nums的同一位置取出的!
所以这一题我们要在单层遍历中加入去重代码即可
if(i>0 && nums[i]==nums[i-1] && used[i-1]==False)
为了方便判断重复元素,我们在主函数中会先对nums数组进行排序
那么遍历到第i个元素就可以通过 nums[i]==nums[i-1]这个代码判断是否出现重复元素
为了保证nums[i-1]合法,所以i必须大于0,
因为每次操作我们会用used数组标记数字的使用情况,
在纵向的递归中,used[i]=used[i-1]=true
但在同层当中,由于前一步存在回溯,我们的used[i-1]==false
翻译一下就是,上一层用过后放回去假装没用过
符合以上条件就是我们的重复元素,那么直接continue不需要继续执行
完整代码如下,需要注意在主函数中定义used数组和对nums数组进行排序!
code
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startindex,vector<bool>& used){//返回的是每个结点result.push_back(path);for(int i=startindex;i<nums.size();i++){if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){//去重continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,i+1,used);used[i]=false;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return result;}
};
题目三:非递减子序列
问题描述
491. 非递减子序列 - 力扣(LeetCode)
给你一个整数数组 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
解题步骤
这一题可以看成上一题的升级版,它在要求不重复的情况下同时要求该子序列递增
但需要注意的是这里的子序列是按照原数组排序生成的,
我们不能使用sort函数,不然结果也是不正确的
所以我们要换一种去重逻辑
但仍旧需要做到只除去同一层的重复项
不除去纵向的重复元素
那么排序不能用,used数组也就不能用了,
我们需要一个新的辅助,对于去重首选unordered_set,
可以利用find函数很快检查到是否已经出现过
那么我们在处理这一层元素前就需要先定义好这个uset
unordered_ser<int> uset;
再进入到遍历逻辑中,挨个检查元素是否符合题意
如果该元素之前已经用过,那么它必然可以在uset中找到
所以第一个不符合的情况是
if(uset.find(nums[i])!=uset.end())
要确保子序列递增,那么nums[i]不能小于当前path的最后一个元素,即path.back()
为防止出现path为空时的错误,先判断path.empty()为false
则第二个不符合情况如下
if(!path.empty() && nums[i]<path.back)
可以合并这两种情况,continue
没有出现以上情况,则处理该结点
把nums[i]加入uset中做记录
再加入该数到path中
递归调用后回溯
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
这里的uset不需要回溯,因为我们在每一层使用它,
如果是递归会重新定义,内容被清空不影响判断去重
此外在加入结果到result数组中时,我们要先判断path.size()>=2,
这也是题目条件之一,要求子序列长度大于等于2
if(path.size()>=2){
result.push_back(path);
}
组合所有代码,即可得到完整版如下方!
code
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int startindex){if(path.size()>=2){result.push_back(path);}unordered_set<int> uset; // 使用set来对本层元素进行去重for(int i=startindex;i<nums.size();i++){if(!path.empty() && nums[i]<path.back() || uset.find(nums[i])!=uset.end()) {continue;}uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return result;}
};
相关文章:
【蓝桥杯速成】| 11.回溯 之 子集问题
题目一:子集 问题描述 78. 子集 - 力扣(LeetCode) 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例…...
统计矩的高阶推广:经验还是理论推导?
矩的发展既是经验总结的结果,也是数学理论推导的产物。研究者们在分析数据、描述物理现象的过程中,发现了低阶矩与日常物理概念(如质心、惯性)之间的紧密联系,而高阶矩的应用往往出现在更复杂的数学体系中,…...
SpringBoot2集成Elasticsearch8(使用spring-boot-starter-data-elasticsearch)
写在前面 使用spring-boot-starter-data-elasticsearch集成Elasticsearch8? What? 官方写的不支持啊?让我们来看下官方给出的版本建议。 官方地址: https://docs.spring.io/spring-data/elasticsearch/reference/elasticsearch/versions.…...
Postgresql源码(142)子查询提升pull_up_sublinks
1 案例 drop table t_fun01; create table t_fun01 (image_id numeric primary key, content_id varchar(50), file_code varchar(20)); create index idx3 on t_fun01(content_id); create index idx4 on t_fun01(file_code); insert into t_fun01 select t.i, t.i%10, t.i%1…...
sonar代码检测研究及平台搭建
为了实现提交代码自动检测代码缺陷,本文介绍了一种将jenkins与gitlab集成的自动检测机制,如需应用于生产级开发流程,可在此基础上进行功能丰富和扩展,本文仅进行了原理性搭建。 一、基础环境准备 与sonar配合使用的jenkins和gitlab基础软件…...
清华大学:DeepSeek从入门到精通系列教程1-9讲(持续更新中)|大礼包免费下载
导 读INTRODUCTION 今天分享由清华大学新闻与传播学院、人工智能学院双聘教授沈阳老师团队倾力打造的《DeepSeek从入门到精通系列教程1-9讲(持续更新中)》,包含:《DeepSeek:从入门到精通》《DeepSeek如何赋能职场应用》…...
使用Python可视化图结构:从GraphML文件生成节点关系图(lightrag 生成)
引言 在数据可视化领域,图结构(Graph)常用于展示实体间的复杂关系。例如,文学分析中的角色关系、社交网络中的用户互动等。本文将通过一个实际案例,演示如何使用 NetworkX 和 Matplotlib 从 GraphML 文件生成节点关系…...
排序复习_代码纯享
头文件 #pragma once #include<iostream> #include<vector> #include<utility> using std::vector; using std::cout; using std::cin; using std::endl; using std::swap;//插入排序 //1、直接插入排序(稳定) void InsertSort(vecto…...
Docker Hub Mirror 终极解决方案——0成本,超高速!
CNB Docker Mirror (cdm) CNB Docker Mirror 是一个基于 CNB 的 Docker 镜像加速工具,提供本地镜像加速功能。 功能特性 镜像加速:在本地启动连接到 CNB 环境的 Docker 镜像加速服务,然后通过配置 Docker 客户端实现镜像加速下载自动重连&…...
2000-2019年各省地方财政车船税数据
2000-2019年各省地方财政车船税数据 1、时间:2000-2019年 2、来源:国家统计局、统计年鉴 3、指标:行政区划代码、地区、年份、地方财政车船税 4、范围:31省 5、指标说明:车船税作为地方财政的重要组成部分&#x…...
c#处理算数溢出的情况
在C#中,算术运算的溢出处理可以通过 checked 和 unchecked 关键字控制,默认行为是 静默截断(unchecked模式),但可以通过配置或代码块显式调整。以下是详细说明: 1. 默认行为(unchecked模式&…...
Java「Deque」 方法详解:从入门到实战
Java Deque 各种方法解析:从入门到实战 在 Java 编程中,Deque(双端队列)是一个功能强大的数据结构,允许开发者从队列的两端高效地添加、删除和检查元素。作为 java.util 包中的一部分,Deque 接口继承自 Qu…...
简记_FPGA 硬件最小系统设计
一、FPGA板级设计的五要素 1.1、电源电路 核心电压:一般为固定值 IO电压:FPGA的IO分为多个bank,同一个bank的不同IO引脚电压相同,不同bank的电压可以不同 辅助电压:除了核心电压和IO电压,FPGA工作所需的…...
C++题目
1、内存管理 1.内存模型 栈:在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。 堆:就是那些由new分配的内存块,其释放由程序员控制(一个new对应一个delete)…...
Vulhub-jangow-01-1.0.1通关攻略
第0步: 打开靶机,按下shift,出现下图界面 在此页面按下e键,进入如下界面, 将ro 替换为 rw signie init/bin/bash 替换完毕后,按下Ctrl键X键,进入如下页面 ip a查看网卡信息 编辑配置文件网卡信…...
入剖析 Android Compose 框架的关键帧动画(keyframes、Animatable)(二十三)
深入剖析 Android Compose 框架的关键帧动画(keyframes、Animatable) 引言 在当今的 Android 应用开发领域,用户体验已成为衡量一款应用成功与否的关键因素之一。而动画作为提升用户体验的重要手段,能够为应用增添生动性和交互性…...
java中的枚举类型和c,c++的有区别吗?c,c++的枚举,结构体,联合体,三种数据有什么区别和联系
Java 枚举类型与 C、C 枚举类型的区别 1. 类型安全 Java:Java 的枚举类型是类型安全的。枚举常量是枚举类型的实例,编译器会严格检查传递的参数是否为该枚举类型的有效常量。例如: java Apply enum Color { RED, GREEN, BLUE } // 编译器会检…...
详解Redis的持久化与数据可靠性
Redis持久化与数据可靠性详解(结合实例) Redis作为内存数据库,持久化是保证数据不丢失的核心机制。它通过将内存数据保存到磁盘,确保服务器重启后能恢复数据。Redis提供RDB、AOF和混合持久化三种方式,下面通过实例和操…...
1、mysql基础篇--概述
关系型数据库(RDBMS) 概念特点:数据模型: 概念 建立在关系模型基础上,有多张表相互连接的二维表组成的数据库 特点: 1、使用表存储,格式统一,便于维护 2、使用sql语言操作&#…...
【Tiny RDM】Redis客户端工具
Tiny RDM Tiny RDM是一款现代化、轻量级、跨平台的Redis客户端,支持Mac、Windows和Linux,目前在Github上已有10kStar。 Github 项目地址: https://github.com/tiny-craft/tiny-rdm 功能特性 极度轻量,基于Webview2,…...
常见框架漏洞攻略-Shiro篇
漏洞名称 Shiro rememberMe反序列化漏洞 漏洞简介 Apache Shiro是⼀个强⼤易⽤的Java安全框架,提供了认证、授权、加密和会话管理等功能。Shiro框架直观、易⽤,同时也能提供健壮的安全性。 漏洞原理 在Shiro框架下,⽤户登陆成功后会⽣成…...
常见框架漏洞之一:Thinkphp5x
ThinkPHP是为了简化企业级应⽤开发和敏捷WEB应⽤开发⽽诞⽣的,是⼀个快速、兼容⽽且简单的轻量级国产PHP开发框架,诞⽣于2006年初,原名FCS,2007年元旦正式更名为 ThinkPHP,遵循Apache2开源协议发布,从Stru…...
MORL4PDEs:基于多目标优化与强化学习的数据驱动偏微分方程发现
摘要:本文提出了一种结合多目标优化与强化学习的数据驱动方法MORL4PDEs,用于从复杂系统观测数据中发现简洁的偏微分方程(PDE)。该方法无需预定义候选函数库,通过神经网络代理生成符号表达式,结合遗传算法优…...
UniApp和微信小程序中v-switch夜间模式动画开关
UniApp兼容版 <template><view><view class"main-container" :style"{ backgroundColor: value ? #45e3f9 : #20114c,transform:scale(${size})}" tap"onClick"><view class"content" :style"{ left: val…...
六十天Linux从0到项目搭建第四天(通配符命令、其他命令、压缩解压工具、shell的感性理解、linux权限解析)
通配符(Wildcard) 是 Shell 提供的特殊字符,用于 匹配文件名或路径名,可以代替一个或多个字符,使得命令能批量操作文件,而无需手动输入每个文件名。 典型用法 * 匹配任意字符 *.txt → 匹配所有 .txt 文…...
RAG优化:python从零实现自适应检索增强Adaptive Retrieval
开篇:当RAG遇上“自适应大脑”,检索从此不再“一根筋”!🧠 想象一下,你的AI助手是个超级聪明的“学霸”,但有时候却像个“一根筋”的机器人——无论你问它什么,它都用同一种方式去回答。问它“什么是XAI?”它给你一堆定义;问它“AI发展太快了吗?”它还是给你一堆定…...
C语言实现的冰墩墩
在windows系统下,vs 2022编译。 其中#include <graphics.h>需要自己下载安装。 环境配置没什么难度,直接上demo。 代码如下: #include <graphics.h> #include <conio.h> #include <math.h> #define PI acos(-1.0…...
【构建CV图像识别系统】从传统方法到深度学习
目录 1. 图像的基本概念1.1 像素与色彩1.2 过滤与卷积 2. 图像分类与检测3. 图像特征的提取3.1 全局特征3.2 局部特征3.2.1 边缘(Edge)3.2.2 角点(Corner)3.2.3 SIFT 特征 4. 传统方法与深度学习在图像识别中的应用4.1 基于传统方…...
在Centos 7环境下安装MySQL
前言:在安装与卸载MySQL时,用户需切换为root,这样安装之后,普通用户也能够使用。 Tips:我们在刚开始学习时,尽量全部使用root进行,适应mysql语句,后面学了用户管理,就可以考虑新建普…...
【机器学习基础 4】 Pandas库
一、Pandas库简介 Pandas 是一个开源的 Python 数据分析库,主要用于数据清洗、处理、探索与分析。其核心数据结构是 Series(一维数据)和 DataFrame(二维表格数据),可以让我们高效地操作结构化数据。Pandas …...
干部监督预警系统的定义与功能
一、干部监督预警系统是什么? 干部监督预警系统是通过整合多源数据(如干部档案、履职表现、廉政记录、舆情反馈等),利用大数据分析、人工智能等技术,对干部行为进行实时监测、风险评估和分级预警的数字化管理工具。 二…...
可视化图解算法:链表的奇偶重排(排序链表)
1. 题目 描述 给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。 注意是节点的编号而非节点的数值。 数据范围:节点数量满足 0≤n≤105,节点中的值都满足 0≤val≤10000 要…...
获取小红书笔记详情接口的详细指南
一、引言 小红书作为一个集社交、购物、分享于一体的综合性平台,拥有海量的用户和丰富的笔记内容。小红书笔记详情API接口为开发者提供了一种高效获取笔记详细信息的方法,包括笔记的标题、正文、图片、视频、标签、点赞数、评论数等。这些数据可以帮助开…...
麒麟系统运维指令
麒麟系统运维指令 麒麟系统运维指令1、 查看系统版本2、查看系统信息3、用户与权限管理4. 网络相关命令5. 包管理6. 文件操作7. 进程管理 麒麟系统运维指令 1、 查看系统版本 目的指令查看操作系统版本信息cat /etc/os-release查看操作系统版本信息hostnamectl查看内核版本un…...
pyqt SQL Server 数据库查询
一、概述 本项目旨在开发一个基于 Python 和 PyQt6 的数据库查询工具,该工具能够连接到 SQL Server 数据库,显示数据库中的表名,支持用户输入 SQL 查询语句进行数据查询,并将查询结果展示在表格中。同时,为了提升用户…...
抓包软件【Fiddler】
我叫补三补四,很高兴见到大家,欢迎一起学习交流和进步 今天来讲一讲Fiddler 什么是Fidder Fiddler是一款非常流行并且实用的HTTP抓包工具,原理是在电脑上开启一个HTTP代理服务器,然后转发所有的HTTP请求和响应。是用C#开发的工具…...
SpringCould微服务架构之Docker(1)
项目中微服务比较多的时候,一个一个手动的部署太麻烦了,所以就需要用到Docker。 项目部署中的问题: Docker是一种快速交付应用、运行应用的技术。...
计算图(Computation Graph)
在强化学习中,TensorFlow的计算图(Computation Graph)是用于描述模型结构和训练流程的核心机制。 1. 计算图的基本概念 定义:计算图是TensorFlow中表示数学运算和数据流动的有向图。图中的节点(Nodes)代表…...
邮件营销:如何设置合适的发送频率
在邮件营销里,把握好发送频率特别关键,这直接关系到客户愿不愿意搭理你的邮件,以及邮件营销能不能达到预期效果。下面这几个步骤和建议,能帮你找到合适的邮件发送频率: 一、了解目标受众 分析客户行为:查…...
React项目中,递归写法获取tree的id集合
后端接口返回一个childrens的树,最后要拿到的是每个childrens下第一个对象的id集合,用于编辑页的回显 采用的是递归写法!!!!!!!! const categoryIds: Array&…...
深入解析Linux网络、安全与容器技术
1. Netfilter:Linux内核的包处理框架 Netfilter 是Linux内核中用于控制网络数据包的核心机制,负责处理数据包的过滤、修改和转发。其核心功能包括: 包过滤(Packet Filtering):根据规则允许或拒绝数据包通过…...
AF3 Rotation 类解读
Rotation 类(rigid_utils 模块)是 AlphaFold3 中用于 3D旋转 的核心组件,支持两种旋转表示: 1️⃣ 旋转矩阵 (3x3) 2️⃣ 四元数 (quaternion, 4元向量) 👉 设计目标: 允许灵活选择 旋转矩阵 或 四元数 封装了常用的 旋转操作(组合、逆旋转、应用到点上等) 像 torch.…...
数据预处理习题
简述常用的文本数据类型。 结构化文本:如数据库中的表格数据、JSON/XML格式数据,具有明确的字段和层级关系。非结构化文本:如自然语言文本(新闻、社交媒体内容)、长文档(书籍、论文)࿰…...
常见框架漏洞—中间件IIS
一.IIS6.x篇 1.在Windows server 2003中搭建网站 2.访问网站,并对该网站进行抓包 3.修改提交方式为PUT,然后写入木马 4.修改提交方式为MOVE,令将其更名为脚本⽂档后缀 5.我们在Windows server 2003中可以看到我们上传的shell.asp 6.我们在网…...
群体智能优化算法-蚁狮优化算法(Ant Lion Optimizer, ALO,含Matlab源代码)
一、文章摘要 蚁狮优化算法(Ant Lion Optimizer,ALO)是一种新颖的元启发式算法,由Mirjalili提出,其灵感来源于自然界中蚁狮幼虫构筑陷阱捕猎蚂蚁的行为。该算法通过模拟蚂蚁的随机游走、蚁狮的陷阱机制、陷阱缩小及精…...
【计算机视觉】数据增强
一、数据增强的意义 在深度学习中,数据集往往有限,而模型需要大量的样本来学习特征。数据增强技术通过对图像进行如下变换: 扩充样本数量:利用已有数据生成新的样本。提高模型鲁棒性:使模型适应不同的图像变换&#…...
BERT文本分类实战----美团外卖评论情绪分类
HuggingFace 提供了巨大的模型库,虽然其中的很多模型性能表现出色,但这些模型往往是在广义的数据集上训练的,缺乏针对特定数据集的优化,所以在获得一个合适的模型之后,往往还要针对具体任务的特定数据集进行二次训练&a…...
Chrome 133 版本开发者工具(DevTools)更新内容
Chrome 133 版本开发者工具(DevTools)更新内容 一、持久化的 AI 聊天记录 AI 助手面板会在本地持久化聊天记录,即使重新加载 DevTools 或 Chrome,也可以查看之前与 Gemini 的对话内容。 二、Performance 面板改进 此版本为 Per…...
大模型应用(Java)2025/3/24
大佬视频👉使用Java实现一个基础的大模型RAG问答对话系统_哔哩哔哩_bilibili 需求 让大模型来理解知识库内容,并根据知识库回答。 通过本次应用我学到了: RAG工程的基本处理框架流程(基于java)向量数据库的基础使用…...
基于Sentinel-1A GRD洪涝淹没范围提取(SDWI阈值法和OSTU自动阈值法)
0 前言 两幅灾前和灾后的遥感影像经过SARscape配准、滤波、辐射定标预处理之后,使用GDAL库分别使用SDWI阈值法和OSTU自动阈值法提取洪涝淹没范围 1 ENVI 5.6和SARscape5.6安装 通过网盘分享的文件:ENVI5(1).6 链接: https://pan.baidu.com/s/1mKcEkC3…...