当前位置: 首页 > 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…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...