每天一道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ÿ…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
