当前位置: 首页 > 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…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...