代码随想录算法训练营第29天|491.递增子序列 * * 46.全排列 * 47.全排列 II

文章目录

  • 491.递增子序列
    • 思路:
      • 代码
    • 思路:优化
      • 代码:
  • 46.全排列
    • 思路
      • 代码一:使用used数组
      • 代码二:使用path判断元素
  • 47.全排列 II
    • 思路一:层节点和路径都是用used数组做记录
    • 思路二:层通过排序后是否重复过滤

491.递增子序列

在这里插入图片描述

思路:

在这里插入图片描述
在这里插入图片描述

代码

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path=new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums,0);return res;}public void backtracking(int[] nums,int startIndex){// if(startIndex>=nums.length-1)return;if(path.size()>1){res.add(new ArrayList<>(path));}int[] used = new int[201];for(int i=startIndex;i<nums.length;i++){if(!path.isEmpty()&&path.getLast()> nums[i]|| (used[nums[i]+100]==1)){continue;}used[nums[i]+100]=1;path.add(nums[i]);backtracking(nums,i+1);path.removeLast();}}
}

思路:优化

通过数组去重,取代hashset
在这里插入图片描述

代码:

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums,0);return res;}public void backtracking(int[] nums,int startIndex){// if(startIndex>=nums.length-1)return;if(path.size()>1){res.add(new ArrayList<>(path));}int[] used = new int[201];for(int i=startIndex;i<nums.length;i++){if(!path.isEmpty()&&path.get(path.size() -1 ) > nums[i]|| (used[nums[i]+100]!=0)){continue;}used[nums[i]+100]=1;path.add(nums[i]);backtracking(nums,i+1);path.remove(path.size() -1);}}
}

46.全排列

在这里插入图片描述

