动态规划学习——子序列问题
目录
编辑
一,最长定差子序列
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 总结…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
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…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

