动态规划学习——子序列问题
目录
编辑
一,最长定差子序列
1.题目
2,题目接口
3,解题思路及其代码
一,最长定差子序列
1.题目
给你一个整数数组
arr和一个整数difference,请你找出并返回arr中最长等差子序列的长度,该子序列中相邻元素之间的差等于difference。子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从
arr派生出来的序列。示例 1:
输入:arr = [1,2,3,4], difference = 1 输出:4 解释:最长的等差子序列是 [1,2,3,4]。示例 2:
输入:arr = [1,3,5,7], difference = 1 输出:1 解释:最长的等差子序列是任意单个元素。示例 3:
输入:arr = [1,5,7,8,5,3,4,2,1], difference = -2 输出:4 解释:最长的等差子序列是 [7,5,3,1]。
2,题目接口
class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {}
};
3,解题思路及其代码
1.状态转移方程:
这道题要我们求的是最长定差子序列问题,不再是最长子序列。这里的关键便是定差,也就是说在我们知道差以后我们便可以知道第2个数的值。我们的dp[i] 表示为以i位置为结尾的最长等差子序列。
2.初始化:
当我们的每个nums[i]单独构成一个子序列时长度为1,所以我们初始化时边初始化为1即可。
在明确好这些后便可以写出如下代码:
class Solution { public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size();vector<int>dp(n,1);int Maxlenth = 1;for(int i = 0;i<n;i++){int num = arr[i]+difference;//找定差for( int j = i+1;j<n;j++){if(arr[j] == num){dp[j] = dp[i]+1;}}Maxlenth = max(Maxlenth,dp[i]);//每次都要更新一下最大值}return Maxlenth;} };但是,这个代码是过不了的。因为这个代码的时间复杂度为O(n^2)。所以我们要对这个代码做一些优化。优化的秘诀便是hash表:unordered_map。改进思路如下:
1.先创建一个hash表。
2.将arr里面的所有元素和元素的对应下标放到hash表中构成映射,arr[i]作key,下标作value。
现在改进代码如下:
class Solution { public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int,int> hash;//在hash表里做dpint n = arr.size();int Max = 1;hash[arr[0]] = 1;for(int i = 1;i<n;i++){hash[arr[i]] = hash[arr[i]-difference]+1;//如果arr[i]-difference那也会访问最后一个arr[i]-difference的值。因为hash的底层插入是头插Max = max(Max,hash[arr[i]]);}return Max;} };
提交:过啦!!!

相关文章:
动态规划学习——子序列问题
目录 编辑 一,最长定差子序列 1.题目 2,题目接口 3,解题思路及其代码 一,最长定差子序列 1.题目 给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列…...
使用 COPY 加速 PostgreSQL 批量插入
文章目录 1.copy命令介紹2.copy vs insert的优势3.测量性能4.结论 1.copy命令介紹 PostgreSQL 中的命令COPY是执行批量插入和数据迁移的强大工具。它允许快速有效地将大量数据插入表中。 COPY命令为批量插入和数据迁移提供了更简单且更具成本效益的解决方案。 可以避免使用诸…...
plotneuralnet和netron结合绘制模型架构图
plotneuralnet和netron结合绘制模型架构图 一、plotneuralnet 本身的操作 模型结构图的可视化,能直观展示模型的结构以及各个模块之间的关系。最近借助plotneuralnet python库(windows版)绘制了一个网络结构图,有一些经验和心得…...
MYSQL 中如何导出数据?
文章目录 前言MySQL 导出数据使用 SELECT ... INTO OUTFILE 语句导出数据SELECT ... INTO OUTFILE 语句有以下属性:导出表作为原始数据导出SQL格式的数据将数据表及数据库拷贝至其他主机 后言 前言 hello world欢迎来到前端的新世界 😜当前文章系列专栏:…...
GPT-4惨遭削弱,偷懒摸鱼绝不多写一行代码,OpenAI已介入调查
GPT-4再次遭网友“群攻”,原因是“懒”得离谱! 有网友想在Android系统开发一个能够与OpenAI API实时交互的应用。 于是把方法示例链接发给GPT-4,让它参考用Kotlin语言编写代码: 没成想,和GPT-4一来二去沟通半天,GPT-4死活给不出…...
CSS特效020:涌动的弹簧效果
CSS常用示例100专栏目录 本专栏记录的是经常使用的CSS示例与技巧,主要包含CSS布局,CSS特效,CSS花边信息三部分内容。其中CSS布局主要是列出一些常用的CSS布局信息点,CSS特效主要是一些动画示例,CSS花边是描述了一些CSS…...
系列五、Spring整合MyBatis不忽略mapper接口同目录的xxxMapper.xml
一、概述 默认情况下maven要求我们将xml配置、properties配置等都放在resources目录下,如果我们强行将其放在java目录,即将xxxMapper.xml和xxxMapper接口放在同一个目录下,那么默认情况下maven打包时会将这个xxxMapper.xml文件忽略掉…...
第454题.四数相加II
力扣题目链接 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] 0 分析: 当需要判断一个元素是…...
RabbitMQ消息队列
简介 MQ(message queue),从字面意思上看就个 FIFO 先入先出的队列,只不过队列中存放的内容是 message 而已,它是一种具有接收数据、存储数据、发送数据等功能的技术服务。 作用:流量削峰、应用解耦、异步处理。 生产者将消息发送…...
ModBus电表与RS485电表有哪些区别?
在能源计量领域,ModBus电表和RS485电表是两种常见的设备,它们都具有监测和记录电能数据的功能。然而,它们之间存在一些区别,比如通信协议、连接方式、数据格式等等参数的区别有哪些? ModBus电表和RS485电表都是用于电能…...
vue项目运行时,报错:ValidationError: webpack Dev Server Invalid Options
在运行vue项目中,遇到报错:ValidationError: webpack Dev Server Invalid Options,如下图截图: 主要由于vue.config.js配置文件错误导致的,具体定位到proxy配置代理不能为空,导致运行项目报错,需…...
书摘:C 嵌入式系统设计模式 02
本书的原著为:《Design Patterns for Embedded Systems in C ——An Embedded Software Engineering Toolkit 》,讲解的是嵌入式系统设计模式,是一本不可多得的好书。 本系列描述我对书中内容的理解。 结构化编程将软件组织成两个截然不同的…...
排序算法基本原理及实现1
📑打牌 : da pai ge的个人主页 🌤️个人专栏 : da pai ge的博客专栏 ☁️宝剑锋从磨砺出,梅花香自苦寒来 📑插入排序 Ǵ…...
Unity 轨道展示系统(DollyMotion)
DollyMotion 🍱功能展示🥙使用💡设置路径点💡触发点位切换💡动态更新路径点💡事件触发💡设置路径💡设置移动方案固定速度方向最近路径方向 💡设置移动速度曲线 传送门 &a…...
优维低代码实践:搜索功能
优维低代码技术专栏,是一个全新的、技术为主的专栏,由优维技术委员会成员执笔,基于优维7年低代码技术研发及运维成果,主要介绍低代码相关的技术原理及架构逻辑,目的是给广大运维人提供一个技术交流与学习的平台。 优维…...
C# ReadOnlyRef Out
C# ReadOnly ReadOnly先看两种情况1.值类型2.引用类型 结论 Ref Out ReadOnly官方文档 ReadOnly 先看两种情况 1.值类型 当数据是值类型时,标记为Readonly时,如果再次设置值,会提示报错,无法分配到只读字段 public class A {pri…...
linux 服务 下 redis 安装和 启动
官网下载 https://redis.io/download/ 安装步骤: 1.安装redis 所需要的依赖 yum install -y gcc tcl2.上传安装包并解压,下载安装包,上传到/usr/local/src目录,解压 tar -zxvf redis-7.2.3.tat.gz进入安装目录,运行…...
ECharts与Excel的结合实战
引言:本文是一篇ECharts和Excel实战的记录。将Excel与ECharts产生火花,从Excel读取数据然后在ECharts上展示。 1.柱状图前端代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title…...
UDP的特点及应用场景
目录 UDP特点 应用场景 总结 User Datagram Protocol(UDP,用户数据报协议)是互联网协议套件中的一种传输层协议。与TCP不同,UDP是一种无连接的、不可靠的协议。 UDP特点 要知道UDP可以用来做什么,首先我们要知道它…...
Python开发——工具篇 Pycharm的相关配置,Python相关操作 持续更新
前言 本篇博客是python开发的工具篇相关,介绍pycharm的使用和相关配置,收录python的相关操作,比如如何启动jupyter。 目录 前言引出Pycharmpycharm如何不同等级日志显示不同颜色设置不同pycharm的python环境 Python操作如何启动Jupyter 总结…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...

