java数据结构与算法刷题-----LeetCode47. 全排列 II

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

    • 1. 暴力回溯
    • 2. 分区法+回溯

在这里插入图片描述

此题为46题的衍生题,在46题的基础上,加上了是否重复的判断,除此之外完全一样。

🏆LeetCode46. 全排列https://blog.csdn.net/grd_java/article/details/136683863

1. 暴力回溯

解题思路:时间复杂度O( n n n^n nn),但是严格来说只到了O( n ∗ n ! n*n! nn!)。空间复杂度O(n)
  1. 在46题的基础上增加一些判断是否重复的操作
  2. 首先我们先将数组排序,这样我们就能通过两个相邻值的比较,确定当前值是否是一个重复的值(不止一个它)
  3. 我们进行全排列时,每个位置可以选择任何不同的值,但是现在有重复的值,就必须确保同一个位置,重复的值只选一次
  4. 所以进行全排列时,通过比较相邻的值就可以判断了。但是必须是有序数组才行(重复数字会都挨在一起)
代码

在这里插入图片描述

int[] nums;boolean[] numsFlag;//flag数组,true表示当前这个值已经选过int len;List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);this.nums = nums;this.len = nums.length;this.numsFlag = new boolean[len];ArrayList<Integer> records = new ArrayList<>();backTracking(records);return ans;}//回溯算法public void backTracking(List<Integer> records){if(records.size() == len) ans.add(new ArrayList<>(records));//全排列完成后,保存答案else{for(int i = 0;i<len;i++){//每个位置都可以选任何值,但是如果当前数字已被选过,则必须跳过这个值//如果当前值已被选,跳过! 或者 当前值和上一个一样 并且 上一个也没有被选(说明上一个就已经不能选,选了会重复了)if(this.numsFlag[i]==true || (i>0 && nums[i] == nums[i-1] && this.numsFlag[i-1] == false) ) continue;this.numsFlag[i] = true;//标志为被选过records.add(nums[i]);//选择这个数字backTracking(records);//进行下一个数字的枚举this.numsFlag[i] = false;//枚举完成后,放弃这个值records.remove(records.size()-1);//尝试当前位置下一个可能的值}}}

2. 分区法+回溯

解题思路:时间复杂度O( n ∗ n ! ∗ l o g 2 n n*n!*log_2{n} nn!log2n),其中 l o g 2 n log_2{n} log2n是判断是否重复的时间开销。空间复杂度O(n)
  1. 含有重复的元素序列,进行全排列,这个方法就不太好用,因为处理重复很麻烦
  2. 所以这里只能通过笨办法,每次选择数字判断是否重复时,从当前位置可选值中,依次遍历判断我们当前要选的数字是否之前就存在过
  3. 这个算法依然不需要flag数组标志数字是否已经选择过,也不需要事先排序。
  4. 与46题代码几乎完全照搬,只单纯加了一个循环遍历数组,判断是否重复的方法而已。
代码

在这里插入图片描述

