【Leetcode每日一题】 综合练习 - 全排列 II(难度⭐⭐)(71)

1. 题目解析

题目链接:47. 全排列 II

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

2.算法原理

算法思路梳理

为了生成给定数组nums的全排列,同时避免由于重复元素导致的重复排列,我们可以遵循以下步骤和策略:

  1. 预处理与排序
    • 由于题目不要求返回排列的顺序,我们可以首先对nums进行排序,使得所有相同的元素相邻。这样方便后续操作,因为我们可以根据元素的顺序来避免产生重复的全排列。
  2. 定义递归函数
    • 设计一个递归函数backtrack(vector<int>& nums, int idx),其中idx表示当前需要填充的位置。该函数用于搜索并存储所有合理的排列。
  3. 初始化数据结构
    • 使用一个二维数组ans来存储所有可能的排列。
    • 使用一个一维数组perm来保存当前状态下的排列。
    • 使用一个一维数组visited来标记元素是否已经被选择用于当前排列。
  4. 递归过程
    • 递归终止条件:当idx等于nums的长度时,说明已经处理完所有数字,此时将perm数组加入ans
    • 递归状态转移:对于每个下标i,如果nums[i]未被标记(即visited[i]为0),并且如果它之前的相同元素(如果存在)已被标记,则执行以下步骤:
      • 标记visited[i]为1,表示nums[i]已被选择用于当前排列。
      • nums[i]添加到perm数组的末尾。
      • 递归调用backtrack函数,处理下一个位置(即idx+1)。
      • 递归返回后,进行回溯操作:将visited[i]重新设为0,并从perm数组中移除nums[i]
  5. 注意事项
    • 在选择元素时,必须确保相同元素按照它们在排序后数组中的顺序出现在排列中。这样可以确保不会产生重复的全排列。
    • 如果当前元素之前的相同元素未被选择(即未被标记),则当前元素也不能被选择,这同样是为了避免重复排列。
  6. 返回结果
    • 递归完成后,ans数组将包含所有不重复的全排列。

算法实现细节

  • 在递归函数中,需要仔细处理边界条件和状态转移的逻辑,确保每次递归调用都符合题目要求。
  • 使用visited数组可以有效地避免重复选择相同的元素,尤其是在处理含有重复元素的数组时。
  • 回溯操作是深度优先搜索中的重要步骤,它允许我们撤销之前的选择,并尝试其他可能性。

3.代码编写

