【排列回溯】Leetcode 46. 全排列 47. 全排列 II

【排列回溯】Leetcode 46. 全排列 47. 全排列 II

  • 46 全排列——used数组上下层保证不取重复的即可
  • 47. 全排列 II——used去重上下层,再去重本层重复元素

46 全排列——used数组上下层保证不取重复的即可

---------------🎈🎈题目链接🎈🎈-------------------
在这里插入图片描述
在这里插入图片描述

used数组,其实就是记录此时temp 里都有哪些元素使用了,这样就保证每一层都可以取剩下的,即一个排列里一个元素只能使用一次。
排列都是从0开始遍历for循环,跳过used中为1 的元素即可。
组合都是从startindex开始遍历for循环,保证不重复

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int[] used = new int[nums.length];
        helper(nums,used);
        return result;
    }
    public void helper(int[] nums, int[] used){
        // 当temp的长度等于nums的长度的时候就可以收获一个结果啦
        if(temp.size() == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(used[i] == 1){ // 如果当前的这个元素已经被前层使用过了,那么used中对应位置会置为1,本层就不使用了
                continue;
            }
            temp.add(nums[i]);
            used[i] = 1;
            helper(nums,used);
            temp.removeLast();
            used[i] = 0;
        }
    }
}             

47. 全排列 II——used去重上下层,再去重本层重复元素

---------------🎈🎈题目链接🎈🎈-------------------
在这里插入图片描述

在这里插入图片描述

这道题目和46.全排列 (opens new window)的区别在与:
给定一个可包含重复数字的序列,要返回所有不重复的全排列。

去重需要先排序!
对于前后层(可以选取相等的元素):使用used数组,如果前层使用了元素,used[i]就置为1。递归到下一层的时候如果used[i] == 1,那么就跳过
对于同一层(不选取相等的元素):当i > 0且 前后两个元素相等:nums[i] == nums[i-1],如果此时的used[i-1] = 0,代表当前元素nums[i] 的前一个元素目前未被使用,说明同层有重复的元素nums[i] 和nums[i-1],所以跳过!⭐️

 if(i>0 && nums[i] == nums[i-1] && used[i-1]==0||  used[i] == 1){
               continue;
  }
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        helper(nums,used);
        return result;
    }
    public void helper(int[] nums, int[] used){
        //temp中长度和nums相同,那么就收货结果
        if(temp.size() == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }

        for(int i = 0; i < nums.length; i++){
        //如果同层中遇到两个相等 且 当前的这个元素已经被前层使用过了 那么就跳过
            if(i>0 && nums[i] == nums[i-1] && used[i-1]==0||  used[i] == 1){
                continue;
            }

            temp.add(nums[i]);
            used[i] = 1;
            helper(nums,used);
            used[i] = 0;
            temp.removeLast();
            
        }
    }
}      

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024年面试AI编译器岗经验总结

面试经历: 面试中必备的知识: 1.用C++实现一个卷积 (图解)一步一步使用CPP实现深度学习中的卷积 - GiantPandaCVGiantPandaCVhttp://giantpandacv.com/academic/%E7%AE%97%E6%B3%95%E7%A7%91%E6%99%AE/%E5%B0%BD%E8%A7%88%E5%8D%B7%E7%A7%AF%E7%A5%9E%E7%BB%8F%E7%BD%91%E…

Springboot引入swagger

讲在前面&#xff1a;在spring引入swagger时&#xff0c;由于使用的JDK、Spring、swagger 的版本不匹配&#xff0c;导致启动报错&#xff0c;一直存在版本依赖问题。所以在此声明清楚使用版本。JDK 1.8、Spring boot 2.6.13、 Swagger 2.9.2。 引入maven依赖 <dependency&…

Mysql【索引覆盖、索引下推、索引合并、索引跳跃】介绍

索引覆盖、索引下推、索引合并、索引跳跃都是Mysql对索引的优化手段&#xff0c;它们的思想就是尽量让查询数据走索引&#xff0c;那它们有什么区别呢&#xff1f; 一、首先介绍一下MySQL体系结构 上图来自MySQL官方文档。 通常把MySQL从上至下分为以下几层&#xff1a; MySQ…

备考ICA----Istio实验18---单集群中部署多个Istio控制面

备考ICA----Istio实验18—单集群中部署多个Istio控制面 单个 Kubernetes 控制面以及多个 Istio 控制面和多个网格。通过 Kubernetes 命名空间和 RBAC 实现软多租户业务隔离。 1. 环境准备 1.1 创建2个命名空间 kubectl create ns usergroup-1 kubectl label ns usergroup-…

外包干了6天,技术明显进步

先说一下自己的情况&#xff0c;本科生&#xff0c;2019年我通过校招踏入了南京一家软件公司&#xff0c;开始了我的职业生涯。那时的我&#xff0c;满怀热血和憧憬&#xff0c;期待着在这个行业中闯出一片天地。然而&#xff0c;随着时间的推移&#xff0c;我发现自己逐渐陷入…

探索Kubernetes的大二层网络:原理、优势与挑战

在云原生领域&#xff0c;Kubernetes (K8s) 已经成为容器编排的事实标准☁️&#x1f4e6;。为了支撑其灵活的服务发现和负载均衡&#x1f50d;&#x1f504;&#xff0c;K8s采用了大二层网络的设计理念&#x1f578;️。本文将深入探讨大二层网络的工作原理、带来的好处✨&…

在线JSON工具

