回溯算法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)
参考资料: https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 491. 非递减子序列 题目描述: 给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素…...
Transformer,革命性的深度学习架构
Transformer 是一种革命性的深度学习架构,专门设计用于处理序列数据,特别是在自然语言处理(NLP)任务中表现卓越。它由 Vaswani 等人在 2017 年发表的论文《Attention is All You Need》中首次提出,打破了当时基于循环神经网络(RNN)和卷积神经网络(CNN)的序列建模常规,…...
实验五:实现循环双链表各种基本运算的算法
实验五:实现循环双链表各种基本运算的算法 一、实验目的与要求 目的:领会循环双链表存储结构和掌握循环双链表中各种基本运算算法设计。 内容:编写一个程序cdinklist.cpp,实现循环双链表的各种基本运算和整体建表算法(假设循环双链表的元素类型ElemType为char),并…...
ElasticSearch IK分词器的安装、词典扩展与停用
🏷️个人主页:牵着猫散步的鼠鼠 🏷️系列专栏:云原生与服务部署-专栏 🏷️个人学习笔记,若有缺误,欢迎评论区指正 目录 编辑 1. 前言 2. IK分词器安装 3. IK分词器词典扩展与停用 4. 总…...
代码随想录训练营总结
为期两个月的代码随想录训练营今天结束了,我想我的收获是非常大的。进到训练营的大群里,令我有种安心的感觉,原来世界各地有这么多与我一起努力的伙伴。更令人安心的是知识星球对于学习进度的规划,细化到每一天每道题,…...
深度学习-转置卷积
转置卷积 转置卷积(Transposed Convolution),也被称为反卷积(Deconvolution),是深度学习中的一种操作,特别是在卷积神经网络(CNN)中。它可以将一个低维度的特征图&#x…...
Unity性能优化工具介绍
文章目录 一.Stats组件1.Audio音频的数据组件:2.图形数据 二.Profiler 性能分析器 一.Stats组件 Unity自带Statistics(统计数据),Game视窗中点击Stats打开 1.Audio音频的数据组件: 1):Level 声音强度 单位是分贝(dB) 表示音频听声音的大小,是闪烁波动的. 2):SDPload 数据信…...
Math之向上向下取整
有时我们会遇到向上和向下取整的操作,这时我们可以使用Math类来进行操作。 1、向上取整 Math.ceil() 方法返回大于或等于指定表达式的最小整数(即向上取整)。如果参数是一个整数,那么结果就是这个整数本身。 示例: …...
MPP架构
MPP架构,即Massively Parallel Processing(大规模并行处理)架构,是一种用于处理大规模数据的并行计算架构。它通过将数据和计算能力分布在多个处理节点上,利用并行处理技术来加速数据处理和分析的速度。 在MPP架构中&…...
These relative modules were not found:* ../../../constant in
这个错误信息表明,你的项目在尝试加载一个相对路径模块 ../../../constant 时遇到了问题。具体来说,它在 ./node_modules/cache-loader/dist/cj 这个路径下找不到这个模块。 这里有几个可能的原因和相应的解决方案: 路径错误:首…...
2024最新彩虹聚合DNS管理系统源码v1.3 全开源
2024最新彩虹聚合DNS管理系统源码v1.3 全开源 聚合DNS管理系统可以实现在一个网站内管理多个平台的域名解析,目前已支持的域名平台有:阿里云、腾讯云、华为云、西部数码、DNSLA、CloudFlare。 本系统支持多用户,每个用户可分配不同的域名解…...
在Go语言中如何实现变参函数和函数选项模式
在Go语言编程中,我们经常会遇到需要给函数传递可选参数的情况。传统的做法是定义一个结构体,将所有可选参数作为结构体字段,然后在调用函数时创建该结构体的实例并传递。这种方式虽然可行,但是当可选参数较多时,创建结构体实例的代码就会变得冗长และ不太直观。 Go语言的一个…...
Spring Boot中的 6 种API请求参数读取方式
使用Spring Boot开发API的时候,读取请求参数是服务端编码中最基本的一项操作,Spring Boot中也提供了多种机制来满足不同的API设计要求。 接下来,就通过本文,为大家总结6种常用的请求参数读取方式。如果你发现自己知道的不到6种&a…...
Linux基础命令[27]-gpasswd
文章目录 1. gpasswd 命令说明2. gpasswd 命令语法3. gpasswd 命令示例3.1 不加参数3.2 -a(将用户加入组)3.3 -d(从组中删除用户)3.4 -r(删除组密码)3.5 -M(多个用户一起加入组)3.6 …...
机会约束转化为确定性约束-- 样本均值法
当涉及到新能源消纳的机会约束规划时,我们需要深入理解其背后的原理和采用的方法。以下是对上文内容的更详细且更贴切的展开解释: 机会约束转化为确定性约束-- 样本均值法代码获取戳此处代码获取戳此处代码获取戳此处 新能源消纳的机会约束 新能源&…...
uniapp中,当页面显示时触发子组件的重新渲染
使用watch监听数据变化: 在子组件中使用watch来监听父组件传递的数据,一旦数据发生变化,子组件就会重新渲染。 子组件代码示例: <template><div>{{ message }}</div> </template><script> export d…...
先进制造aps专题五 aps软件的排程算法和优化算法介绍
aps软件的核心,主要是数据管理,排程/优化算法,各类甘特图 所有aps软件排程算法都是Heuristics启发式算法(如Greedy算法),只是有的aps软件还支持ga遗传算法优化(比如sap apo,oracle aps,isuperap…...
【跳坑日记】暴力解决Ubuntu SSH报错: Failed to start OpenBSD Secure Shell server
报错环境说明: 服务器环境:Ubuntu 20.04 错误内容 最近服务器突然报错,提示如下图信息: 搜素了各种问答,国内的回答大多数是用 ssh-keygen -A命令来解决,但最终也无法登录服务器。 最终搜索到ask ubun…...
从需求角度介绍PasteSpider(K8S平替部署工具适合于任何开发语言)
你是否被K8S的强大而吸引,我相信一部分人是被那复杂的配置和各种专业知识而劝退,应该还有一部分人是因为K8S太吃资源而放手! 这里介绍一款平替工具PasteSpider,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],Pwitwc…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
