当前位置: 首页 > news >正文

每天一道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. 最长定差子序列(动态规划中等)

今日份题目&#xff1a; 给你一个整数数组 arr 和一个整数 difference&#xff0c;请你找出并返回 arr 中最长等差子序列的长度&#xff0c;该子序列中相邻元素之间的差等于 difference 。 子序列 是指在不改变其余元素顺序的情况下&#xff0c;通过删除一些元素或不删除任何…...

C#的 Settings.Settings配置文件的使用方法

1、定义 在Settings.settings文件中定义配置字段。把作用范围定义为&#xff1a;User则运行时可更改(用户范围的字段数据更改存储在用户信息中&#xff0c;不在该程序文件中)&#xff0c;Applicatiion则运行时不可更改。可以使用数据网格视图(VS软件的Properties 下面的Setting…...

神经网络基础-神经网络补充概念-35-为什么正则化可以减少过拟合

概念 正则化可以减少过拟合的原因在于它通过限制模型的复杂性来约束参数的取值范围&#xff0c;从而提高了模型的泛化能力。过拟合是指模型在训练集上表现很好&#xff0c;但在未见过的数据上表现不佳&#xff0c;这通常是因为模型过于复杂&#xff0c;过多地拟合了训练数据中…...

Glide 的超时控制相关处理

作者&#xff1a;newki 前言 Glide 相信大家都不陌生&#xff0c;各种源码分析&#xff0c;使用介绍大家应该都是烂熟于心。但是设置 Glide 的超时问题大家遇到过没有。 我遇到了&#xff0c;并且掉坑里了&#xff0c;情况是这样的。 调用接口从网络拉取用户头像&#xff0c…...

使用requests如何实现自动登录

不知道大家有没有注意到&#xff0c;好多网站我们登录过后&#xff0c;在之后的某段时间内访问该网页时&#xff0c;不会给出请登录的提示&#xff0c;时间到期后就会提示请登录&#xff01;这样在使用爬虫访问网页时还要登录&#xff0c;打乱我们的节奏&#xff0c;那么如何使…...

【代码随想录-Leetcode第六题:209. 长度最小的子数组】

209. 长度最小的子数组 题目思路代码实现 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回…...

部署LVS-DR群集

LVS的工作模式及工作过程 LVS 有三种负载均衡的模式&#xff0c;分别是VS/NAT&#xff08;nat 模式&#xff09;、VS/DR&#xff08;路由模式&#xff09;、VS/TUN&#xff08;隧道模式&#xff09;。 1、NAT模式&#xff08;VS-NAT&#xff09; 原理&#xff1a;首先负载均…...

建库、建表、修改表、复制表、字符类型、数值类型、枚举类型、日期时间类型、检索目录、数据导入命令、数据导入步骤、数据导出命令、非空、默认值、唯一索

Top NSD DBA DAY04 案例1&#xff1a;表管理案例2&#xff1a;数据类型案例3&#xff1a;数据批量处理案例4&#xff1a;表头基本约束 1 案例1&#xff1a;表管理 1.1 问题 建库练习建表练习修改表练习 1.2 方案 在MySQL50主机完成练习。 1.3 步骤 实现此案例需要按照如…...

iview默认样式覆盖

scoped 属性是 HTML5 中的新属性。 当style标签拥有scoped属性时&#xff0c;它的css样式只能用于当前的Vue组件&#xff0c;可以使组件的样式不相互污染。 如果一个项目的所有style标签都加上了scoped属性&#xff0c;相当于实现了样式的模块化。 1、全页面覆盖 不添加scoped…...

System.Text.Encoding不同字符编码之间进行转换

System.Text.Encoding 是 C# 中用于处理字符编码和字符串与字节之间转换的类。它提供了各种静态方法和属性&#xff0c;用于在不同字符编码之间进行转换&#xff0c;以及将字符串转换为字节数组或反之。 在处理多语言文本、文件、网络通信以及其他字符数据的场景中&#xff0c…...

计组 | DMA

前言 记录一些计组相关联的题集与知识点&#xff0c;方便记忆与理解。 DMA 采用DMA方式传送数据时&#xff0c;每传送一个数据就要用一个&#xff08; C&#xff09;时间。 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生成的配置文件&#xff0c;在linux下的路径…...

Jetpack 中的 databinding - 使用篇

什么叫databinding 数据绑定库是一种支持库&#xff0c;借助该库&#xff0c;您可以使用声明性格式&#xff08;而非程序化地&#xff09;将布局中的界面组件绑定到应用中的数据源。使用数据绑定可以简化 findViewById 。 如何使用 应用模块下 build.gradle 文件中添加 data…...

C++之signal信号应用实例(一百七十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…...

【数据分析入门】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 的含义 路径和回路 权和网的含义 图存储结构的分类 什么是连通图&#xff0c;&#xff08;强&#xff09;连通图详解 强连通图 什么是生成树&#xff0c;生…...

爬虫IP时效问题:优化爬虫IP使用效果实用技巧

目录 1. 使用稳定的代理IP服务提供商&#xff1a; 2. 定期检测代理IP的可用性&#xff1a; 3. 配置合理的代理IP切换策略&#xff1a; 4. 使用代理IP池&#xff1a; 5. 考虑代理IP的地理位置和速度&#xff1a; 6. 设置合理的请求间隔和并发量&#xff1a; 总结 在爬虫过…...

【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”问题

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

我的创作纪念日(128天)

机缘 CSDN账号创建已有3年了&#xff0c;本篇是第一篇纪念文。。。有点偷懒的感觉了。。。 从第一篇文章的发布&#xff0c;到现在已经过了128天了&#xff0c;回想起当时发布文章的原因&#xff0c;仅仅只是因为找不到合适的云笔记&#xff0c;鬼使神差的想到了CSDN&#xff…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...

CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)

漏洞概述 漏洞名称&#xff1a;Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号&#xff1a;CVE-2023-25194 CVSS评分&#xff1a;8.8 影响版本&#xff1a;Apache Kafka 2.3.0 - 3.3.2 修复版本&#xff1a;≥ 3.4.0 漏洞类型&#xff1a;反序列化导致的远程代…...

[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%

本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...