当前位置: 首页 > news >正文

【代码随想录|回溯算法排列问题】

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.非减子序列 题目链接. - 力扣&#xff08;LeetCode&#xff09; 这里和子集问题||很像&#xff0c;但是这里要的是非递减的子序列&#xff0c;要按照给的数组的顺序来进行排序&#xff0c;就是如果我给定的数组是[4,4,3,2,1]&#xff0c;如果用子集||的做法先进行排序得到…...

Azure Kubernetes Service (AKS)资源优化策略

针对Azure Kubernetes Service (AKS)的资源优化策略&#xff0c;可以从多个维度进行考虑和实施&#xff0c;以提升集群的性能、效率和资源利用率。以下是一些关键的优化策略&#xff1a; 一、 Pod资源请求和限制 设置Pod请求和限制&#xff1a;在YAML清单中为所有Pod设置CPU和…...

R语言 | 宽数据变成一列,保留对应的行名和列名

对应稀疏矩阵 转为 宽数据框&#xff0c;见 数据格式转换 | 稀疏矩阵3列还原为原始矩阵/数据框&#xff0c;自定义函数 df3toMatrix() 目的&#xff1a;比如查看鸢尾花整体的指标分布&#xff0c;4个指标分开&#xff0c;画到一个图中。每个品种画一个图。 1.数据整理&#…...

RTSP播放器EasyPlayer.js播放器在webview环境下,PC和安卓能够正常播放,IOS环境下播放器会黑屏无法播放

流媒体技术分为顺序流式传输和实时流式传输两种。顺序流式传输允许用户在下载的同时观看&#xff0c;而实时流式传输则允许用户实时观看内容。 流媒体播放器负责解码和呈现内容&#xff0c;常见的播放器包括VLC和HTML5播放器等。流媒体技术的应用场景广泛&#xff0c;包括娱乐…...

.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&#xff0c;因为其维护不力&#xff0c;并转向 Microsoft.AspNetCore.OpenApi。除了 Swashbuckle&am…...

c语言数据22数组使用

1.1数组分配的空间 int a[10]{1,2,3,4,5,6,7,8,9,10};//分配空间 元素类型大小int4*元素个数1040byte 元素之间空间连续 数组名代表数组首元素地址&#xff1b;a 取的是a[0]的地址&#xff1b;&a 是整个数组的地址 说明&#xff1a; 数组首元素地址&#xff1a; 0号元…...

深入理解TensorFlow中的形状处理函数

摘要 在深度学习模型的构建过程中&#xff0c;张量&#xff08;Tensor&#xff09;的形状管理是一项至关重要的任务。特别是在使用TensorFlow等框架时&#xff0c;确保张量的形状符合预期是保证模型正确运行的基础。本文将详细介绍几个常用的形状处理函数&#xff0c;包括get_…...

MySQL数据库3——函数与约束

一.函数 1.字符串函数 MySQL中内置了很多字符串函数&#xff0c;常用的几个如下&#xff1a; 使用方法&#xff1a; SELECT 函数名(参数);注意&#xff1a;MySQL中的索引值即下标都是从1开始的。 2.数值函数 常见的数值函数如下&#xff1a; 使用方法&#xff1a; SELECT…...

⾃动化运维利器 Ansible-Jinja2

Ansible-Jinja2 一、Ansible Jinja2模板背景介绍二、 JinJa2 模板2.1 JinJa2 是什么2.2 JinJa2逻辑控制 三、如何使用模板四、实例演示 按顺序食用&#xff0c;口味更佳 ( 1 ) ⾃动化运维利器Ansible-基础 ( 2 ) ⾃动化运维利器 Ansible-Playbook ( 3 ) ⾃动化运维利器 Ansible…...

博客文章怎么设计分类与标签

首发地址&#xff08;欢迎大家访问&#xff09;&#xff1a;博客文章怎么设计分类与标签 新网站基本上算是迁移完了&#xff0c;迁移之后在写文章的过程中&#xff0c;发现个人的文章分类和标签做的太混乱了&#xff0c;分类做的像标签&#xff0c;标签也不是特别的丰富&#x…...

