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

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...