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

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 1‘ 2,也就是选择完1之后再选择第二个1,两个元素虽然重复,但是第二个元素是前一个元素的下一层,这时是没有问题的。
  2. 另一种是之前的 同层 分支已经有 1 1‘ 2了,这次的选择是 1‘ 1 2 。两个元素重复,且重的是同层路径。那就说明是重复分支

具体区分的办法是 nums[i-1] 的used状态是被选择的,那么说明当前的nums[i] 是 nums[i-1]的下一层路径。 否则如果 nums[i-1] 的状态是没被选择的,那么说明当前 的nums[i] 是nums[i-1] 同层路径。
Alt

代码

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),的树形结构如下:
Alt树枝上去重(used[i - 1] == true)的树型结构如下:
Alt

相关文章:

LeetCode-47 全排列Ⅱ

LeetCode-47 全排列Ⅱ 题目描述解题思路代码说明 题目描述 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 &#xff1a; 输入&#xff1a;nums [1,1,2]输出&#xff1a; [[1,1,2], [1,2,1], [2,1,1]] b站题目解读讲的不好&…...

list 的实现

目录 list 结点类 结点类的构造函数 list的尾插尾删 list的头插头删 迭代器 运算符重载 --运算符重载 和! 运算符重载 * 和 -> 运算符重载 list 的insert list的erase list list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要…...

一个程序员的牢狱生涯(47)学法

星期一 学法 二铺不知道什么时候走到了我的身边,向我说道,这是二铺在我进来号子后主动过来和我说话。 我听到二铺这声突兀的说话后,抬起头。这时我才看到,除了二铺,还有六子、棍子都围在我的身边,看着我。虽然六子和棍子依旧一副‘吊儿郎当’的样子,但我从他们几个的眼神…...

微信小程序-页面导航

一、页面导航 页面导航指的是页面之间的相互跳转&#xff0c;例如&#xff1a;浏览器中实现页面导航的方式有如下两种&#xff1a; 1.<a>链接 2.location.href 二、小程序中实现页面导航的两种方式 1.声明式导航 在页面上声明一个<navigator>导航组件 通过点击…...

计算机网络- 特定服务类型(Type of Service, TOS) 服务质量(Quality of Service, QoS)

特定服务类型&#xff08;Type of Service, TOS&#xff09; 具有特定服务类型&#xff08;Type of Service, TOS&#xff09;的数据包是指在IP头部中包含特定TOS字段设置的数据包。TOS字段用于指示数据包的服务质量要求&#xff0c;如延迟、吞吐量、可靠性等。现代IP网络通常…...

2.6 Docker部署多个前端项目

2.6 Docker部署多个项目 三. 部署前端项目 1.将前端项目打包到同一目录下&#xff08;tcm-ui&#xff09; 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盘只读无法格式化&#xff0c;该怎么处理&#xff1f;别担心&#xff01;本文将向你提供一些实用方法&#xff0c;助你解决U盘写保护的难题。这些方法能有效帮助你解除U盘的只读状态&#xff0c;从而可以顺利进行格式化和其他操作。 不能格式化只读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…...

服装连锁店收银系统需要具备的五大功能

当今服装连锁店在市场竞争中需要拥有高效的收银系统来提升业务效率和顾客满意度。以下是服装连锁店收银系统需要具备的五大功能&#xff1a; 首先&#xff0c;完善的商品管理功能是至关重要的。这包括商品信息的录入、管理、更新和查询。收银系统应该能够快速而准确地识别商品&…...

IMU状态预积分代码实现 —— IMU状态预积分类

IMU状态预积分代码实现 —— IMU状态预积分类 实现IMU状态预积分类 实现IMU状态预积分类 首先&#xff0c;实现预积分自身的结构。一个预积分类应该存储一下数据&#xff1a; 预积分的观测量 △ R ~ i j , △ v ~ i j , △ p ~ i j \bigtriangleup \tilde{R} _{ij},\bigtrian…...

C语言编程:探索最小公倍数的奥秘

C语言编程&#xff1a;探索最小公倍数的奥秘 在编程的世界中&#xff0c;计算两个数的最小公倍数&#xff08;LCM&#xff09;是一个常见的数学问题。C语言作为一种基础且强大的编程语言&#xff0c;为我们提供了实现这一功能的工具。本文将从四个方面、五个方面、六个方面和七…...

Java设计模式-活动对象与访问者

活动对象 Java设计模式中&#xff0c;活动对象是指一个对象始终处于活动的状态&#xff0c;该对象包括一个线程安全的数据结构以及一个活跃的执行线程。 如上所示&#xff0c;ActiveCreature类的构造函数初始化一个线程安全的数据结构&#xff08;阻塞队列&#xff09;、初始化…...

用HAL库改写江科大的stm32入门-6-3 PWM驱动LED呼吸灯

接线图&#xff1a; 2 :实验目的&#xff1a; 利用pwm实现呼吸灯。 关键PWM定时器设置&#xff1a; 代码部分&#xff1a; int main(void) {/* USER CODE BEGIN 1 *//* USER CODE END 1 *//* MCU Configuration--------------------------------------------------------*…...

[数据集][目标检测]喝水检测数据集VOC+YOLO格式995张3类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;995 标注数量(xml文件个数)&#xff1a;995 标注数量(txt文件个数)&#xff1a;995 标注类别…...

【C++】开源:RabbitMQ安装与配置使用(SimpleAmqpClient)

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下次更新不迷路&#x1…...

git使用流程与规范

原文网址&#xff1a;git代码提交流程与规范-CSDN博客 简介 本文git提交流程与规范是宝贵靠谱的经验&#xff0c;它能解决如下问题&#xff1a; 分支差距过大&#xff0c;导致合代码无数的冲突合完代码后发现代码丢失分支不清晰&#xff0c;无法追溯问题合代码耗时很长&…...

力扣 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的模拟实现其实就是增删改查&#xff0c;只不过加入了类的概念。 为了防止与std里面的string冲突&#xff0c;所以这里统一用String。 目录 前言 一 初始化和销毁 1.1 构造函数 1.2 析构函数 二 迭代器实现 三 容量大小及操作 四 运算符重载 4.1 bool…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...