【代码随想录|回溯算法排列问题】
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)即非极大值抑制,是一种在计算机视觉领域,尤其是目标检测任务中广泛应用的后处理算法。其核心思想是抑…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
