每天一道leetcode:1218. 最长定差子序列(动态规划中等)
今日份题目:
给你一个整数数组 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]。
提示
-
1 <= arr.length <= 105 -
-104 <= arr[i], difference <= 104
题目思路
这道题目,我们假设选择当前数据,那么到目前数值为止的最长序列长度应该为这个数值减去difference的那个数记录的长度加一,所以得到状态转移方程:dp[arr[i]]=dp[arr[i]-difference]+1;
注意:由于arr[i]的数据范围有负数,普通的数组不能用来记录有负数的情况,故使用unordered_map记录dp值。
代码
class Solution
{
public:int longestSubsequence(vector<int> &arr, int difference) {int ans=0;unordered_map<int,int> dp; //假设结果序列选择当前数据,那么到目前数值为止的最长序列长度为状态转移方程for(int i=0;i<arr.size();i++) {dp[arr[i]]=dp[arr[i]-difference]+1; //状态转移方程ans=max(ans,dp[arr[i]]); //记录最大结果}return ans;}
};
提交结果

欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!
更新不易,宝子们点个赞支持下,谢谢!
相关文章:
每天一道leetcode:1218. 最长定差子序列(动态规划中等)
今日份题目: 给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference 。 子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何…...
C#的 Settings.Settings配置文件的使用方法
1、定义 在Settings.settings文件中定义配置字段。把作用范围定义为:User则运行时可更改(用户范围的字段数据更改存储在用户信息中,不在该程序文件中),Applicatiion则运行时不可更改。可以使用数据网格视图(VS软件的Properties 下面的Setting…...
神经网络基础-神经网络补充概念-35-为什么正则化可以减少过拟合
概念 正则化可以减少过拟合的原因在于它通过限制模型的复杂性来约束参数的取值范围,从而提高了模型的泛化能力。过拟合是指模型在训练集上表现很好,但在未见过的数据上表现不佳,这通常是因为模型过于复杂,过多地拟合了训练数据中…...
Glide 的超时控制相关处理
作者:newki 前言 Glide 相信大家都不陌生,各种源码分析,使用介绍大家应该都是烂熟于心。但是设置 Glide 的超时问题大家遇到过没有。 我遇到了,并且掉坑里了,情况是这样的。 调用接口从网络拉取用户头像,…...
使用requests如何实现自动登录
不知道大家有没有注意到,好多网站我们登录过后,在之后的某段时间内访问该网页时,不会给出请登录的提示,时间到期后就会提示请登录!这样在使用爬虫访问网页时还要登录,打乱我们的节奏,那么如何使…...
【代码随想录-Leetcode第六题:209. 长度最小的子数组】
209. 长度最小的子数组 题目思路代码实现 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回…...
部署LVS-DR群集
LVS的工作模式及工作过程 LVS 有三种负载均衡的模式,分别是VS/NAT(nat 模式)、VS/DR(路由模式)、VS/TUN(隧道模式)。 1、NAT模式(VS-NAT) 原理:首先负载均…...
建库、建表、修改表、复制表、字符类型、数值类型、枚举类型、日期时间类型、检索目录、数据导入命令、数据导入步骤、数据导出命令、非空、默认值、唯一索
Top NSD DBA DAY04 案例1:表管理案例2:数据类型案例3:数据批量处理案例4:表头基本约束 1 案例1:表管理 1.1 问题 建库练习建表练习修改表练习 1.2 方案 在MySQL50主机完成练习。 1.3 步骤 实现此案例需要按照如…...
iview默认样式覆盖
scoped 属性是 HTML5 中的新属性。 当style标签拥有scoped属性时,它的css样式只能用于当前的Vue组件,可以使组件的样式不相互污染。 如果一个项目的所有style标签都加上了scoped属性,相当于实现了样式的模块化。 1、全页面覆盖 不添加scoped…...
System.Text.Encoding不同字符编码之间进行转换
System.Text.Encoding 是 C# 中用于处理字符编码和字符串与字节之间转换的类。它提供了各种静态方法和属性,用于在不同字符编码之间进行转换,以及将字符串转换为字节数组或反之。 在处理多语言文本、文件、网络通信以及其他字符数据的场景中,…...
计组 | DMA
前言 记录一些计组相关联的题集与知识点,方便记忆与理解。 DMA 采用DMA方式传送数据时,每传送一个数据就要用一个( C)时间。 A 指令周期 B 机器周期 C 存储周期 D 总线周期发…...
在服务器开jupyter notebook server
参考 https://blog.csdn.net/qq_23869697/article/details/124178117https://blog.csdn.net/m0_37201243/article/details/122531675 1、安装notebook pip install notebook 2、生成配置文件 jupyter notebook --generate-config生成的配置文件,在linux下的路径…...
Jetpack 中的 databinding - 使用篇
什么叫databinding 数据绑定库是一种支持库,借助该库,您可以使用声明性格式(而非程序化地)将布局中的界面组件绑定到应用中的数据源。使用数据绑定可以简化 findViewById 。 如何使用 应用模块下 build.gradle 文件中添加 data…...
C++之signal信号应用实例(一百七十六)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…...
【数据分析入门】Numpy进阶
目录 一、数据重塑1.1 透视1.2 透视表1.3 堆栈/反堆栈1.3 融合 二、迭代三、高级索引3.1 基础选择3.2 通过isin选择3.3 通过Where选择3.4 通过Query选择3.5 设置/取消索引3.6 重置索引3.6.1 前向填充3.6.2 后向填充 3.7 多重索引 四、重复数据五、数据分组5.1 聚合5.2 转换 六、…...
数据结构的图存储结构
目录 数据结构的图存储结构 图存储结构基本常识 弧头和弧尾 入度和出度 (V1,V2) 和 的区别,v2> 集合 VR 的含义 路径和回路 权和网的含义 图存储结构的分类 什么是连通图,(强)连通图详解 强连通图 什么是生成树,生…...
爬虫IP时效问题:优化爬虫IP使用效果实用技巧
目录 1. 使用稳定的代理IP服务提供商: 2. 定期检测代理IP的可用性: 3. 配置合理的代理IP切换策略: 4. 使用代理IP池: 5. 考虑代理IP的地理位置和速度: 6. 设置合理的请求间隔和并发量: 总结 在爬虫过…...
【uniapp】picker mode=“region“ 最简单的省市区 三级联动
省市区 picker template <picker mode"region" :value"date" class"u-w-440" change"bindTimeChange"><u--inputborder"bottom"class"u-fb u-f-s-28"placeholder"请选择省市区"type"te…...
解决Java中的“Unchecked cast: java.lang.Object to java.util.List”问题
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
我的创作纪念日(128天)
机缘 CSDN账号创建已有3年了,本篇是第一篇纪念文。。。有点偷懒的感觉了。。。 从第一篇文章的发布,到现在已经过了128天了,回想起当时发布文章的原因,仅仅只是因为找不到合适的云笔记,鬼使神差的想到了CSDNÿ…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