功能支持 ctrls json格式化游览器本地保存ctrla ctrlc 自动检测选中范围是否是全选&#xff0c;然后按照格式化方式添加到粘贴板中json 粘贴JSON自动格式化json可视化修改json压缩复制json层级折叠json关键key 搜索(自动提示高亮)满足某些近视的可以自行调整字体大小, 并且会游…

敦煌网、速卖通、国际站铺需要自养号补单来稳定出单率吗?

亚马逊、速卖通、Lazada、shoppe、速卖通、敦煌网、Temu、shein、美客多、阿里国际、卖家如何保证店铺出单稳定?在竞争激烈的平台上&#xff0c;保持店铺的稳定出单是每个卖家都追求的目标。为了实现这一目标&#xff0c;卖家需要综合考虑产品、运营、客户服务等多个方面的因素…

推动科技创新润德生物邀您到场参观2024第13届生物发酵展

参展企业介绍 山东润德生物科技有限公司成立于2014年10月17日&#xff0c;是一家围绕生物制品的研发、生产、营销、国际贸易、技术服务为核心业务的国家高新技术企业&#xff0c;近年来荣获国家制造业单项冠军示范企业、国家级绿色工厂、国家知识产权优势企业、国家工业产品绿…

Nacos Namespace 未授权访问漏洞

Nacos Namespace 未授权访问漏洞 问题 nacos 源码启动&#xff0c;发现即使开启了鉴权&#xff1a;nacos.core.auth.enabledtrue&#xff0c;未登录情况下&#xff0c;命名空间列表接口仍旧能查询到数据 鉴权逻辑 通过**AuthFilter **进行权限校验判断方法上是否存在注解 …

电脑硬件 - 硬盘

硬盘是一台电脑的数据中心&#xff0c;存放着我们用户的所有文件和数据 对于一块硬盘&#xff0c;其重要指标&#xff1a;顺序读写能力&#xff0c;随机读写能力 顺序读写影响大文件的拷贝&#xff0c;随机读写影响大量小文件的拷贝&#xff08;打开软件的快慢&#xff09; 因…

Chatgpt掘金之旅—有爱AI商业实战篇|内容策展业务|(八)

演示站点&#xff1a; https://ai.uaai.cn 对话模块 官方论坛&#xff1a; www.jingyuai.com 京娱AI 一、AI技术创业内容策展业务有哪些机会&#xff1f; 人工智能&#xff08;AI&#xff09;技术作为当今科技创新的前沿领域&#xff0c;为创业者提供了广阔的机会和挑战。随着…

蓝色系UX/UI设计求职面试作品集模版figmasketchPPT可编辑源文件

页面数量: 20P 页面尺寸:1920*1080PX 交付格式&#xff1a;figma、sketch、PPT 赠送文件&#xff1a;24款高质量样机&#xff08;PSD格式&#xff09; 该作品集虽然只有20页&#xff0c;但可根据需求复制作品集里已有的页面作为模版来扩展您的设计项目 该作品集模版可编辑可修…

蓝桥杯嵌入式备考笔记

这里写目录标题 keil配置LED-KEY-LCDledkeyLCD最多21位 RTCPWM捕获占空比ADCI2C按键长按uartPWMDAC双击高亮EEp初始化LED闪烁时间倒计时 keil配置 LED-KEY-LCD 留下这几个 按键 创建俩个文件写代码&#xff0c;记得把这两个文件加进工程 led uwTick 1ms执行一次 写错…

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…

C语言语法最后一个教案-教案21(预处理 · 头文件)

最近给大家争取到一个 深夜福利 保证你在深夜手机刷到 嘎嘎香~ 那就是 官方授权 大流量卡 缺点&#xff1a;月租太便宜 185GB~ 100分钟通话时长~ 长期套餐~ 畅想自由的气息 流量自由的同时还拥有超长通话&#xff0c;而且免费领取。 名额有限&#xff0c;咱们废话不…

Golang | Leetcode Golang题解之第14题最长公共前缀

题目&#xff1a; 题解&#xff1a; func longestCommonPrefix(strs []string) string {if len(strs) 0 {return ""}isCommonPrefix : func(length int) bool {str0, count : strs[0][:length], len(strs)for i : 1; i < count; i {if strs[i][:length] ! str0 …

LiveGBS流媒体平台GB/T28181常见问题-系统服务日志如何配置日志个数日志路径日志时长web操作日志操如何配置保留天数及过滤

LiveGBS系统服务日志如何配置日志个数日志路径日志时长web操作日志操如何配置保留天数及过滤 1、系统服务日志1.1、日志目录1.2、配置日志文件个数及记录时间1.3、配置日志文件路径 2、Web 操作日志2.1、配置保留天数2.2、配置不记录操作日志2.1.1、不记录所有2.1.2、不记录指定…

项目设计方案:市交通视频监控平台项目设计方案(四)

目录 1 前言 1.1 目的 1.2 适用范围 1.3 术语表 2 现状分析 2.1 业务现状 2.2 组织机构现状 2.3 存在的问题 2.4 项目成果预期 3 系统建设原则 4 项目需求 4.1 项目需求 4.1.1 业务需求主要分为三部分&#xff1a; 4.1.2 技术需求主要分为四部分&#xff1a; 4.…

yolov5旋转目标检测遥感图像检测-无人机旋转目标检测(代码和原理)

YOLOv5&#xff08;You Only Look Once version 5&#xff09;是一个流行且高效的实时目标检测深度学习模型&#xff0c;最初设计用于处理图像中的水平矩形边界框目标。然而&#xff0c;对于旋转目标检测&#xff0c;通常需要对原始YOLOv5架构进行扩展或修改&#xff0c;以便能…