剑指 Offer II 084. 含有重复元素集合的全排列


comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20084.%20%E5%90%AB%E6%9C%89%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0%E9%9B%86%E5%90%88%E7%9A%84%E5%85%A8%E6%8E%92%E5%88%97/README.md

剑指 Offer II 084. 含有重复元素集合的全排列

题目描述

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

 

示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],[1,2,1],[2,1,1]]

示例 2:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

提示:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

 

注意:本题与主站 47 题相同: https://leetcode.cn/problems/permutations-ii/

解法

方法一

Python3
class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:nums.sort()n=len(nums)res=[]path=[]used=[0]*ndef dfs(i):if len(path)==n:res.append(path[:])returnif len(path)>n:returnfor j in range(n):if used[j]:continue #纵向避免重复选择(这题只能通过位置标记)#j and not used[j-1]很巧妙(既实现了同层剪枝,也避免了对异层【递归方向】的影响【可以选同值异位元素】):起始位置之后的重复元素需要被跳过,而不同层(比如下一层递归)中的同值异位元素是可以使用的 # (j and not used[j-1]) 类似  重复元素组合问题中的j>i,只不过排列可以选到之前的元素if (j and not used[j-1]) and nums[j]==nums[j-1]:continue path.append(nums[j])used[j]=1dfs(j+1)path.pop()used[j]=0dfs(0)return res
Java
class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();int n = nums.length;boolean[] used = new boolean[n];Arrays.sort(nums);dfs(0, n, nums, used, path, res);return res;}private void dfs(int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {if (u == n) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < n; ++i) {if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {continue;}path.add(nums[i]);used[i] = true;dfs(u + 1, n, nums, used, path, res);used[i] = false;path.remove(path.size() - 1);}}
}
C++
class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {int n = nums.size();vector<vector<int>> res;vector<int> path(n, 0);vector<bool> used(n, false);sort(nums.begin(), nums.end());dfs(0, n, nums, used, path, res);return res;}void dfs(int u, int n, vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {if (u == n) {res.emplace_back(path);return;}for (int i = 0; i < n; ++i) {if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;path[u] = nums[i];used[i] = true;dfs(u + 1, n, nums, used, path, res);used[i] = false;}}
};
Go
func permuteUnique(nums []int) [][]int {n := len(nums)res := make([][]int, 0)path := make([]int, n)used := make([]bool, n)sort.Ints(nums)dfs(0, n, nums, used, path, &res)return res
}func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {if u == n {t := make([]int, n)copy(t, path)*res = append(*res, t)return}for i := 0; i < n; i++ {if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {continue}path[u] = nums[i]used[i] = truedfs(u+1, n, nums, used, path, res)used[i] = false}
}
C#
using System.Collections.Generic;
using System.Linq;public class Solution {public IList<IList<int>> PermuteUnique(int[] nums) {var results = new List<IList<int>>();var temp = new List<int>();var count = nums.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());Search(count, temp, results);return results;}private void Search(Dictionary<int, int> count, IList<int> temp, IList<IList<int>> results){if (!count.Any() && temp.Any()){results.Add(new List<int>(temp));return;}var keys = count.Keys.ToList();foreach (var key in keys){temp.Add(key);--count[key];if (count[key] == 0) count.Remove(key);Search(count, temp, results);temp.RemoveAt(temp.Count - 1);if (count.ContainsKey(key)){++count[key];}else{count[key] = 1;}}}
}
Swift
class Solution {func permuteUnique(_ nums: [Int]) -> [[Int]] {var res = [[Int]]()var path = [Int]()var used = [Bool](repeating: false, count: nums.count)let sortedNums = nums.sorted()dfs(0, sortedNums.count, sortedNums, &used, &path, &res)return res}private func dfs(_ u: Int, _ n: Int, _ nums: [Int], _ used: inout [Bool], _ path: inout [Int], _ res: inout [[Int]]) {if u == n {res.append(path)return}for i in 0..<n {if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {continue}path.append(nums[i])used[i] = truedfs(u + 1, n, nums, &used, &path, &res)used[i] = falsepath.removeLast()}}
}

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

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

相关文章

