【代码随想录|回溯算法排列问题】
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)即非极大值抑制,是一种在计算机视觉领域,尤其是目标检测任务中广泛应用的后处理算法。其核心思想是抑…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
comfyui 工作流中 图生视频 如何增加视频的长度到5秒
comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗? 在ComfyUI中实现图生视频并延长到5秒,需要结合多个扩展和技巧。以下是完整解决方案: 核心工作流配置(24fps下5秒120帧) #mermaid-svg-yP…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
