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…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
LeetCode - 148. 排序链表
目录 题目 思路 基本情况检查 复杂度分析 执行示例 读者可能出的错误 正确的写法 题目 148. 排序链表 - 力扣(LeetCode) 思路 链表归并排序采用"分治"的策略,主要分为三个步骤: 分割:将链表从中间…...