CentOS 7 64 安装 Docker

前言 在虚拟机中安装 Docker 是一种常见的测试和开发环境搭建方式。通过在虚拟机上安装 Docker&#xff0c;可以方便地创建和管理容器化应用&#xff0c;同时避免对宿主机系统造成影响。以下是在 CentOS 7 虚拟机中安装 Docker 的详细步骤。 1. 更新系统&#xff08;可以不操作…

SPI驱动(八) -- SPI_DAC设备驱动程序

文章目录 参考资料&#xff1a;一、编写设备树二、 编写驱动程序三、编写测试APP四、Makefile五、上机实验 参考资料&#xff1a; 参考资料&#xff1a; 内核头文件&#xff1a;include\linux\spi\spi.h内核文档&#xff1a;Documentation\spi\spidevDAC芯片手册&#xff1a;…

Ansible 自动化运维

Ansible架构: 一.部署主机清单 前期环境准备: 管理端: 192.168.60.128 被管理端: client1:192.168.60.129 client2:192.168.60.131 1.所有被管理端配置ssh密钥 (1.免密登陆 2.允许root远程登陆) 脚本如下: #!/bin/bash# 检查 sshpass 是否已安装 if ! command -v ss…

Qt 实现波浪填充的圆形进度显示

话不多说&#xff0c;先上效果图 代码示例&#xff1a; #include <QApplication> #include <QWidget> #include <QPainter> #include <QPropertyAnimation> #include <QTimer> #include <cmath>class WaveProgressBar : public QWidget {…

DQN 玩 2048 实战|第一期!搭建游戏环境(附 PyGame 可视化源码)

视频讲解&#xff1a; DQN 玩 2048 实战&#xff5c;第一期&#xff01;搭建游戏环境&#xff08;附 PyGame 可视化源码&#xff09; 代码仓库&#xff1a;GitHub - LitchiCheng/DRL-learning: 深度强化学习 2048游戏介绍&#xff0c;引用维基百科 《2048》在44的网格上进行。…

星越L_外后视镜使用讲解

目录 1.外后视镜调节 2后视镜折叠 3.后视镜加热 1.外后视镜调节 L控制左边后视镜调节,上下拨动调整视野,一般此镜左右21分,上下55开。 R控制左边后视镜调节,上下拨动调整视野,一般此镜左右13分,上下55开。 2后视镜折叠 车辆解锁自动展开 车辆关闭自动折叠 严寒天气…

2025-03-15 Python深度学习2——Numpy库

文章目录 1 基础1.1 数据类型1.1.1 整型数组与浮点型数组1.1.2 元素同化1.1.3 数组类型转换 1.2 数组维度1.2.1 一维数组与二维数组1.2.2 数组形状变换 2 创建数组2.1 创建指定数组2.2 创建递增数组2.3 创建同值数组2.4 创建随机数组 3 索引3.1 访问数组元素3.1.1 访问向量3.1.…

【Linux-传输层协议TCP】流量控制+滑动窗口+拥塞控制+延迟应答+捎带应答+面向字节流+粘包问题+TCP异常情况+TCP小结

5.流量控制 接收端处理数据的速度是有限的。如果发送端发的太快&#xff0c;导致接收端的缓冲区被打满&#xff0c;这个时候如果发送端继续发送就会造成丢包&#xff0c;继而引起丢包重传等等一系列连锁反应。 因此TCP 支持根据接收端的接收数据的能力来决定发送端发送数据的…

[C语言日寄] qsort函数的练习

【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋&#xff1a;这是一个专注于C语言刷题的专栏&#xff0c;精选题目&#xff0c;搭配详细题解、拓展算法。从基础语法到复杂算法&#xff0c;题目涉及的知识点全面覆盖&#xff0c;助力你系统提升。无论你是初学者&#xff0c;还是…

C语言每日一练——day_8

引言 针对初学者&#xff0c;每日练习几个题&#xff0c;快速上手C语言。第八天。&#xff08;连续更新中&#xff09; 采用在线OJ的形式 什么是在线OJ&#xff1f; 在线判题系统&#xff08;英语&#xff1a;Online Judge&#xff0c;缩写OJ&#xff09;是一种在编程竞赛中用…

