当前位置: 首页 > news >正文

回溯算法05(leetcode491/46/47)

参考资料:

https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

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]]

思路分析:

代码实现:

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 start){//不用写终止条件,后面for循环自动判断if(path.size()>1){res.add(new ArrayList<>(path));// return;//不用return,因为每个除第一层节点不收集以外,其他节点都收集}HashSet<Integer> hs=new HashSet<>();//每层递归都是新的,——>树层去重for(int i=start;i<nums.length;i++){if(!path.isEmpty() && nums[i]<path.get(path.size()-1) || hs.contains(nums[i])){continue;//此时是同一层递归取数的过程,所以continue,还可以往后选数}hs.add(nums[i]);path.add(nums[i]);backTracking(nums,i+1);path.remove(path.size()-1);//hs不用回溯,因为还在同一层中,要用于树层去重}}
}

 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]]

思路分析:

代码实现:

class Solution {List<List<Integer>> res=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {if(nums.length==0) return res;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++){if(used[i]) continue;used[i]=true;path.add(nums[i]);backTracking(nums);path.removeLast();used[i]=false;}}
}

 47. 全排列 II

题目描述:

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

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

思路分析:

代码实现:

class Solution {List<List<Integer>> res=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {if(nums.length==0) return res;used=new boolean[nums.length];Arrays.sort(nums);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++){if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;//树层去重if(used[i]) continue;used[i]=true;path.add(nums[i]);backTracking(nums);path.removeLast();used[i]=false;}}
}

总结:

1. 根据题目要求看是否需要排序

2.树层去重(同一层递归):

1)可排序,用used[]数组记录 

        i>0 && num[i]==num[i-1] && !used[i]

        要回溯

2) 不可排序,用HashSet记录

        !path.isEmpty() && nums[i]<path.get(path.size()-1) || hs.contains(nums[i])

        不用回溯,因为每层新建

3.元素不重复取(树枝,下一层递归)

  if(used[i]) continue; 

4.continue

本层递归其他数还可往后取  

相关文章:

回溯算法05(leetcode491/46/47)

参考资料&#xff1a; https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 491. 非递减子序列 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素…...

Transformer,革命性的深度学习架构

Transformer 是一种革命性的深度学习架构,专门设计用于处理序列数据,特别是在自然语言处理(NLP)任务中表现卓越。它由 Vaswani 等人在 2017 年发表的论文《Attention is All You Need》中首次提出,打破了当时基于循环神经网络(RNN)和卷积神经网络(CNN)的序列建模常规,…...

实验五:实现循环双链表各种基本运算的算法

实验五&#xff1a;实现循环双链表各种基本运算的算法 一、实验目的与要求 目的:领会循环双链表存储结构和掌握循环双链表中各种基本运算算法设计。 内容:编写一个程序cdinklist.cpp,实现循环双链表的各种基本运算和整体建表算法(假设循环双链表的元素类型ElemType为char),并…...

ElasticSearch IK分词器的安装、词典扩展与停用

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;云原生与服务部署-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 ​编辑 1. 前言 2. IK分词器安装 3. IK分词器词典扩展与停用 4. 总…...

代码随想录训练营总结

为期两个月的代码随想录训练营今天结束了&#xff0c;我想我的收获是非常大的。进到训练营的大群里&#xff0c;令我有种安心的感觉&#xff0c;原来世界各地有这么多与我一起努力的伙伴。更令人安心的是知识星球对于学习进度的规划&#xff0c;细化到每一天每道题&#xff0c;…...

深度学习-转置卷积

转置卷积 转置卷积&#xff08;Transposed Convolution&#xff09;&#xff0c;也被称为反卷积&#xff08;Deconvolution&#xff09;&#xff0c;是深度学习中的一种操作&#xff0c;特别是在卷积神经网络&#xff08;CNN&#xff09;中。它可以将一个低维度的特征图&#x…...

Unity性能优化工具介绍

文章目录 一.Stats组件1.Audio音频的数据组件:2.图形数据 二.Profiler 性能分析器 一.Stats组件 Unity自带Statistics(统计数据),Game视窗中点击Stats打开 1.Audio音频的数据组件: 1):Level 声音强度 单位是分贝(dB) 表示音频听声音的大小,是闪烁波动的. 2):SDPload 数据信…...

Math之向上向下取整

有时我们会遇到向上和向下取整的操作&#xff0c;这时我们可以使用Math类来进行操作。 1、向上取整 Math.ceil() 方法返回大于或等于指定表达式的最小整数&#xff08;即向上取整&#xff09;。如果参数是一个整数&#xff0c;那么结果就是这个整数本身。 示例&#xff1a; …...

MPP架构

