力扣47:全排列Ⅱ

力扣47:全排列Ⅱ

  • 题目
  • 思路
  • 代码

题目

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

思路

又是任意顺序和所有不重复的排列,显而易见我们要使用回溯的办法。
首先是回溯的结束条件即新数组的长度等于nums的长度。这道题的难点主要是如何判断当前位置已经被使用过以及当前位置是否是重复的也就是是否已经插入过了。之前的全排列Ⅰ我们使用的是bool类型的数组来判断当前位置是否被使用了,这道题同样可以使用这种方法不过想要使用这种方法我们每次都需要从头开始遍历这个bool数组从而得到一个值为false的位置。所以这次我们换一个方式我们使用过这个位置代表着什么,代表着这个位置被固定了因为他已经插入到临时数组里了它最后是要被插入到答案里的。所以我们可以定义一个变量number,这个变量代表的意思是这是第几位数字,每当我们使用过一个位置后我们就把当前位置的值和number位置的值进行交换,这样做还有一个好处就是我们不需要定义临时数组了我们直接在nums上进行交换最后长度即number等于nums的长度后直接插入nums即可。
其次就是如何解决剪枝的问题,这个问题也好解决我们在每次进入回溯函数的时候定义一个哈希表即set,在每次进入遇到一个位置时先判断它的值在set中是否能找到能找到说明它不能被固定了直接跳过到下一个位置,找不到就将该位置的值插入到set中。

代码

