代码随想录算法训练营第二十九天(回溯5)|491. 非递减子序列、46. 全排列、47. 全排列 II(JAVA)

文章目录

  • 491. 非递减子序列
    • 解题思路
    • 源码
  • 46. 全排列
    • 解题思路
    • 源码
  • 47. 全排列 II
    • 解题思路
    • 源码
  • 总结


491. 非递减子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

示例 1:

  • 输入:nums = [4,6,7,7]
  • 输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2:

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

提示:

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

解题思路

跟之前的子集II很像,但是不能用它的去重逻辑,本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。
在这里插入图片描述

源码

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    private void backTracking(int[] nums, int startIndex){
        if(path.size() >= 2)
                result.add(new ArrayList<>(path));            
        HashSet<Integer> hs = new HashSet<>();
        for(int i = startIndex; i < nums.length; i++){
            if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))
                continue;
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

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

示例 2:

  • 输入:nums = [0,1]
  • 输出:[[0,1],[1,0]]

示例 3:

  • 输入:nums = [1]
  • 输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

解题思路

典型的排列问题,回溯搜索代替for来暴力实现
在这里插入图片描述

源码

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

47. 全排列 II

给定一个可包含重复数字的序列 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

解题思路

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

这里又涉及到去重了。

在40.组合总和II 、90.子集II 我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素进行排序,这样我们才方便通过相邻的节点来判断是否重复使用了。
在这里插入图片描述

源码

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}

总结

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

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

相关文章

探索未来游戏:生成式人工智能AI如何重塑你的游戏世界?

生成式人工智能&#xff08;Generative AI&#xff09;正以前所未有的速度改变着各行各业的运作模式。其中&#xff0c;游戏产业作为科技应用的前沿阵地&#xff0c;正经历着前所未有的变革。本文将探讨生成式人工智能如何重塑游戏产业&#xff0c;以及这一变革背后的深远影响。…

博士推荐 | 拥有超过10年的数据解决方案经验,数据驱动的决策者

编辑 / 木子 审核 / 朝阳 伟骅英才 伟骅英才致力于以大数据、区块链、AI人工智能等前沿技术打造开放的人力资本生态&#xff0c;用科技解决职业领域问题&#xff0c;提升行业数字化服务水平&#xff0c;提供创新型的产业与人才一体化服务的人力资源解决方案和示范平台&#x…

评估精益管理培训的有效性需要收集哪些数据?

近年来&#xff0c;企业纷纷寻求通过精益管理培训来提升效率和竞争力。然而&#xff0c;精益管理培训是否真正有效&#xff0c;能否为企业带来实实在在的改变&#xff0c;这是许多管理者和决策者关心的问题。为了回答这个问题&#xff0c;我们需要收集一系列关键数据来评估精益…

基于 OpenHarmony PrecentPositionLayout 开发指南

1. PrecentPositionLayout 功能介绍 1.1. 组件介绍&#xff1a; 鸿蒙 SDK 提供了不同布局规范的组件容器&#xff0c;例如以单一方向排列的 DirectionalLayout、以相对位置排列的DependentLayout、以确切位置排列的 PositionLayout 等。 但是 PositionLayout 中组件的位置是…

基于单片机收音机调幅系统设计仿真源码

**单片机设计介绍&#xff0c;基于单片机收音机调幅系统设计仿真源码 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机收音机调幅系统设计的仿真源码&#xff0c;主要实现了通过单片机控制调幅收音机的核心功能。以下是…

C++ | Leetcode C++题解之第16题最接近的三数之和

题目&#xff1a; 题解&#xff1a; class Solution { public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int n nums.size();int best 1e7;// 根据差值的绝对值来更新答案auto update [&](int cur) {if (abs(cur…

城市郊野公园“风筝节”视频智能识别技术安全监管方案

一、方案背景 四月天气十分舒适&#xff0c;微风拂面&#xff0c;这段时间也是游客前往户外放风筝的好时机&#xff0c;很多城市都举办了“风筝节”等活动&#xff0c;尤其是在周末节假日期间&#xff0c;城市各个郊野公园的游客量逐渐暴增。然而&#xff0c;随着参与人数的增…

C++ 十进制转十六进制

文章目录 toHexString(int n) 函数&#xff0c;输入整型数字n&#xff0c;返回 字符串string类。 #include <iostream> #include <string> #include <vector> #include <math.h> using namespace std;string toHexString(int n) {vector <int> …

CICD流水线 发布应用到docker镜像仓库

