动态规划-子序列问题——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开发 工作流简单介绍问题思考工作流实例 图像流简单介绍瘦脸图像流的设计创建图像流设计流程 总结参考链接 工作流简单介绍 工作流起源于生产组织和办公自动化领域,是指在计算机应用环境下,对业务过程的部分或整体进行自动化处理。它通过…...
中药是怎么计价的 复制药方文本划价系统操作教程
一、概述 【软件资源文件下载可以点文章最后卡片】 通过复制药方文本,快速划价并计算出总金额。 可以保存记录,如日期,客户名称,药方名称,金额等,便于查询统计或导出表格。 中药划价系统怎么收费 中药是…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)
目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 编辑编辑 UDP的特征 socke函数 bind函数 recvfrom函数(接收函数) sendto函数(发送函数) 五、网络编程之 UDP 用…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...
MCP和Function Calling
MCP MCP(Model Context Protocol,模型上下文协议) ,2024年11月底,由 Anthropic 推出的一种开放标准,旨在统一大模型与外部数据源和工具之间的通信协议。MCP 的主要目的在于解决当前 AI 模型因数据孤岛限制而…...