class Solution {
public:// 回溯void totalSort(vector<int>& nums, vector<vector<int>>& res, int number) {// 如果当前位置等于长度就直接插入if (number == nums.size()) {res.push_back(nums);return;}set<int> s;for (int i = number; i < nums.size(); i++) {// 剪枝// 如果在set中存在就说明是重复元素会导致答案重复if (s.find(nums[i]) != s.end()) {continue;}s.insert(nums[i]);// 固定使用过的值到number位置上swap(nums[i], nums[number]);totalSort(nums, res, number + 1);swap(nums[i], nums[number]);}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;totalSort(nums, res, 0);return res;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/92890.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/92890.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

学习笔记091——如何实现web登录时,密码复杂度校验?(后端)

1、创建工具类 /*** 密码复杂度校验* param password 密码*/ public static void validatePassword(String password) {// 至少8位if (password.length() < 8) {throw new IllegalArgumentException("密码长度至少为8位");}// 包含大小写字母if (!password.matche…

雪花算法snowflake分布式id生成原理详解,以及对解决时钟回拨问题几种方案讨论

一、前言在日趋复杂的分布式系统中&#xff0c;数据量越来越大&#xff0c;数据库分库分表是一贯的垂直水平做法&#xff0c;但是需要一个全局唯一ID标识一条数据或者MQ消息&#xff0c;数据库id自增就显然不能满足要求了。因为场景不同&#xff0c;分布式ID需要满足以下几个条…

【PCB设计经验】去耦电容如何布局?

0805 和 0603 以及更小 封装的电容用作于对中高频的去耦,其摆放位置是有要求的: 一、建议尽可能的靠近主控芯片的 电源管脚放置。 二、使用较宽和短的引线连接到电源和地过孔可以采用如下 图 4–1 中的图 ( 2 )、( 3)、 ( 4 )任意一种方式,避免使用长线或者较细的…

自动化运维实验

目录 一、实验拓扑 二、实验目的 三、实验步骤 实验思路&#xff1a; 代码部分&#xff1a; 四、实验结果&#xff1a; 一、实验拓扑 二、实验目的 利用python脚本&#xff0c;在本地&#xff0c;或者虚拟机里实现&#xff0c;设备CRC数量统计&#xff0c;并输出成表格 三、实验…

Wed前端第二次作业

一、作业1&#xff1a;完成自己学校的官网&#xff0c;动忘内容直接贴&#xff0c;至少三个不同的页面1、界面1&#xff08;1&#xff09;相关代码<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name&quo…

第5节 大模型分布式推理通信优化与硬件协同

前言 在分布式推理中,多设备(如GPU、CPU)之间的数据传输(通信)是连接计算的“桥梁”。如果通信效率低下,即使单设备计算能力再强,整体性能也会大打折扣。想象一下:如果工厂之间的物流卡车跑得比生产速度还慢,再多的工厂也无法提高整体产量。 本节将从最基础的单设备内…

XGBoost 的适用场景以及与 CNN、LSTM 的区别

XGBoost 的核心优势与适用场景XGBoost 是一种梯度提升决策树算法&#xff0c;属于集成学习方法。它在处理结构化/表格化数据方面表现极其出色&#xff0c;是 Kaggle 竞赛和工业界广泛应用的“冠军”模型。其核心优势和应用场景包括&#xff1a;1. 结构化/表格化数据数据形式&a…

快速设计简单嵌入式操作系统(3):动手实操,基于STC8编写单任务执行程序,感悟MCU指令的执行过程

引言 前面我们陆续学习了操作系统常见的基础概念&#xff0c;接着简单了解了一下8051单片机的内存结构和执行顺序切换的相关概念。接下来&#xff0c;我们就开始进行实操&#xff0c;基于8051单片机STC8来编写一个简单的操作系统&#xff0c;这里我们先实现一个单任务的执行程…

Spring AI Alibaba - 聊天机器人快速上手

本节对应 Github&#xff1a;https://github.com/JCodeNest/JCodeNest-AI-Alibaba/tree/master/spring-ai-alibaba-helloworld 本文将以阿里巴巴的通义大模型为例&#xff0c;通过 Spring AI Alibaba 组件&#xff0c;手把手带你完成从零到一的构建过程&#xff1a;首先&#…

串口通信学习

不需要校验位就选8位&#xff0c;需要校验位就选9位&#xff01;USRTUSART框图STM32的外设引脚这是USART的基本结构。数据帧&#xff0c;八位是这个公式还是很重要的&#xff01;如果在编辑器里面使用printf打印汉字的话&#xff0c;会出现乱码的话&#xff0c;前提是你的编码格…

面试经典150题[001]:合并两个有序数组(LeetCode 88)

合并两个有序数组&#xff08;LeetCode 88&#xff09; https://leetcode.cn/problems/merge-sorted-array/?envTypestudy-plan-v2&envIdtop-interview-150 1. 题目背景 你有两个已经排好序的数组&#xff1a; nums1&#xff1a;前面是有效数字&#xff0c;后面是空位&…

快速安装达梦8测试库

计划&#xff1a;数据库名实例名PORT_NUMMAL_INST_DW_PORTMAL_HOSTMAL_PORTMAL_DW_PORTDMDWDBINST_1533615101192.168.207.612510135101*****[2025-08-11 15:14:34]***** Last login: Fri Jul 25 17:36:04 2025 from 192.168.88.48 [rootdm01 ~]# ip a 1: lo: <LOOPBACK,UP,…

Hive中优化问题

一、小文件合并优化Hive中的小文件分为Map端的小文件和Reduce端的小文件。(1)、Map端的小文件优化是通过CombineHiveInputFormat操作。相关的参数是&#xff1a;set hive.input.formatorg.apache.hadoop.hive.ql.io.CombineHiveInputFormat;(2)、Reduce端的小文件合并Map端的小…

tlias智能学习辅助系统--Maven高级-继承

目录 一、打包方式与应用场景 二、父子工程继承关系 1. 父工程配置 2. 子工程配置 三、自定义属性与引用属性 1. 定义属性 2. 在 dependencyManagement 中引用 3. 子工程中引用 四、dependencyManagement 与 dependencies 的区别 五、项目结构示例 六、小结 在实际开…

把 AI 押进“小黑屋”——基于 LLM 的隐私对话沙盒设计与落地

标签&#xff1a;隐私计算、可信执行环境、LLM、沙盒、内存加密、TEE、SGX、Gramine ---- 1. 背景&#xff1a;甲方爸爸一句话&#xff0c;“数据不能出机房” 我们给某三甲医院做智能问诊助手&#xff0c;模型 70 B、知识库 300 GB。 甲方只给了两条铁律&#xff1a; 1. 患者…

Java 大视界 -- Java 大数据在智能教育学习效果评估指标体系构建与精准评估中的应用(394)

Java 大视界 -- Java 大数据在智能教育学习效果评估指标体系构建与精准评估中的应用&#xff08;394&#xff09;引言&#xff1a;正文&#xff1a;一、传统学习评估的 “数字陷阱”&#xff1a;看不全、说不清、跟不上1.1 评估维度的 “单行道”1.1.1 分数掩盖的 “学习真相”…

Dubbo 3.x源码(33)—Dubbo Consumer接收服务调用响应

基于Dubbo 3.1&#xff0c;详细介绍了Dubbo Consumer接收服务调用响应 此前我们学习了Dubbo Provider处理服务调用请求的流程&#xff0c;现在我们来学习Dubbo Consumer接收服务调用响应流程。 实际上接收请求和接收响应同属于接收消息&#xff0c;它们的流程的很多步骤是一样…

栈和队列:数据结构中的基础与应用​

栈和队列&#xff1a;数据结构中的基础与应用在计算机科学的领域中&#xff0c;数据结构犹如大厦的基石&#xff0c;支撑着各类复杂软件系统的构建。而栈和队列作为两种基础且重要的数据结构&#xff0c;以其独特的特性和广泛的应用&#xff0c;在程序设计的舞台上扮演着不可或…

服务端配置 CORS解决跨域问题的原理

服务端配置 CORS&#xff08;跨域资源共享&#xff09;的原理本质是 浏览器与服务器之间的安全协商机制。其核心在于服务器通过特定的 HTTP 响应头声明允许哪些外部源&#xff08;Origin&#xff09;访问资源&#xff0c;浏览器根据这些响应头决定是否放行跨域请求。以下是详细…

Unity笔记(五)知识补充——场景切换、退出游戏、鼠标隐藏锁定、随机数、委托

写在前面&#xff1a;写本系列(自用)的目的是回顾已经学过的知识、记录新学习的知识或是记录心得理解&#xff0c;方便自己以后快速复习&#xff0c;减少遗忘。主要是C#代码部分。十七、场景切换和退出游戏1、场景切换场景切换使用方法&#xff1a; SceneManager.LoadScene()&a…