代码随想录算法训练营第二十九天| LeetCode491.递增子序列* 、LeetCode46.全排列*、LeetCode47.全排列 II
#LeetCode 491. Non-decreasing Subsequences
#LeetCode 491. 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili
首先,本题不能考虑首先对数组排序,排序会导致数组直接变为一个递增的序列。本题依然是一个组合问题,所以无序,i 在for loop中依然是从startIndex 开始。与之前的去重逻辑不同,每一层会有一个uset 变量,是记录本层元素是否重复使用,新的一层uset都会重新定义,不是之前去重那样的全局变量,同样回溯的时候也不需要删除元素,也是在树层去重。
代码:
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex) {if (startIndex > nums.length) {return;}if (path.size() > 1) {result.add(new ArrayList<>(path));}HashSet<Integer> uset = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {if (!path.isEmpty() && path.getLast() > nums[i] || uset.contains(nums[i])) {continue;}uset.add(nums[i]);path.addLast(nums[i]);backtracking(nums, i + 1);path.removeLast();}}
}
#LeetCode 46. Permutations
#LeetCode 46. 视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列_哔哩哔哩_bilibili
与之前的组合问题不同的地方在于,排列是有序的,[1, 2] 和[2, 1] 是不同的,如果用used 数组,那么在for loop 遍历的时候也是通过used 数组的标记,来判断下一次取具体哪一个数字。
回溯方法代码:
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new LinkedList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}used[i] = true;path.addLast(nums[i]);backtracking(nums, used);used[i] = false;path.removeLast();}}
}
#LeetCode 47. Permutations II
#LeetCode 47. 视频讲解:回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili
如果完成了之前的题目,那么这个题目较简单,排列的思想与上一个题目相似,去重与之前组合去重相似,记得数组需要排序。
回溯方法代码:
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new LinkedList<>(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;}path.addLast(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.removeLast();}}
}相关文章:
代码随想录算法训练营第二十九天| LeetCode491.递增子序列* 、LeetCode46.全排列*、LeetCode47.全排列 II
#LeetCode 491. Non-decreasing Subsequences #LeetCode 491. 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 首先,本题不能考虑首先对数组排序,排序会导致数组直接变为一个…...
基于SpringBoot设计模式之开端
文章目录 前言引言开始 前言 为了更好的在项目中,能更加优雅的使用设计模式,比较针对性的解决我们的问题。我将在这个专栏详细的描述23种设计模式,为了与时俱进,我打算通过springboot的形式将23种设计模式全部撸完! 引…...
tensorflow实现二分类
# 导入所需库和模块 from tensorflow.keras.layers import Dense, Input, Activation # 导入神经网络层和激活函数模块 from tensorflow.keras.models import Sequential # 导入Keras的Sequential模型 import pandas as pd # 导入Pandas库用于数据处理 import numpy as np …...
简化路径[中等]
优质博文:IT-BLOG-CN 一、题目 给你一个字符串path,表示指向某一文件或目录的Unix风格 绝对路径 (以/开头),请你将其转化为更加简洁的规范路径。在Unix风格的文件系统中,一个点.表示当前目录本身&#x…...
记一次若依项目组装树型结构数据的效率优化
背景 最近公司的项目使用了若依框架做开发,发现部门管理功能的部门如果有3万笔记录时,查询部门信息并组装为父子结构时运行特别缓慢,本地运行需要3分钟才能加载出来,因此接到优化的工作。 代码展示 首先看看表结构是这么定义的…...
秒杀系统之系统优化
3 系统优化 对于一个软件系统,提高性能可以有很多种手段,如提升硬件水平、调优JVM 性能,这里主要关注代码层面的性能优化—— 减少序列化:减少 Java 中的序列化操作可以很好的提升系统性能。序列化大部分是在 RPC 阶段发生&#x…...
【介绍下Python多线程,什么是Python多线程】
🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者,CSDN实力新星,CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共…...
FPGA相关论文阅读
一、Achieving 100Gbps Intrusion Prevention on a Single Server 论文名称中文翻译:在单台服务器上实现100Gbps吞吐量的入侵防御检测。 文章中的Mixed-1和Norm-1 二、Distributed Password Hash Computation on Commodity Heterogeneous Programmable Platforms…...
瑞芯微RK3588驱动设计之DVP并口摄像头2
dts配置看瑞芯微RK3588驱动配置之DVP并口摄像头1_rockchip 调试dvp设备 直接显示摄像头数据-CSDN博客 这里看看驱动的具体实现,以gc2145为例。 gc2145的驱动源码如下: // SPDX-License-Identifier: GPL-2.0 /** GC2145 CMOS Image Sensor driver*** C…...
安卓手机APP开发__支持64位的架构
安卓手机APP开发__支持64位的架构 目录 概述 读取你的APP 快速的状态检查 你的APP使用了原生的代码吗? 你的APP包含了64位的代码库吗? 确保在这些目录中有原生的代码库. 使用APK分析器查看原生的代码库 通过解压缩APK查看原生的代码库 用安卓工…...
Foxmail使用经验总结
目录 1.概述 2.版本历史 3.使用方法 3.1.安装和设置账户 3.2.收取和阅读邮件 3.3.发送邮件 3.4.管理联系人 3.5.日程安排和任务管理 3.6.定制设置和插件 3.7.跨平台同步 4.小结 1.概述 Fox…...
信息系统项目管理师0601:项目立项管理 — 考点总结(可直接理解记忆)
点击查看专栏目录 项目立项管理 — 考点总结(可直接理解记忆) 1.项目建议书(又称立项申请)是项目建设单位向上级主管部门提交项目申请时所必须的文件,是对拟建项目提出的框架性的总体设想。在项目建议书批准后,方可开展对外工作(掌握)。 2.项目建议书应该包括的核心内…...
实验三:机器学习1.0
要求: 针对实验1和实验2构建的数据集信息分析 设计实现通过数据简介进行大类分类的程序 代码实现: 训练集数据获取: read_data.py import json import pickledef read_intro():data []trypathr"E:\Procedure\Python\Experiment\f…...
Vue 3 + Vite项目实战:常见问题与解决方案全解析
文章目录 一、项目使用本地图片打包后不显示1、在html中时候,本地运行和打包后线上运行都ok。2、用动态数据,本地运行ok,打包后线上运行不显示3、适用于处理单个链接的资源文件4、用动态数据且本地和线上访问都可显示 二、使用插件vite-plugi…...
飞天使-k8s知识点31-rancher的正确打开方式
文章目录 安装之前优化一下内核参数以及系统内核版本 rancher安装主要是使用以下命令nginx的配置为解决办法 安装之前优化一下内核参数以及系统内核版本 内核版本 4.17 cat > /etc/modules-load.d/iptables.conf <<EOF ip_tables iptable_filter EOF 然后重启服务器…...
Vue.component v2v3注册(局部与全局)组件使用详解
在Vue中,可以通过两种方式注册组件:局部注册和全局注册。 局部注册是在父组件中通过import和components选项注册的组件,仅在当前父组件及其子组件中可用。 // 父组件中import ChildComponent from ./ChildComponent.vue;export default {co…...
HNU-算法设计与分析-作业5
第五次作业【回溯算法】 文章目录 第五次作业【回溯算法】<1> 算法分析题5-3 回溯法重写0-1背包<2> 算法分析题5-5 旅行商问题(剪枝)<3> 算法实现题5-2 最小长度电路板排列问题<4> 算法实现题5-7 n色方柱问题<5> 算法实现…...
基础之音视频2
01 前言 02 mp 03 mp实例 简易音乐播放器 04 音频 sound-pool 1.作用 播放多个音频,短促音频 2.过程 加载load- 3.示例 模拟手机选铃声 步骤: 创建SoundPool对象,设置相关属性 音频流存入hashmap 播放音频 05 videoview 3gp 体积小 mp4 …...
两小时看完花书(深度学习入门篇)
1.深度学习花书前言 机器学习早期的时候十分依赖于已有的知识库和人为的逻辑规则,需要人们花大量的时间去制定合理的逻辑判定,可以说是有多少人工,就有多少智能。后来逐渐发展出一些简单的机器学习方法例如logistic regression、naive bayes等…...
21【Aseprite 作图】画白菜
1 对着参考图画轮廓 2 缩小尺寸 变成这样 3 本来是红色的描边,可以通过油漆桶工具(取消 “连续”),就把红色的轮廓线,变成黑色的 同时用吸管工具,吸取绿色和白色,用油漆桶填充颜色 4 加上阴影…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
