LeetCode-47 全排列Ⅱ
LeetCode-47 全排列Ⅱ
- 题目描述
- 解题思路
- 代码
- 说明
题目描述
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 :
- 输入:nums = [1,1,2]
- 输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
b站题目解读讲的不好,勿喷
解题思路
首先选择对原数组排序,保证相同的数字都相邻,然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」,即如下的判断条件:
if (i > 0 && nums[i] == nums[i - 1] && used[i-1] == false) {continue;
}
即可实现树层的去重。
-
希望在计算的过程中进行去重操作,所以我们对数组
nums排序处理。 -
如果
nums[i] == nums[i-1]就说明该分支有可能是重复的。 但是这个相等条件有两种可能:
- 一种是,1 1‘ 2,也就是选择完1之后再选择第二个1,两个元素虽然重复,但是第二个元素是前一个元素的下一层,这时是没有问题的。
- 另一种是之前的 同层 分支已经有 1 1‘ 2了,这次的选择是 1‘ 1 2 。两个元素重复,且重的是同层路径。那就说明是重复分支。
具体区分的办法是 nums[i-1] 的used状态是被选择的,那么说明当前的nums[i] 是 nums[i-1]的下一层路径。 否则如果 nums[i-1] 的状态是没被选择的,那么说明当前 的nums[i] 是nums[i-1] 同层路径。

代码
class Solution {
public:
// [] 中的数字可以重复,结果集的vector元素不能重复vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);back_tracking(nums, used);return res;}
private:vector<vector<int>> res;vector<int> path;void back_tracking(vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {res.push_back(path);return;} else {for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;if (used[i] == false) {used[i] = true;path.push_back(nums[i]);back_tracking(nums, used);path.pop_back();used[i] = false;}}}}
};
说明
去重最关键的代码就是
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}
而改成used[i-1]==true也正确
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {continue;
}
树层上去重(used[i - 1] == false),的树形结构如下:
树枝上去重(used[i - 1] == true)的树型结构如下:

相关文章:
LeetCode-47 全排列Ⅱ
LeetCode-47 全排列Ⅱ 题目描述解题思路代码说明 题目描述 给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。 示例 : 输入:nums [1,1,2]输出: [[1,1,2], [1,2,1], [2,1,1]] b站题目解读讲的不好&…...
list 的实现
目录 list 结点类 结点类的构造函数 list的尾插尾删 list的头插头删 迭代器 运算符重载 --运算符重载 和! 运算符重载 * 和 -> 运算符重载 list 的insert list的erase list list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要…...
一个程序员的牢狱生涯(47)学法
星期一 学法 二铺不知道什么时候走到了我的身边,向我说道,这是二铺在我进来号子后主动过来和我说话。 我听到二铺这声突兀的说话后,抬起头。这时我才看到,除了二铺,还有六子、棍子都围在我的身边,看着我。虽然六子和棍子依旧一副‘吊儿郎当’的样子,但我从他们几个的眼神…...
微信小程序-页面导航
一、页面导航 页面导航指的是页面之间的相互跳转,例如:浏览器中实现页面导航的方式有如下两种: 1.<a>链接 2.location.href 二、小程序中实现页面导航的两种方式 1.声明式导航 在页面上声明一个<navigator>导航组件 通过点击…...
计算机网络- 特定服务类型(Type of Service, TOS) 服务质量(Quality of Service, QoS)
特定服务类型(Type of Service, TOS) 具有特定服务类型(Type of Service, TOS)的数据包是指在IP头部中包含特定TOS字段设置的数据包。TOS字段用于指示数据包的服务质量要求,如延迟、吞吐量、可靠性等。现代IP网络通常…...
2.6 Docker部署多个前端项目
2.6 Docker部署多个项目 三. 部署前端项目 1.将前端项目打包到同一目录下(tcm-ui) 2. 部署nginx容器 docker run --namenginx -p 9090:9090 -p 9091:9091 -d nginx3. 复制nginx.conf文件到主机目录 docker cp nginx:/etc/nginx/nginx.conf /root/ja…...
如何格式化只读U盘?
U盘只读无法格式化,该怎么处理?别担心!本文将向你提供一些实用方法,助你解决U盘写保护的难题。这些方法能有效帮助你解除U盘的只读状态,从而可以顺利进行格式化和其他操作。 不能格式化只读U盘 “我购买了一个U盘&…...
【并查集】专题练习
题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 模板 836. 合并集合 - AcWing题库 #include<bits/stdc.h> using lllong long; //#define int ll const int N1e510,mod1e97; int n,m; int p[N],sz[N]; int find(int a) {if(p[a]!a) p[a]find(p[a]);return p[a…...
服装连锁店收银系统需要具备的五大功能
当今服装连锁店在市场竞争中需要拥有高效的收银系统来提升业务效率和顾客满意度。以下是服装连锁店收银系统需要具备的五大功能: 首先,完善的商品管理功能是至关重要的。这包括商品信息的录入、管理、更新和查询。收银系统应该能够快速而准确地识别商品&…...
IMU状态预积分代码实现 —— IMU状态预积分类
IMU状态预积分代码实现 —— IMU状态预积分类 实现IMU状态预积分类 实现IMU状态预积分类 首先,实现预积分自身的结构。一个预积分类应该存储一下数据: 预积分的观测量 △ R ~ i j , △ v ~ i j , △ p ~ i j \bigtriangleup \tilde{R} _{ij},\bigtrian…...
C语言编程:探索最小公倍数的奥秘
C语言编程:探索最小公倍数的奥秘 在编程的世界中,计算两个数的最小公倍数(LCM)是一个常见的数学问题。C语言作为一种基础且强大的编程语言,为我们提供了实现这一功能的工具。本文将从四个方面、五个方面、六个方面和七…...
Java设计模式-活动对象与访问者
活动对象 Java设计模式中,活动对象是指一个对象始终处于活动的状态,该对象包括一个线程安全的数据结构以及一个活跃的执行线程。 如上所示,ActiveCreature类的构造函数初始化一个线程安全的数据结构(阻塞队列)、初始化…...
用HAL库改写江科大的stm32入门-6-3 PWM驱动LED呼吸灯
接线图: 2 :实验目的: 利用pwm实现呼吸灯。 关键PWM定时器设置: 代码部分: int main(void) {/* USER CODE BEGIN 1 *//* USER CODE END 1 *//* MCU Configuration--------------------------------------------------------*…...
[数据集][目标检测]喝水检测数据集VOC+YOLO格式995张3类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):995 标注数量(xml文件个数):995 标注数量(txt文件个数):995 标注类别…...
【C++】开源:RabbitMQ安装与配置使用(SimpleAmqpClient)
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍。 无专精则不能成,无涉猎则不能通。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路…...
git使用流程与规范
原文网址:git代码提交流程与规范-CSDN博客 简介 本文git提交流程与规范是宝贵靠谱的经验,它能解决如下问题: 分支差距过大,导致合代码无数的冲突合完代码后发现代码丢失分支不清晰,无法追溯问题合代码耗时很长&…...
力扣 264. 丑数 II python AC
堆 from heapq import heappop, heappushclass Solution:def nthUglyNumber(self, n):q [1]vis {1}for _ in range(n - 1):now heappop(q)for i in [2, 3, 5]:if now * i not in vis:vis.add(now * i)heappush(q, now * i)return heappop(q)...
resetlogs强制拉库失败并使用备份system文件还原数据库故障处理---惜分飞
接手一个库,在open的过程中遭遇到ORA-600 2662错误 Sun May 26 10:15:54 2024 alter database open RESETLOGS RESETLOGS is being done without consistancy checks. This may result in a corrupted database. The database should be recreated. RESETLOGS after incomplete…...
解析Java中1000个常用类:Error类,你学会了吗?
在 Java 编程中,异常处理是一个至关重要的部分。Java 提供了丰富的异常处理机制,包括 Exception 和 Error。 本文将深入探讨 Error 类的功能、用法、实际应用中的注意事项,以及如何处理和预防这些错误。 什么是 Error 类? Error 类是 Java 中 Throwable 类的一个子类,用…...
【C++】——string模拟实现
前言 string的模拟实现其实就是增删改查,只不过加入了类的概念。 为了防止与std里面的string冲突,所以这里统一用String。 目录 前言 一 初始化和销毁 1.1 构造函数 1.2 析构函数 二 迭代器实现 三 容量大小及操作 四 运算符重载 4.1 bool…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