思路

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码一:使用used数组

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used=new boolean[nums.length];backtracking(nums,used);return res;}public void backtracking(int[] nums,boolean[] used){if(path.size()==nums.length){res.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){// System.out.println("数值"+nums[i]+"布尔值"+used[nums[i]+10]);if(used[i]){continue;}path.add(nums[i]);used[i]=true;backtracking(nums,used);used[i]=false;path.remove(path.size()-1);}}
}

代码二:使用path判断元素

path是linkedlist

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {// boolean[] used=new boolean[nums.length];backtracking(nums);return res;}public void backtracking(int[] nums){if(path.size()==nums.length){res.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){// System.out.println("数值"+nums[i]+"布尔值"+used[nums[i]+10]);if(path.contains(nums[i])){continue;}path.add(nums[i]);backtracking(nums);path.removeLast();}}
}

47.全排列 II

在这里插入图片描述

思路一:层节点和路径都是用used数组做记录

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used=new boolean[nums.length];backtracking(nums,used);return res;}public void backtracking(int[] nums,boolean[] used){if(path.size()==nums.length){res.add(new ArrayList<>(path));return;}int[] cengused=new int[21];for(int i=0;i<nums.length;i++){// System.out.println("数值"+nums[i]+"布尔值"+used[nums[i]+10]);if(used[i]||cengused[nums[i]+10]==1){continue;}path.add(nums[i]);cengused[nums[i]+10]=1;used[i]=true;backtracking(nums,used);used[i]=false;path.remove(path.size()-1);}}
}

思路二:层通过排序后是否重复过滤

在这里插入图片描述

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++) {// used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}//如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] == false) {used[i] = true;//标记同⼀树⽀nums[i]使⽤过,防止同一树枝重复使用path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);//回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复used[i] = false;//回溯}}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【第二届 Runway短视频创作大赛】——截至日期2024年03月01日

短视频创作大赛 关于AI Fil&#xff4d; Festival竞赛概况参加资格报名期间报名方法 提交要求奖品附录 关于AI Fil&#xff4d; Festival 2022年成立的AIFF是一个融合了最新AI技术于电影制作中的艺术和艺术家节日&#xff0c;让我们得以一窥新创意时代的风采。从众多参赛作品中…

C语言笔试题之实现C库函数 strstr()(设置标志位)

实例要求&#xff1a; 1、请你实现C库函数strstr()&#xff08;stdio.h & string.h&#xff09;&#xff0c;请在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;&#xff1b;2、函数声明&#xff1a;int strStr(char* h…

MATLAB知识点:易错点:判断浮点数是否相等

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第3章 3.4.3 关系运算 下面我们再来看一个易错点&…

flask+pyinstaller实现mock接口,并打包到exe运行使用postman验证

flask代码 from flask import Flask, request, jsonifyapp Flask(__name__)app.route("/login", methods[POST]) def login():username request.json.get("username").strip() # 用户名password request.json.get("password").strip() # 密…

林浩然的趣味解读:赫伯特·亚历山大·西蒙的跨界智慧与伟大成就

林浩然的趣味解读&#xff1a;赫伯特亚历山大西蒙的跨界智慧与伟大成就 Lin Haoran’s Amusing Interpretation: Herbert Alexander Simon’s Interdisciplinary Wisdom and Great Achievements 林浩然&#xff0c;这位机智幽默且对知识充满好奇的探索者&#xff0c;最近在一次…

代码随想录算法训练营第二十四天 |回溯算法基础知识,77.组合(已补充)

回溯算法理论基础&#xff08;已观看&#xff09; 带你学透回溯算法&#xff08;理论篇&#xff09;| 回溯法精讲&#xff01;_哔哩哔哩_bilibili #题目分类 什么是回溯法 溯法也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 在二叉树系列中&#xff0c;我们已经不…

2022年通信工程师初级 实务 真题

文章目录 三、第3章 接入网&#xff0c;接入网的功能结构&#xff0c;无线频段及技术四、第4章 互联网&#xff0c;网络操作系统的功能&#xff0c;IP地址五、第6章 移动通信系统&#xff0c;FDD、TDD 三、第3章 接入网&#xff0c;接入网的功能结构&#xff0c;无线频段及技术…

numa网卡绑定

#概念 参考&#xff1a;https://www.jianshu.com/p/0f3b39a125eb(opens new window) chip&#xff1a;芯片&#xff0c;一个cpu芯片上可以包含多个cpu core&#xff0c;比如四核&#xff0c;表示一个chip里4个core。 socket&#xff1a;芯片插槽&#xff0c;颗&#xff0c;跟…

【Spring Boot】第二篇 自动装配原来就这么简单

导航 一. 什么是自动装配?二. 如何实现自动装配?1. 配置清单在哪里?2. 自动装配实现核心点1: 从META‐INF/spring.factories路径读取配置类清单核心点2: 过滤第一次过滤: 根据EnableAutoConfiguration注解中exclude和excludeName属性第二次过滤: 通过AutoConfigurationImpor…

Java实现网上药店系统 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 药品类型模块2.3 药品档案模块2.4 药品订单模块2.5 药品收藏模块2.6 药品资讯模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 角色表3.2.2 药品表3.2.3 药品订单表3.2.4 药品收藏表3.2.5 药品留言表…

【集合系列】LinkedHashMap 集合

LinkedHashMap集合 1. 概述2. 方法3. 遍历方式4. 代码示例5. 注意事项 其他集合类 祖父类 Map 父类 HashMap 集合类的遍历方式 具体信息请查看 API 帮助文档 1. 概述 LinkedHashMap 是 Java 中的一种特殊类型的 HashMap&#xff0c;它继承自 HashMap 类&#xff0c;并实现了…

免费:阿里云学生服务器领取申请(2024新版教程)

2024年阿里云学生服务器免费领取&#xff0c;先完成学生认证即可免费领取一台云服务器ECS&#xff0c;配置为2核2G、1M带宽、40G系统盘&#xff0c;在云服务器ECS实例过期之前&#xff0c;完成实验与认证任务&#xff0c;还可以免费续费6个月&#xff0c;阿里云百科aliyunbaike…

2023爱分析·大模型厂商全景报告|爱分析报告

01 研究范围定义 研究范围 大模型是指通过在海量数据上依托强大算力资源进行训练后能完成大量不同下游任务的模型。2023年以来&#xff0c;ChatGPT引爆全球大模型市场。国内众多大模型先后公测&#xff0c;众多互联网领军者投身大模型事业&#xff0c;使得大模型市场进入“百团…

Redis篇之过期淘汰策略

一、数据的过期策略 1.什么是过期策略 Redis对数据设置数据的有效时间&#xff0c;数据过期以后&#xff0c;就需要将数据从内存中删除掉。可以按照不同的规则进行删除&#xff0c;这种删除规则就被称之为数据的删除策略&#xff08;数据过期策略&#xff09;。 2.过期策略-惰…

【C语言自定义类型详解进阶】结构体(补充结构体的对齐和位段,一口气看完系列,央妈都点赞的博文)

目录 1.结构体 1.1 结构的基础知识 1.2 结构的声明 1.2.1特殊的声明&#xff08;匿名结构体类型&#xff09; 1.3结构体变量的定义 1.4关于匿名结构体类型的补充 1.5结构体的自引用 1.6结构体变量的初始化 2.结构体内存对齐&#xff08;重点&#xff09; 2.1偏移量补…

Redis篇之缓存雪崩

一、什么的缓存雪崩 缓存雪崩&#xff1a;在同一时间段大量的缓存key同时失效或者redis服务宕机&#xff0c;导致大量请求到达数据库给数据库带来巨大压力&#xff0c;可能导致数据库崩了。 二、应该怎么解决 1.给不同的Key的TTL添加随机值 2.利用Redis集群提高服务的可用性 3…

【人工智能】人工智能 – 引领未来科技的潮流

写在前面 引言红利挑战结论 引言 人工智能是指使计算机系统表现出类似于人类智能的能力。其目标是实现机器具备感知、理解、学习、推理和决策等智能行为。人工智能的发展可以追溯到上世纪50年代&#xff0c;随着计算机技术和算法的不断进步&#xff0c;人工智能得以实现。 今天…

QML中常见热区及层级结构

目录 引言层级结构默认层级结构z值作用范围遮罩实现-1的作用 热区嵌套与普通元素与其他热区与Flickable 事件透传总结 引言 热区有很多种&#xff0c;诸如MouseArea、DropArea、PinchArea等等&#xff0c;基本都是拦截对应的事件&#xff0c;允许开发者在事件函数对事件进行响…

米贸搜|Facebook在购物季使用的Meta广告投放流程

一、账户简化 当广告系列开始投放后&#xff0c;每个广告组都会经历一个初始的“机器学习阶段”。简化账户架构可以帮助AI系统更快获得广告主所需的成效。例如&#xff1a; 每周转化次数超过50次的广告组&#xff0c;其单次购物费用要低28%&#xff1b;成功结束机器学习阶段的…

图像处理入门:OpenCV的基础用法解析

图像处理入门&#xff1a;OpenCV的基础用法解析 引言OpenCV的初步了解深入理解OpenCV&#xff1a;计算机视觉的开源解决方案什么是OpenCV&#xff1f;OpenCV的主要功能1. 图像处理2. 图像分析3. 结构分析和形状描述4. 动态分析5. 三维重建6. 机器学习7. 目标检测 OpenCV的应用场…