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

动态规划学习——子序列问题

目录

​编辑

一,最长定差子序列

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;}
};

提交:过啦!!!

相关文章:

动态规划学习——子序列问题

目录 ​编辑 一&#xff0c;最长定差子序列 1.题目 2&#xff0c;题目接口 3&#xff0c;解题思路及其代码 一&#xff0c;最长定差子序列 1.题目 给你一个整数数组 arr 和一个整数 difference&#xff0c;请你找出并返回 arr 中最长等差子序列的长度&#xff0c;该子序列…...

使用 COPY 加速 PostgreSQL 批量插入

文章目录 1.copy命令介紹2.copy vs insert的优势3.测量性能4.结论 1.copy命令介紹 PostgreSQL 中的命令COPY是执行批量插入和数据迁移的强大工具。它允许快速有效地将大量数据插入表中。 COPY命令为批量插入和数据迁移提供了更简单且更具成本效益的解决方案。 可以避免使用诸…...

plotneuralnet和netron结合绘制模型架构图

plotneuralnet和netron结合绘制模型架构图 一、plotneuralnet 本身的操作 模型结构图的可视化&#xff0c;能直观展示模型的结构以及各个模块之间的关系。最近借助plotneuralnet python库&#xff08;windows版&#xff09;绘制了一个网络结构图&#xff0c;有一些经验和心得…...

MYSQL 中如何导出数据?

文章目录 前言MySQL 导出数据使用 SELECT ... INTO OUTFILE 语句导出数据SELECT ... INTO OUTFILE 语句有以下属性:导出表作为原始数据导出SQL格式的数据将数据表及数据库拷贝至其他主机 后言 前言 hello world欢迎来到前端的新世界 &#x1f61c;当前文章系列专栏&#xff1a;…...

GPT-4惨遭削弱,偷懒摸鱼绝不多写一行代码,OpenAI已介入调查

GPT-4再次遭网友“群攻”&#xff0c;原因是“懒”得离谱! 有网友想在Android系统开发一个能够与OpenAI API实时交互的应用。 于是把方法示例链接发给GPT-4&#xff0c;让它参考用Kotlin语言编写代码: 没成想&#xff0c;和GPT-4一来二去沟通半天&#xff0c;GPT-4死活给不出…...

CSS特效020:涌动的弹簧效果

CSS常用示例100专栏目录 本专栏记录的是经常使用的CSS示例与技巧&#xff0c;主要包含CSS布局&#xff0c;CSS特效&#xff0c;CSS花边信息三部分内容。其中CSS布局主要是列出一些常用的CSS布局信息点&#xff0c;CSS特效主要是一些动画示例&#xff0c;CSS花边是描述了一些CSS…...

系列五、Spring整合MyBatis不忽略mapper接口同目录的xxxMapper.xml

一、概述 默认情况下maven要求我们将xml配置、properties配置等都放在resources目录下&#xff0c;如果我们强行将其放在java目录&#xff0c;即将xxxMapper.xml和xxxMapper接口放在同一个目录下&#xff0c;那么默认情况下maven打包时会将这个xxxMapper.xml文件忽略掉&#xf…...

第454题.四数相加II

力扣题目链接 给你四个整数数组 nums1、nums2、nums3 和 nums4 &#xff0c;数组长度都是 n &#xff0c;请你计算有多少个元组 (i, j, k, l) 能满足&#xff1a; 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] 0 分析&#xff1a; 当需要判断一个元素是…...

RabbitMQ消息队列

简介 MQ(message queue)&#xff0c;从字面意思上看就个 FIFO 先入先出的队列&#xff0c;只不过队列中存放的内容是 message 而已&#xff0c;它是一种具有接收数据、存储数据、发送数据等功能的技术服务。 作用&#xff1a;流量削峰、应用解耦、异步处理。 生产者将消息发送…...

ModBus电表与RS485电表有哪些区别?

在能源计量领域&#xff0c;ModBus电表和RS485电表是两种常见的设备&#xff0c;它们都具有监测和记录电能数据的功能。然而&#xff0c;它们之间存在一些区别&#xff0c;比如通信协议、连接方式、数据格式等等参数的区别有哪些&#xff1f; ModBus电表和RS485电表都是用于电能…...

vue项目运行时,报错:ValidationError: webpack Dev Server Invalid Options

在运行vue项目中&#xff0c;遇到报错&#xff1a;ValidationError: webpack Dev Server Invalid Options&#xff0c;如下图截图&#xff1a; 主要由于vue.config.js配置文件错误导致的&#xff0c;具体定位到proxy配置代理不能为空&#xff0c;导致运行项目报错&#xff0c;需…...

书摘:C 嵌入式系统设计模式 02

本书的原著为&#xff1a;《Design Patterns for Embedded Systems in C ——An Embedded Software Engineering Toolkit 》&#xff0c;讲解的是嵌入式系统设计模式&#xff0c;是一本不可多得的好书。 本系列描述我对书中内容的理解。 结构化编程将软件组织成两个截然不同的…...

排序算法基本原理及实现1

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 &#x1f4d1;插入排序 &#x1f4…...

Unity 轨道展示系统(DollyMotion)

DollyMotion &#x1f371;功能展示&#x1f959;使用&#x1f4a1;设置路径点&#x1f4a1;触发点位切换&#x1f4a1;动态更新路径点&#x1f4a1;事件触发&#x1f4a1;设置路径&#x1f4a1;设置移动方案固定速度方向最近路径方向 &#x1f4a1;设置移动速度曲线 传送门 &a…...

优维低代码实践:搜索功能

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…...

C# ReadOnlyRef Out

C# ReadOnly ReadOnly先看两种情况1.值类型2.引用类型 结论 Ref Out ReadOnly官方文档 ReadOnly 先看两种情况 1.值类型 当数据是值类型时&#xff0c;标记为Readonly时&#xff0c;如果再次设置值&#xff0c;会提示报错&#xff0c;无法分配到只读字段 public class A {pri…...

linux 服务 下 redis 安装和 启动

官网下载 https://redis.io/download/ 安装步骤&#xff1a; 1.安装redis 所需要的依赖 yum install -y gcc tcl2.上传安装包并解压&#xff0c;下载安装包&#xff0c;上传到/usr/local/src目录&#xff0c;解压 tar -zxvf redis-7.2.3.tat.gz进入安装目录&#xff0c;运行…...

ECharts与Excel的结合实战

引言&#xff1a;本文是一篇ECharts和Excel实战的记录。将Excel与ECharts产生火花&#xff0c;从Excel读取数据然后在ECharts上展示。 1.柱状图前端代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title…...

UDP的特点及应用场景

目录 UDP特点 应用场景 总结 User Datagram Protocol&#xff08;UDP&#xff0c;用户数据报协议&#xff09;是互联网协议套件中的一种传输层协议。与TCP不同&#xff0c;UDP是一种无连接的、不可靠的协议。 UDP特点 要知道UDP可以用来做什么&#xff0c;首先我们要知道它…...

Python开发——工具篇 Pycharm的相关配置,Python相关操作 持续更新

前言 本篇博客是python开发的工具篇相关&#xff0c;介绍pycharm的使用和相关配置&#xff0c;收录python的相关操作&#xff0c;比如如何启动jupyter。 目录 前言引出Pycharmpycharm如何不同等级日志显示不同颜色设置不同pycharm的python环境 Python操作如何启动Jupyter 总结…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...