每天一道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ÿ…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