FastDDS之DataSharing

目录 原理说明限制条件配置Data-Sharing delivery kindData-sharing domain identifiers最大domain identifiers数量共享内存目录 DataReader和DataWriter的history耦合DataAck阻塞复用 本文详细记录Fast DDS中Data Sharing的实现原理和代码分析。 DataSharing的概念&#xff1…...

计算机网络在线测试-概述

单项选择题 第1题 数据通信中&#xff0c;数据传输速率&#xff08;比特率&#xff0c;bps&#xff09;是指每秒钟发送的&#xff08;&#xff09;。 二进制位数 &#xff08;我的答案&#xff09; 符号数 字节数 码元数 第2题 一座大楼内的一个计算机网络系统&#xf…...

【MySQL】数据库必考知识点:查询操作全面详解与深度解剖

前言&#xff1a;本节内容讲述基本查询&#xff0c; 基本查询要分为两篇文章进行讲解。 本篇文章主要讲解的是表内删除数据、查询结果进行插入、聚合统计、分组聚合统计。 如果想要学习对应知识的可以观看哦。 ps:本篇内容友友们只要会创建表了就可以看起来了哦&#xff01;&am…...

鲸鱼机器人和乐高机器人的比较

鲸鱼机器人和乐高机器人各有其独特的优势和特点&#xff0c;家长在选择时可以根据孩子的年龄、兴趣、经济能力等因素进行综合考虑&#xff0c;选择最适合孩子的教育机器人产品。 优势 鲸鱼机器人 1&#xff09;价格亲民&#xff1a;鲸鱼机器人的产品价格相对乐高更为亲民&…...

游戏引擎学习第15天

视频参考:https://www.bilibili.com/video/BV1mbUBY7E24 关于游戏中文件输入输出&#xff08;IO&#xff09;操作的讨论。主要分为两类&#xff1a; 只读资产的加载 这部分主要涉及游戏中用于展示和运行的只读资源&#xff0c;例如音乐、音效、美术资源&#xff08;如 3D 模型和…...

详解模版类pair

目录 一、pair简介 二、 pair的创建 三、pair的赋值 四、pair的排序 &#xff08;1&#xff09;用sort默认排序 &#xff08;2&#xff09;用sort中的自定义排序进行排序 五、pair的交换操作 一、pair简介 pair是一个模版类&#xff0c;可以存储两个值的键值对.first以…...

AI驱动的桌面笔记应用Reor

网友 竹林风 说&#xff0c;已经成功的用 mxbai-embed-large 映射到 text-embedding-ada-002&#xff0c;并测试成功了。不愧是爱折腾的人&#xff0c;老苏还没时间试&#xff0c;因为又找到了另一个支持 AI 的桌面版笔记 Reor Reor 简介 什么是 Reor ? Reor 是一款由人工智…...

搜维尔科技:使用sensglove触觉反馈手套进行虚拟拆装操作

使用sensglove触觉反馈手套进行虚拟拆装操作 搜维尔科技&#xff1a;使用sensglove触觉反馈手套进行虚拟拆装操作...

深入理解电子邮件安全:SPF、DKIM 和 DMARC 完全指南

引言 在当今数字时代&#xff0c;电子邮件已经成为我们日常通信中不可或缺的一部分。然而&#xff0c;随之而来的安全问题也日益突出。邮件欺诈、钓鱼攻击和垃圾邮件等威胁不断增加&#xff0c;这促使了多种邮件安全验证机制的出现。本文将深入探讨三个最重要的邮件安全协议&a…...

【有啥问啥】复习一下什么是NMS(非极大值抑制)?

复习一下什么是NMS&#xff08;非极大值抑制&#xff09;&#xff1f; 什么是NMS&#xff1f; NMS&#xff08;Non-Maximum Suppression&#xff09;即非极大值抑制&#xff0c;是一种在计算机视觉领域&#xff0c;尤其是目标检测任务中广泛应用的后处理算法。其核心思想是抑…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...