python从邮件中提取链接中的符号为什么会变成amp; 解决办法

在Python中&#xff0c;从邮件中提取链接时&#xff0c;&符号变成&amp;是因为HTML实体编码。HTML使用&amp;表示&&#xff0c;以确保在浏览器中正确显示。 原因 HTML实体编码&#xff1a;&在HTML中有特殊含义&#xff0c;用于表示实体编码的开始。为了避免…

农业电商|基于SprinBoot+vue的农业电商服务系统(源码+数据库+文档)

农业电商服务系统 目录 基于SprinBootvue的农业电商服务系统 一、前言 二、系统设计 三、系统功能设计 5.1系统功能实现 5.2后台模块实现 5.2.1管理员模块实现 5.2.2商家模块实现 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码…

【JAVA】七、基础知识“if+switch+循环结构”详细讲解~简单易懂!

目录 7、逻辑控制 7.1 分支结构 7.1.1 if 语句 语法格式1 语法格式2 语法格式3 7.1.2 switch语句 基本语法 执行流程 7.2 循环结构 7.2.1 while循环 语法格式 7.2.2 Break 7.2.3 Continue 7.2.4 for循环 语法格式 执行过程 7.2.5 do while循环 语法格式 7.3 …

C# Exe + Web 自动化 (BitComet 绿灯 自动化配置、设置)

BitComet GreenLight,内网黄灯转绿灯 (HighID), 增加p2p连接率提速下载-CSDN博客 前两天写个这个&#xff0c;每次开机关机后要重来一遍很麻烦的索性写个自动化。 先还是按照上面的教程自己制作一遍&#xff0c;留下Luck 以及 路由器相关的 端口记录信息。 &#xff08;因为自…

JumpServer基础功能介绍演示

堡垒机可以让运维人员通过统一的平台对设备进行维护&#xff0c;集中的进行权限的管理&#xff0c;同时也会对每个操作进行记录&#xff0c;方便后期的溯源和审查&#xff0c;JumpServer是由飞致云推出的开源堡垒机&#xff0c;通过简单的安装配置即可投入使用&#xff0c;本文…

sqldef:一款免费的数据库变更管理工具

应用程序的升级通常伴随着数据库表结构的变更&#xff0c;为了维护各种环境的数据库变更&#xff0c;我们通常需要引入 Liquibase 或者 Flyaway 这样的数据库版本控制工具。不过&#xff0c;这类工具通常需要绑定某种编程语言&#xff0c;例如 Java&#xff1b;这次我们介绍一个…

行为模式---状态模式

概念 状态模式是一种行为模式&#xff0c;用于在内部状态改变的时候改变其行为。它的核心思想就是允许一个对象在其内部状态改变的时候改变它的行为。状态模式通过将对象的状态封装成独立的类&#xff0c;并将其行为委托给当前的状态对象&#xff0c;从而使得对象行为随着状态…

1688按图搜索商品(拍立淘)接口的参数说明【附代码实例】

阿里巴巴中国站按图搜索1688商品&#xff08;拍立淘&#xff09; API 返回值说明 item_search_img-按图搜索1688商品&#xff08;拍立淘&#xff09; 1688.item_search_img 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;se…

Linux文件管理练习

1、列出所有账号的账号名 切割显示-cut 作用&#xff1a;cut命令用于按列提取文本内容 格式: cut -d "分隔符" -f列数字 文件名 2、将/etc/passwd中内容按照冒号隔开的第三个字符从大到小排序后输出所有内容 排序显示-sort 作用:sort命令用于对文本内容进行排…

解决PC串流至IPad Pro时由于分辨率不一致导致的黑边问题和鼠标滚轮反转问题

问题背景 今天在做 电脑串流ipad pro 的时候发现了2个问题&#xff1a; 1.ipadpro 接上鼠标后&#xff0c;滚轮上下反转&#xff0c;这个是苹果自己的模拟造成的问题&#xff0c;在设置里选择“触控板与鼠标”。 关闭“自然滚动”,就可以让鼠标滚轮正向滚动。 2. ipadpro 分…