动态规划-子序列问题——1218.最长定差子序列
1.题目解析
题目来源:1218.最长定差子序列——力扣

测试用例

2.算法原理
1.状态表示
本题可以看作是寻找一个等差序列,并且公差给出,这里并不是普通的使用一个dp表,而是将arr与dp表同时存储于一个哈希表,arr[i]映射dp[i],这样就可以只遍历符合等差序列的每个位置而不用遍历所有位置
2.状态转移方程
只需要找到符合等差序列的哈希表就直接对等差序列长度+1即可,即:hash[arr[i]] = hash[arr[i] - difference] + 1;
3.初始化
最小等差序列的长度为1,将第一个哈希表的位置置为1即可
4.填表顺序
从左到右只填写符合等差序列位置的值
5.返回值
返回哈希表的最大值

3.实战代码
class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size();unordered_map<int,int> hash;//arr[i] - dp[i]hash[arr[0]] = 1;int ret = 1;for(int i = 1;i < n;i++){hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret,hash[arr[i]]);}return ret;}
};
相关文章:
动态规划-子序列问题——1218.最长定差子序列
1.题目解析 题目来源:1218.最长定差子序列——力扣 测试用例 2.算法原理 1.状态表示 本题可以看作是寻找一个等差序列,并且公差给出,这里并不是普通的使用一个dp表,而是将arr与dp表同时存储于一个哈希表,arr[i]映射dp…...
双子塔楼宇可视化系统:提升建筑管理与运营效率
利用图扑可视化技术对双子塔楼宇的各项功能进行实时监控和管理。通过数据分析优化资源配置,提高能源效率,增强楼宇安全性,实现智能化运营。...
32位的ARMlinux的4字节变量原子访问问题
在32位的ARM Linux内核中,4字节整型变量通常被认为是原子操作。 这主要是因为: 对齐要求:在ARM架构中,4字节整型变量通常是按4字节对齐存储的,这样可以确保在读取和写入时,CPU能够以单个指令完成操作。 …...
用哪种建站程序做谷歌SEO更容易?
做网站很容易,但做一个能带来流量和订单的网站就没那么简单了。尤其是在谷歌SEO优化方面,不同的建站程序对SEO的支持程度也不同。在这方面,WordPress和Shopify无疑是最佳选择。 WordPress作为一个内容管理系统(CMS)&am…...
IPsec简单介绍
VPN相关介绍 VPN:虚拟私有网络 例如:像这种不加密的 PPTPL2TP ------- 一般用在windows server 服务端(但是大多数企业不用这个) 假如总公司内部的PC1要去访问分公司内部的PC2(一般用在公司服务器有内网的服务&#…...
颠覆级AI:10秒生成超清视频
颠覆级AI:10秒生成超清视频 Pyramid-Flow 是一款开源 AI 视频生成神器💻,只需文字或图片即可极速生成高清视频🎥!高效、高清、资源需求低,适合创作广告、教学视频等多种用途🚀,快来…...
《西安科技大学学报》
《西安科技大学学报》主要刊载安全科学与工程、矿业工程、建筑与土木工程、地质与环境工程、测绘工程、材料科学与工程、化学与化工、机械工程、电气工程及自动化、通信与信息工程、计算机科学与工程、矿业经济管理等专业领域内具有创新性的学术论文和科研成果。 来稿必须符合以…...
redis详细教程(2.List教程)
List是一种可以存储多个有序字符串的数据类型,其中的元素按照顺序排列(可以重复出现),可以通过数字索引来访问列表中的元素,索引可以从左到右或者从右到左。 Redis 列表可以通过两种方式实现:压缩列表&…...
电子电气架构 --- 电气系统工程
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...
15-4连续子串和的整除问题
问题描述 小M是一个五年级的小学生,今天他学习了整除的知识,想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1},然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这…...
Spring源码:Bean创建、Bean获取
Bean是怎么被创建,如何获取Bean,基于Spring 5.3.24版本,Spring Boot 可用 2.7.6 结论: 创建:非懒加载的单实例bean在容器创建的时候创建,通过beanFactory的doGetBean方法,利用反射进行创建&…...
MetaArena推出《Final Glory》:引领Web3游戏技术新风向
随着区块链技术的日益成熟,Web3游戏成为了游戏产业探索的新方向,将去中心化经济与虚拟世界结合在一起,形成了一个全新的生态体系。然而,尽管Web3游戏展示了令人兴奋的可能性,但其背后的技术障碍依旧严峻,特…...
玩转Shodan:深度挖掘特定漏洞与脆弱资产的实战技巧
内容预览 ≧∀≦ゞ Shodan进阶使用之发现并解锁隐藏的脆弱资产声明导语VNC未授权访问查询被黑的网站查询思科未授权设备查询MongoDB未授权访问搜索后台管理页面结语 Shodan进阶使用之发现并解锁隐藏的脆弱资产 声明 笔记内容参考了B站UP主泷羽sec的学习视频,如有侵…...
Java程序设计:spring boot(8)——API ⽂档构建⼯具 - Swagger2
目录 1 环境整合配置 2 Swagger2 常⽤注解说明 2.1 Api 2.2 ApiOperation 2.3 ApiImplicitParams 2.4 ApiResponses 2.5 ApiModel 3 用户模块注解配置 3.1 Controller 使用注解 3.2 JavaBean 使用注解 4 Swagger2 接⼝⽂档访问 由于 Spring Boot 能够快速开发、便捷…...
【Python】if选择判断结构详解:逻辑分支与条件判断
目录 🍔 if选择判断结构作用 1.1 if选择判断结构的基本语法 1.2 if选择结构案例 1.3 if...else...结构 1.4 if...elif...else多条件判断结构 1.5 if嵌套结构 🍔 综合案例:石头剪刀布 2.1 需求分析 2.2 代码实现 2.3 随机出拳 &…...
邮件系统SSL加密传输,保护你的电子邮件免受网络威胁
在互联网的浪潮中,企业数字化转型的步伐不断加快。企业邮箱作为数字化应用的重要组成部分,已成为员工沟通、协同工作和企业管理的关键工具。但是在公共网络安全性普遍较弱的背景下,黑客容易侵入企业网络,监控流量,截获…...
Redis_写时复制(cow)
Redis会根据配置,每隔一段时间中对Redis服务中当下的数据集进行快照。配置自动生成rdb文件,后台使用的是bgsave方式。 save 60 1000 //关闭RDB只需要将所有的save保存策略注释掉即可Redis借助操作系统提供的写时复制技术(Copy-On-Write, COW…...
【mysql进阶】4-5. InnoDB 内存结构
InnoDB 内存结构 1 InnoDB存储引擎中内存结构的主要组成部分有哪些? 🔍 分析过程 从官⽹给出的InnoDB架构图中可以找到答案 InnoDB存储引擎架构链接:https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html ✅ 解答问题 InnoD…...
从零入门扣子Bot开发
从零入门扣子Bot开发 工作流简单介绍问题思考工作流实例 图像流简单介绍瘦脸图像流的设计创建图像流设计流程 总结参考链接 工作流简单介绍 工作流起源于生产组织和办公自动化领域,是指在计算机应用环境下,对业务过程的部分或整体进行自动化处理。它通过…...
中药是怎么计价的 复制药方文本划价系统操作教程
一、概述 【软件资源文件下载可以点文章最后卡片】 通过复制药方文本,快速划价并计算出总金额。 可以保存记录,如日期,客户名称,药方名称,金额等,便于查询统计或导出表格。 中药划价系统怎么收费 中药是…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
