【代码随想录|回溯算法排列问题】
491.非减子序列
题目链接. - 力扣(LeetCode)
这里和子集问题||很像,但是这里要的是非递减的子序列,要按照给的数组的顺序来进行排序,就是如果我给定的数组是[4,4,3,2,1],如果用子集||的做法先进行排序得到[1,2,3,4,4],那我就会收集得到[1,2][2,3][3,4][4,4]等等子集,但是这道题的话我得到的集合只有[4,4],就是这里我只从我给的数组里进行排序,给非递减的子集。
去结点操作:
一、进行树层去重
但是用之前的方法排序后看used数组里面我两个元素到底用没用已经不可行了,所以这里加了一个set数组,来进行去重,只要我没有和之前相同的元素那就继续取
(这里不用回溯掉used 我觉得是之前回溯是因used定义是在主函数里面,你不手动回溯那个值不会主动变为0,而这里直接定义函数里,在每一层循环外面,我一进去递归就重开了一个set数组,天然的就不用进行回溯了)
二、去掉递减的结点
去结点的时候,我们把我们遍历到的节点和收集到的结点进行比较,如果这个节点比我们收集到的结点小了,那么我们硬塞进去就不是递增序列了,所以直接continue进行收集下一个结点。
class Solution {
public:
vector<int>path;
vector<vector<int>> result;
void backtracing (vector<int>& nums,int startindex){if(path.size()>1){result.push_back(path);//子集在2到2以上再进行收集}unordered_set<int> used;//每一层都会重置usedfor(int i=startindex;i<nums.size();i++){if(!path.empty()&&nums[i]<path.back()||used.find(nums[i])!=used.end()){continue;//去掉要进行递减的结点和树层去重}path.push_back(nums[i]);used.insert(nums[i]);//把nums[i]的值放used里面好进行判断到底用没用过backtracing (nums,i+1);path.pop_back();}
}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracing (nums,0);return result;}
};
46.全排列
题目链接https://leetcode.cn/problems/permutations
要求是同一个数不能重复选取嘛,所以要用到used数组
这个是排列问题,需要返回和传进来数组大小相等的全排列数组,所以排列问题就不用设置startindex了,因为不用对前面的数进行去重,但是要设置一个used数组,不能重复选择同一个元素。
class Solution {//正确代码
public:
vector<int>path;
vector<vector<int>>result;void backtracking(vector<int>& nums,vector<bool>used){if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i]==true){//用过的数就跳过continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,used);path.pop_back();used[i]=false;}}vector<vector<int>> permute(vector<int>& nums) {vector<bool>used(nums.size(),false);backtracking(nums,used);return result;}
};
注意这里只能是递归到used数组为true的时候continue进行下一次选取,如果像我一样直接对used等于0来进行判断的话,那它等于1的时候就不会有限制,就会一直进行递归进行循环,直到栈空(离大谱..)
for(int i=0;i<nums.size();i++){//错误代码if(used[i]==false){path.push_back(nums[i]);used[i]=true;}backtracking(nums,used);path.pop_back();used[i]=false;}
47.全排列||
题目链接https://leetcode.cn/problems/permutations-ii
这道题和46.全排列不太一样的就是这里给的nums数组有重复值,比如nums给[1,1,2],那么如果我按没有重复数的做法来做的话就会有两个[1,1,2],那这里就是不允许的,所以我们要在上一道题的基础上多进行一次去重,就是像组合问题一样进行树层去重,同一树层上的数continue不再选取。
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, vector<bool> used) {if (nums.size() == path.size()) {result.push_back(path);//到了nums大小就收集到result,然后返回return;}for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)continue;//树层去重if (used[i] == true)//选过的不再重复选continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());//把nums排序used数组好进行比较进行树层去重backtracking(nums, used);return result;}
};
相关文章:
【代码随想录|回溯算法排列问题】
491.非减子序列 题目链接. - 力扣(LeetCode) 这里和子集问题||很像,但是这里要的是非递减的子序列,要按照给的数组的顺序来进行排序,就是如果我给定的数组是[4,4,3,2,1],如果用子集||的做法先进行排序得到…...
Azure Kubernetes Service (AKS)资源优化策略
针对Azure Kubernetes Service (AKS)的资源优化策略,可以从多个维度进行考虑和实施,以提升集群的性能、效率和资源利用率。以下是一些关键的优化策略: 一、 Pod资源请求和限制 设置Pod请求和限制:在YAML清单中为所有Pod设置CPU和…...
R语言 | 宽数据变成一列,保留对应的行名和列名
对应稀疏矩阵 转为 宽数据框,见 数据格式转换 | 稀疏矩阵3列还原为原始矩阵/数据框,自定义函数 df3toMatrix() 目的:比如查看鸢尾花整体的指标分布,4个指标分开,画到一个图中。每个品种画一个图。 1.数据整理&#…...
RTSP播放器EasyPlayer.js播放器在webview环境下,PC和安卓能够正常播放,IOS环境下播放器会黑屏无法播放
流媒体技术分为顺序流式传输和实时流式传输两种。顺序流式传输允许用户在下载的同时观看,而实时流式传输则允许用户实时观看内容。 流媒体播放器负责解码和呈现内容,常见的播放器包括VLC和HTML5播放器等。流媒体技术的应用场景广泛,包括娱乐…...
.NET周刊【11月第3期 2024-11-17】
国内文章 .NET 9使用Scalar替代Swagger https://www.cnblogs.com/netry/p/18543378/scalar-an-alternative-to-swagger-in-dotnet-9 .NET 9 移除了 Swashbuckle.AspNetCore,因为其维护不力,并转向 Microsoft.AspNetCore.OpenApi。除了 Swashbuckle&am…...
c语言数据22数组使用
1.1数组分配的空间 int a[10]{1,2,3,4,5,6,7,8,9,10};//分配空间 元素类型大小int4*元素个数1040byte 元素之间空间连续 数组名代表数组首元素地址;a 取的是a[0]的地址;&a 是整个数组的地址 说明: 数组首元素地址: 0号元…...
深入理解TensorFlow中的形状处理函数
摘要 在深度学习模型的构建过程中,张量(Tensor)的形状管理是一项至关重要的任务。特别是在使用TensorFlow等框架时,确保张量的形状符合预期是保证模型正确运行的基础。本文将详细介绍几个常用的形状处理函数,包括get_…...
MySQL数据库3——函数与约束
一.函数 1.字符串函数 MySQL中内置了很多字符串函数,常用的几个如下: 使用方法: SELECT 函数名(参数);注意:MySQL中的索引值即下标都是从1开始的。 2.数值函数 常见的数值函数如下: 使用方法: SELECT…...
⾃动化运维利器 Ansible-Jinja2
Ansible-Jinja2 一、Ansible Jinja2模板背景介绍二、 JinJa2 模板2.1 JinJa2 是什么2.2 JinJa2逻辑控制 三、如何使用模板四、实例演示 按顺序食用,口味更佳 ( 1 ) ⾃动化运维利器Ansible-基础 ( 2 ) ⾃动化运维利器 Ansible-Playbook ( 3 ) ⾃动化运维利器 Ansible…...
博客文章怎么设计分类与标签
首发地址(欢迎大家访问):博客文章怎么设计分类与标签 新网站基本上算是迁移完了,迁移之后在写文章的过程中,发现个人的文章分类和标签做的太混乱了,分类做的像标签,标签也不是特别的丰富&#x…...
FastDDS之DataSharing
目录 原理说明限制条件配置Data-Sharing delivery kindData-sharing domain identifiers最大domain identifiers数量共享内存目录 DataReader和DataWriter的history耦合DataAck阻塞复用 本文详细记录Fast DDS中Data Sharing的实现原理和代码分析。 DataSharing的概念࿱…...
计算机网络在线测试-概述
单项选择题 第1题 数据通信中,数据传输速率(比特率,bps)是指每秒钟发送的()。 二进制位数 (我的答案) 符号数 字节数 码元数 第2题 一座大楼内的一个计算机网络系统…...
【MySQL】数据库必考知识点:查询操作全面详解与深度解剖
前言:本节内容讲述基本查询, 基本查询要分为两篇文章进行讲解。 本篇文章主要讲解的是表内删除数据、查询结果进行插入、聚合统计、分组聚合统计。 如果想要学习对应知识的可以观看哦。 ps:本篇内容友友们只要会创建表了就可以看起来了哦!&am…...
鲸鱼机器人和乐高机器人的比较
鲸鱼机器人和乐高机器人各有其独特的优势和特点,家长在选择时可以根据孩子的年龄、兴趣、经济能力等因素进行综合考虑,选择最适合孩子的教育机器人产品。 优势 鲸鱼机器人 1)价格亲民:鲸鱼机器人的产品价格相对乐高更为亲民&…...
游戏引擎学习第15天
视频参考:https://www.bilibili.com/video/BV1mbUBY7E24 关于游戏中文件输入输出(IO)操作的讨论。主要分为两类: 只读资产的加载 这部分主要涉及游戏中用于展示和运行的只读资源,例如音乐、音效、美术资源(如 3D 模型和…...
详解模版类pair
目录 一、pair简介 二、 pair的创建 三、pair的赋值 四、pair的排序 (1)用sort默认排序 (2)用sort中的自定义排序进行排序 五、pair的交换操作 一、pair简介 pair是一个模版类,可以存储两个值的键值对.first以…...
AI驱动的桌面笔记应用Reor
网友 竹林风 说,已经成功的用 mxbai-embed-large 映射到 text-embedding-ada-002,并测试成功了。不愧是爱折腾的人,老苏还没时间试,因为又找到了另一个支持 AI 的桌面版笔记 Reor Reor 简介 什么是 Reor ? Reor 是一款由人工智…...
搜维尔科技:使用sensglove触觉反馈手套进行虚拟拆装操作
使用sensglove触觉反馈手套进行虚拟拆装操作 搜维尔科技:使用sensglove触觉反馈手套进行虚拟拆装操作...
深入理解电子邮件安全:SPF、DKIM 和 DMARC 完全指南
引言 在当今数字时代,电子邮件已经成为我们日常通信中不可或缺的一部分。然而,随之而来的安全问题也日益突出。邮件欺诈、钓鱼攻击和垃圾邮件等威胁不断增加,这促使了多种邮件安全验证机制的出现。本文将深入探讨三个最重要的邮件安全协议&a…...
【有啥问啥】复习一下什么是NMS(非极大值抑制)?
复习一下什么是NMS(非极大值抑制)? 什么是NMS? NMS(Non-Maximum Suppression)即非极大值抑制,是一种在计算机视觉领域,尤其是目标检测任务中广泛应用的后处理算法。其核心思想是抑…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