准备工作 1.先注册免费的镜像仓库 复制链接: https://cr.console.aliyun.com/cn-beijing/instances 实施 1. 新建流水线&#xff0c;选择模板 2.添加流水线源&#xff0c;及是你的代码仓库, 选择对应分支. 3.代码检查以及单元测试&#xff0c;这个步骤可以不用动它. 4. …

Java学习笔记23(面向对象三大特征)

1.5 多态 ​ *多态(polymorphic) ​ *方法或对象具有多种形态&#xff0c;是面向对象的第三大特征&#xff0c;多态是建立在封装和继承基础之上的 1.多态的具体体现 1.方法的多态 &#xff08;重写和重载体现了多态&#xff09; 2.对象的多态 ​ 1.一个对象的编译类型和…

如何魔改 diffusers 中的 pipelines

如何魔改 diffusers 中的 pipelines 整个 Stable Diffusion 及其 pipeline 长得就很适合 hack 的样子。不管是通过简单地调整采样过程中的一些参数&#xff0c;还是直接魔改 pipeline 内部甚至 UNet 内部的 Attention&#xff0c;都可以实现很多有趣的功能或采样生图结果。 本…

如何编写一份完整的软件测试报告

软件测试是软件开发过程中一个非常重要的环节&#xff0c;它有助于确保软件的质量和稳定性。编写一份完整的软件测试报告是软件测试工作的重要组成部分&#xff0c;它不仅可以帮助测试团队记录测试结果和发现的问题&#xff0c;还可以为开发团队提供有价值的反馈和改进建议。下…

我独自升级崛起下载慢/下载不了/无法下载的解决方法

我独自升级是一款RGP游戏&#xff0c;以充满独特的画风以及新的类型的挑战得到玩家们的喜爱。通过打怪、完成任务、参加活动等方式获得经验值&#xff0c;合理分配技能点数和属性点数&#xff0c;以适应不同阶段的挑战需求。掌握装备掉落、合成、升级机制&#xff0c;及时更换更…

ubuntu安装nginx以及开启文件服务器

1. 下载源码 下载页面&#xff1a;https://nginx.org/en/download.html 下载地址&#xff1a;https://nginx.org/download/nginx-1.24.0.tar.gz curl -O https://nginx.org/download/nginx-1.24.0.tar.gz2. 依赖配置 sudo apt install gcc make libpcre3-dev zlib1g-dev ope…

中药提取物备案数据库<5000+中药提取物>

NMPA中药提取物备案数据库的建立是确保中药提取物质量安全、规范生产行为、加强监管、保障公众用药安全、促进产业发展和国际化的重要措施。 通过查询中药提取物备案信息我们能了解到中药提取物的实用备案号、药品通用名称、药品生产企业、批准文号、备案日期、备案状态、中药…

Mysql启动报错:本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止

Mysql启动报错&#xff1a;本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止 文章目录 Mysql启动报错&#xff1a;本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止1. 备份mysql的data文件夹2. 重新构建 Wind…

智能照明控制系统的节能优势及其应用

【摘要】&#xff1a;通过智能照明控制系统与传统照明控制的对比&#xff0c;阐明智能照明控制系统的优势&#xff0c;基本组成、在智能建筑中的应用效果以及其实施存在的问题和前景展望。 安科瑞薛瑶瑶18701709087 【关键字】&#xff1a;智能照明控制&#xff1b;系统组成&…

【御控物联】 JavaScript JSON结构转换(21):数组To对象——综合应用

文章目录 一、JSON结构转换是什么&#xff1f;二、术语解释三、案例之《JSON数组 To JSON对象》四、代码实现五、在线转换工具六、技术资料 一、JSON结构转换是什么&#xff1f; JSON结构转换指的是将一个JSON对象或JSON数组按照一定规则进行重组、筛选、映射或转换&#xff0…

医院智慧手术麻醉系统管理源码 C# .net有演示

医院智慧手术麻醉系统管理源码 C# .net有演示 手术麻醉管理系统(DORIS)是应用于医院手术室、麻醉科室的计算机软件系统。该系统针对整个围术期&#xff0c;对病人进行全程跟踪与信息管理&#xff0c;自动集成病人HIS、LIS、RIS、PACS信息&#xff0c;采集监护等设备数据&#x…

【THM】Protocols and Servers 2(协议和服务器 2

介绍 协议和服务器房间涵盖了许多协议: 远程登录HTTP协议文件传输协议邮件传输协议POP3IMAP实现这些协议的服务器会受到不同类型的攻击。仅举几例,请考虑: 嗅探攻击(网络数据包捕获)中间人 ( MITM ) 攻击密码攻击(身份验证攻击)漏洞从安全的角度来看,我们始终需要思考…