class Solution {int[] nums;int len;List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> permuteUnique(int[] nums) {this.nums = nums;this.len = nums.length;dfs(0);return ans;}private void dfs(int idx) {if (idx == len) {List<Integer> result = new ArrayList<>();for (int num: nums) result.add(num);ans.add(result);}for (int i = idx; i < len; i++) {if (isRepeat(nums, idx, i)) continue;//与46题唯一的不同swap(nums, idx, i);dfs( idx + 1);swap(nums, idx, i);}}//log_2{n},判断当前位置i的取值,是否是重复的(之前取过的值)//与46题唯一的不同private boolean isRepeat(int[] nums, int idx, int i) {while (idx < i) if (nums[idx++] == nums[i]) return true;return false;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

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

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

相关文章

QTextToSpeech的使用——Qt

前言 之前随便看了几眼QTextToSpeech的帮助就封装使用了&#xff0c;达到了效果就没再管了&#xff0c;最近需要在上面加功能&#xff08;变换语速&#xff09;&#xff0c;就写了个小Demo后&#xff0c;发现不对劲了。 出现的问题 场景 写了个队列添加到语音播放子线程中&a…

一条 SQL 更新语句如何执行的

Server 层 存储引擎层 总流程 查询语句 连接器 查询缓存 分析器 优化器 执行器 更新语句 redo log&#xff08;节省的是随机写磁盘的 IO 消耗&#xff08;转成顺序写&#x…

Qt+FFmpeg+opengl从零制作视频播放器-3.解封装

解封装&#xff1a;如下图所示&#xff0c;就是将FLV、MKV、MP4等文件解封装为视频H.264或H.265压缩数据&#xff0c;音频MP3或AAC的压缩数据&#xff0c;下图为常用的基本操作。 ffmpeg使用解封装的基本流程如下&#xff1a; 在使用FFmpeg API之前&#xff0c;需要先注册API&a…

精简版 Obsidian 图床配置 PicGo+ gitee

精简版 Obsidian 图床配置 PicGo gitee 图床的作用 图床&#xff08;Image Hosting Service&#xff09;是一种在线服务&#xff0c;用于存储和托管用户上传的图片文件。用户可以将图片上传到图床服务器&#xff0c;并获得一个可访问的图片链接&#xff0c;然后可以在网页、博…

为什么要用scrapy爬虫库?而不是纯python进行爬虫?

为什么要用scrapy爬虫库&#xff1f;而不是纯python进行爬虫&#xff1f; Scrapy的优点Scrapy节省的工作使用纯Python编写爬虫的不足 Scrapy是一个使用Python编写的开源和协作的web爬虫框架&#xff0c;它被设计用于爬取网页数据并从中提取结构化数据。Scrapy的强大之处在于其广…

mysql 主从延迟分析

一、如何分析主从延迟 分析主从延迟一般会采集以下三类信息。 从库服务器的负载情况 为什么要首先查看服务器的负载情况呢&#xff1f;因为软件层面的所有操作都需要系统资源来支撑。 常见的系统资源有四类&#xff1a;CPU、内存、IO、网络。对于主从延迟&#xff0c;一般会…

加密货币在网络违法犯罪活动中的利用情况调查

一、调查背景 区块链基于分布式共识和经济激励等手段&#xff0c;在开放式、无许可的网络空间中&#xff0c;为价值的确立、存储、转移提供了新的解决方案。然而随着加密生态在过去若干年的快速发展&#xff0c;加密货币也越来越多地被用于各类风险活动&#xff0c;为网络赌博…

ES6(一):let和const、模板字符串、函数默认值、剩余参数、扩展运算符、箭头函数

一、let和const声明变量 1.let没有变量提升&#xff0c;把let放下面打印不出来&#xff0c;放上面可以 <script>console.log(a);let a1;</script> 2.let是一个块级作用域,花括号里面声明的变量外面找不到 <script>console.log(b);if(true){let b1;}//und…

el-table的border属性失效问题解决方案

目录 问题&#xff1a; 使用的代码&#xff1a; 官方文档的说明&#xff1a; 可能的问题所在&#xff1a; 关于使用了作用域插槽&#xff1a; a.自定义内容的样式覆盖&#xff1a; b.表格结构的改变&#xff1a; 解决方案&#xff1a; 通过css样式解决&#xff1a; 下面…

聚酰亚胺PI材料难于粘接,用什么胶水粘接?那么让我们先一步步的从认识它开始(一)

聚酰亚胺PI的基本概念 聚酰亚胺&#xff08;Polyimide&#xff0c;简称PI&#xff09;是一种重要的高性能聚合物材料。是指主链上含有酰亚胺环的一类聚合物&#xff0c;是综合性能最佳的有机高分子材料之一。它具有最高的阻燃等级&#xff08;UL-94&#xff09;&#xff0c;以及…

Editor.md-编辑器

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…

学生时期学习资源同步-1 第一学期结业考试题8

原创作者&#xff1a;田超凡&#xff08;程序员田宝宝&#xff09; 版权所有&#xff0c;引用请注明原作者&#xff0c;严禁复制转载

云服务器2核4G配置,阿里云和腾讯云哪个便宜?性能更好?

租用2核4G服务器费用多少&#xff1f;2核4G云服务器多少钱一年&#xff1f;1个月费用多少&#xff1f;阿里云2核4G服务器30元3个月、轻量应用服务器2核4G4M带宽165元一年、企业用户2核4G5M带宽199元一年&#xff1b;腾讯云轻量2核4G服务器5M带宽165元一年、252元15个月、540元三…

搭建谷歌Gemini

前言 Gemini是Google AI于2023年发布的大型语言模型&#xff0c;拥有强大的文本生成、理解和转换能力。它基于Transformer模型架构&#xff0c;并使用了大量文本和代码数据进行训练。Gemini可以执行多种任务&#xff0c;包括&#xff1a; 生成文本&#xff1a;可以生成各种类…

Qt/QML编程之路:基于QWidget编程及各种2D/3D/PIC绘制的示例(45)

关于使用GWidget,这里有一个示例,看了之后很多图形绘制,控件使用,及最基本的QWidget编程都比较清楚了。ui的绘制: 运行后的界面如 工程中有非常丰富的关于各种图形的绘制,比如上图中circle,还有image。有下面一段readme的说明: # EasyQPainter Various operation pra…

css超出部分显示省略号

目录 前言 一、CSS单行实现 二、CSS多行实现&#xff08;CSS3出的&#xff0c;兼容性需要注意&#xff09; 三、微信小程序超过2行出现省略号实现 四、JavaScript脚本实现 前言 CSS文本溢出就显示省略号&#xff0c;就是在样式中指定了盒子的宽度与高度,有可能出现某些内…

“antd“: Unknown word.cSpell

你遇到的问题是 VS Code 的 Code Spell Checker 插件在检查拼写时&#xff0c;将 "antd" 标记为未知单词。"antd" 是 Ant Design 的缩写&#xff0c;是一个流行的 React UI 库&#xff0c;不是一个英语单词&#xff0c;所以 Spell Checker 会将其标记为错误…

Linux的一些常用指令

一、文件中 r w x - 的含义 r&#xff08;read&#xff09;是只读权限&#xff0c; w&#xff08;write&#xff09;是写的权限&#xff0c; x&#xff08;execute&#xff09;是可执行权限&#xff0c; -是没有任何权限。 二、一些指令 # 解压压缩包 tar [-zxvf] 压缩包名…

Selenium 学习(0.20)——软件测试之单元测试

我又&#xff08;浪完&#xff09;回来了…… 很久没有学习了&#xff0c;今天忙完终于想起来学习了。没有学习的这段时间&#xff0c;主要是请了两个事假&#xff08;5工作日和10工作日&#xff09;放了个年假&#xff08;13天&#xff09;&#xff0c;然后就到现在了。 看了下…

hadoop报错:HADOOP_HOME and hadoop.home.dir are unset. 解决方法

参考&#xff1a;https://blog.csdn.net/weixin_45735242/article/details/120579387 解决方法 1.下载apache-hadoop-3.1.0-winutils-master 官网下载地址&#xff1a; https://github.com/s911415/apache-hadoop-3.1.0-winutils win配置系统环境&#xff1a; 然后重启idea…