MPP架构&#xff0c;即Massively Parallel Processing&#xff08;大规模并行处理&#xff09;架构&#xff0c;是一种用于处理大规模数据的并行计算架构。它通过将数据和计算能力分布在多个处理节点上&#xff0c;利用并行处理技术来加速数据处理和分析的速度。 在MPP架构中&…...

These relative modules were not found:* ../../../constant in

这个错误信息表明&#xff0c;你的项目在尝试加载一个相对路径模块 ../../../constant 时遇到了问题。具体来说&#xff0c;它在 ./node_modules/cache-loader/dist/cj 这个路径下找不到这个模块。 这里有几个可能的原因和相应的解决方案&#xff1a; 路径错误&#xff1a;首…...

2024最新彩虹聚合DNS管理系统源码v1.3 全开源

2024最新彩虹聚合DNS管理系统源码v1.3 全开源 聚合DNS管理系统可以实现在一个网站内管理多个平台的域名解析&#xff0c;目前已支持的域名平台有&#xff1a;阿里云、腾讯云、华为云、西部数码、DNSLA、CloudFlare。 本系统支持多用户&#xff0c;每个用户可分配不同的域名解…...

在Go语言中如何实现变参函数和函数选项模式

在Go语言编程中,我们经常会遇到需要给函数传递可选参数的情况。传统的做法是定义一个结构体,将所有可选参数作为结构体字段,然后在调用函数时创建该结构体的实例并传递。这种方式虽然可行,但是当可选参数较多时,创建结构体实例的代码就会变得冗长และ不太直观。 Go语言的一个…...

Spring Boot中的 6 种API请求参数读取方式

使用Spring Boot开发API的时候&#xff0c;读取请求参数是服务端编码中最基本的一项操作&#xff0c;Spring Boot中也提供了多种机制来满足不同的API设计要求。 接下来&#xff0c;就通过本文&#xff0c;为大家总结6种常用的请求参数读取方式。如果你发现自己知道的不到6种&a…...

Linux基础命令[27]-gpasswd

文章目录 1. gpasswd 命令说明2. gpasswd 命令语法3. gpasswd 命令示例3.1 不加参数3.2 -a&#xff08;将用户加入组&#xff09;3.3 -d&#xff08;从组中删除用户&#xff09;3.4 -r&#xff08;删除组密码&#xff09;3.5 -M&#xff08;多个用户一起加入组&#xff09;3.6 …...

机会约束转化为确定性约束-- 样本均值法

当涉及到新能源消纳的机会约束规划时&#xff0c;我们需要深入理解其背后的原理和采用的方法。以下是对上文内容的更详细且更贴切的展开解释&#xff1a; 机会约束转化为确定性约束-- 样本均值法代码获取戳此处代码获取戳此处代码获取戳此处 新能源消纳的机会约束 新能源&…...

uniapp中,当页面显示时触发子组件的重新渲染

使用watch监听数据变化&#xff1a; 在子组件中使用watch来监听父组件传递的数据&#xff0c;一旦数据发生变化&#xff0c;子组件就会重新渲染。 子组件代码示例&#xff1a; <template><div>{{ message }}</div> </template><script> export d…...

先进制造aps专题五 aps软件的排程算法和优化算法介绍

aps软件的核心&#xff0c;主要是数据管理&#xff0c;排程/优化算法&#xff0c;各类甘特图 所有aps软件排程算法都是Heuristics启发式算法&#xff08;如Greedy算法&#xff09;&#xff0c;只是有的aps软件还支持ga遗传算法优化&#xff08;比如sap apo,oracle aps,isuperap…...

【跳坑日记】暴力解决Ubuntu SSH报错: Failed to start OpenBSD Secure Shell server

报错环境说明&#xff1a; 服务器环境&#xff1a;Ubuntu 20.04 错误内容 最近服务器突然报错&#xff0c;提示如下图信息&#xff1a; 搜素了各种问答&#xff0c;国内的回答大多数是用 ssh-keygen -A命令来解决&#xff0c;但最终也无法登录服务器。 最终搜索到ask ubun…...

从需求角度介绍PasteSpider(K8S平替部署工具适合于任何开发语言)

你是否被K8S的强大而吸引&#xff0c;我相信一部分人是被那复杂的配置和各种专业知识而劝退&#xff0c;应该还有一部分人是因为K8S太吃资源而放手&#xff01; 这里介绍一款平替工具PasteSpider&#xff0c;PasteSpider是一款使用c#编写的linux容器部署工具(使用PasteSpider和…...

线性三角化

点的线性三角化 输入一堆的点 [ R w c , t w c , p u c ] [R_{wc},t_{wc},p_{uc}] [Rwc​,twc​,puc​]转化成空间的一系列射线 [ P w i , t w i ] , P w i t w c , t w i R w c p u c [P_{wi},t_{wi}],P_{wi}t_{wc},t_{wi}R_{wc}\times p_{uc} [Pwi​,twi​],Pwi​twc​…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...