动态规划学习——子序列问题
目录
编辑
一,最长定差子序列
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 总结…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...

