代码随想录算法训练营第二十九天| 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 加上阴影…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