class Solution {vector<int> path;vector<vector<int>> ret;bool cheak[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){//剪枝是重点,if判断!!!if(cheak[i] == true || (i != 0 && nums[i] == nums[i - 1]) && cheak[i - 1] == false){continue;}path.push_back(nums[i]);cheak[i] = true;dfs(nums, pos + 1);path.pop_back();cheak[i] = false;}}
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~

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

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

相关文章

快速上手RabbitMQ

安装RabbitMQ 首先将镜像包上传到虚拟机&#xff0c;使用命令加载镜像 docker load -i mq.tar 运行MQ容器 docker run \-e RABBITMQ_DEFAULT_USERitcast \-e RABBITMQ_DEFAULT_PASS123321 \-v mq-plugins:/plugins \--name mq \--hostname mq \-p 15672:15672 \-p 5672:5672 …

如何使用 GPT API 从 PDF 出版物导出研究图表?

原文地址&#xff1a;how-to-use-gpt-api-to-export-a-research-graph-from-pdf-publications 揭示内部结构——提取研究实体和关系 2024 年 2 月 6 日 介绍 研究图是研究对象的结构化表示&#xff0c;它捕获有关实体的信息以及研究人员、组织、出版物、资助和研究数据之间的关…

brpc profiler

cpu profiler cpu profiler | bRPC MacOS的额外配置 在MacOS下&#xff0c;gperftools中的perl pprof脚本无法将函数地址转变成函数名&#xff0c;解决办法是&#xff1a; 安装standalone pprof&#xff0c;并把下载的pprof二进制文件路径写入环境变量GOOGLE_PPROF_BINARY_PA…

Microsoft 365 for Mac(Office 365)v16.84正式激活版

office 365 for mac包括Word、Excel、PowerPoint、Outlook、OneNote、OneDrive和Teams的更新。Office提供了跨应用程序的功能&#xff0c;帮助用户在更短的时间内创建令人惊叹的内容&#xff0c;您可以在这里创作、沟通、协作并完成重要工作。 Microsoft 365 for Mac(Office 36…

1. 深度学习笔记--神经网络中常见的激活函数

1. 介绍 每个激活函数的输入都是一个数字&#xff0c;然后对其进行某种固定的数学操作。激活函数给神经元引入了非线性因素&#xff0c;如果不用激活函数的话&#xff0c;无论神经网络有多少层&#xff0c;输出都是输入的线性组合。激活函数的意义在于它能够引入非线性特性&am…

【webrtc】MessageHandler 7: 基于线程的消息处理:切换main线程向observer发出通知

以当前线程作为main线程 RemoteAudioSource 作为一个handler 仅实现一个退出清理的功能 首先on message的处理会切换到main 线程 :main_thread_其次,这里在main 线程对sink_ 做清理再次,在main 线程做出状态改变,并能通知给所有的observer 做出on changed 行为。对接mediac…

clang:在 Win10 上编译 MIDI 音乐程序(二)

先从 Microsoft C Build Tools - Visual Studio 下载 1.73GB 安装 "Microsoft C Build Tools“ 访问 Swift.org - Download Swift 找到 Windows 10&#xff1a;x86_64 下载 swift-5.10-RELEASE-windows10.exe 大约490MB 建议安装在 D:\Swift\ &#xff0c;安装后大约占…

《金融研究》:普惠金融改革试验区DID工具变量数据(2012-2023年)

数据简介&#xff1a;本数据集包括普惠金融改革试验区和普惠金融服务乡村振兴改革试验区两类。 其中&#xff0c;河南兰考、浙江宁波、福建龙岩和宁德、江西赣州和吉安、陕西铜川五省七地为普惠金融改革试验区。山东临沂、浙江丽水、四川成都三地设立的是普惠金融服务乡村振兴…

手撸Mybatis(二)—— 配置项的获取

本专栏的源码&#xff1a;https://gitee.com/dhi-chen-xiaoyang/yang-mybatis。 配置项解析 在mybatis中&#xff0c;一般我们会定义一个mapper-config.xml文件&#xff0c;来配置数据库连接的相关信息&#xff0c;以及我们的mapperxml文件存放目录。在本章&#xff0c;我们会…

docker-compose启动mysql5.7报错

描述一下问题经过&#xff1a; 使用docker compose 部署mysql5.7 文件如下: 使用命名卷的情况下&#xff0c;匿名卷不存在该问题 services:mysql:restart: alwaysimage: mysql:5.7container_name: mysql-devports:- 3306:3306environment:- MYSQL_DATABASEdev- MYSQL_ROOT_PAS…

团队经理口才训练教案(3篇)

团队经理口才训练教案&#xff08;3篇&#xff09; **篇&#xff1a;基础口才训练 一、教学目标 让团队经理了解口才在团队管理中的重要性。 教授基础口才技巧&#xff0c;如发音、语速、语调等。 二、教学内容 口才的重要性 强调团队经理的口才能力对团队凝聚力、沟通…

详细介绍ARM-ORACLE Database 19c数据库下载

目录 1. 前言 2. 获取方式 2.1 ORACLE专栏 2.2 ORACLE下载站点 1. 前言 现有网络上已有非常多关于ORACLE数据库机下载的介绍&#xff0c;但对于ARM平台的介绍不多&#xff0c;借此机会我将该版的下载步骤做如下说明&#xff0c;希望能够一些不明之人提供帮助和参考 2. 获…

分享一篇关于AGI的短文:苦涩的教训

学习强化学习之父、加拿大计算机科学家理查德萨顿&#xff08; Richard S. Sutton &#xff09;2019年的经典文章《The Bitter Lesson&#xff08;苦涩的教训&#xff09;》。 文章指出&#xff0c;过去70年来AI研究走过的最大弯路&#xff0c;就是过于重视人类既有经验和知识&…

Flutter笔记:美工设计.导出视频到RIVE

Flutter笔记 美工设计.导出视频到RIVE - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28…

目标跟踪—卡尔曼滤波

目标跟踪—卡尔曼滤波 卡尔曼滤波引入 滤波是将信号中特定波段频率滤除的操作&#xff0c;是抑制和防止干扰的一项重要措施。是根据观察某一随机过程的结果&#xff0c;对另一与之有关的随机过程进行估计的概率理论与方法。 历史上最早考虑的是维纳滤波&#xff0c;后来R.E.卡…

原生IP和住宅IP有什么区别?

原生IP和住宅IP在多个方面存在显著的区别。 从定义和来源来看&#xff0c;原生IP是指未经NAT&#xff08;网络地址转换&#xff09;处理的真实、公网可路由的IP地址&#xff0c;它直接从互联网服务提供商&#xff08;ISP&#xff09;获得&#xff0c;而不是通过代理服务器或VP…

【MATLAB】解决不同版本MATLAB出现中文乱码的问题

解决不同版本MATLAB出现中文乱码的问题 方法1&#xff1a;更改保存类型为GBK方法2&#xff1a;记事本打开方法3&#xff1a;Notepad参考 低版本matlab打开高版本Matlab的.m文件时&#xff0c;出现中文乱码问题。比如下图&#xff1a; 出现原因为&#xff1a; 编码格式不统一问…

批量抓取某电影网站的下载链接

思路&#xff1a; 进入电影天堂首页&#xff0c;提取到主页面中的每一个电影的背后的那个urL地址 a. 拿到“2024必看热片”那一块的HTML代码 b. 从刚才拿到的HTML代码中提取到href的值访问子页面&#xff0c;提取到电影的名称以及下载地址 a. 拿到子页面的页面源代码 b. 数据提…

Ansys Speos|进行智能手机镜头杂散光分析

本例的目的是研究智能手机Camera系统的杂散光。杂散光是指光向相机传感器不需要的散光光或镜面光&#xff0c;是在光学设计中无意产生的&#xff0c;会降低相机系统的光学性能。 在本例中&#xff0c;光学透镜系统使用Ansys Zemax OpticStudio (ZOS)进行设计&#xff0c;并使用…

A Bug‘s Life (并查集)

//新生训练 #include <iostream> #include <algorithm> using namespace std; const int N 5000; int p[N], sz[N]; int n, m; int find(int x) {if (p[x] ! x)p[x] find(p[x]);return p[x]; } int main() {int T;scanf("%d", &T);for (int k 1; …