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

动态规划-子序列问题——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.题目解析 题目来源&#xff1a;1218.最长定差子序列——力扣 测试用例 2.算法原理 1.状态表示 本题可以看作是寻找一个等差序列&#xff0c;并且公差给出&#xff0c;这里并不是普通的使用一个dp表&#xff0c;而是将arr与dp表同时存储于一个哈希表&#xff0c;arr[i]映射dp…...

双子塔楼宇可视化系统:提升建筑管理与运营效率

利用图扑可视化技术对双子塔楼宇的各项功能进行实时监控和管理。通过数据分析优化资源配置&#xff0c;提高能源效率&#xff0c;增强楼宇安全性&#xff0c;实现智能化运营。...

32位的ARMlinux的4字节变量原子访问问题

在32位的ARM Linux内核中&#xff0c;4字节整型变量通常被认为是原子操作。 这主要是因为&#xff1a; 对齐要求&#xff1a;在ARM架构中&#xff0c;4字节整型变量通常是按4字节对齐存储的&#xff0c;这样可以确保在读取和写入时&#xff0c;CPU能够以单个指令完成操作。 …...

用哪种建站程序做谷歌SEO更容易?

做网站很容易&#xff0c;但做一个能带来流量和订单的网站就没那么简单了。尤其是在谷歌SEO优化方面&#xff0c;不同的建站程序对SEO的支持程度也不同。在这方面&#xff0c;WordPress和Shopify无疑是最佳选择。 WordPress作为一个内容管理系统&#xff08;CMS&#xff09;&am…...

IPsec简单介绍

VPN相关介绍 VPN&#xff1a;虚拟私有网络 例如&#xff1a;像这种不加密的 PPTPL2TP ------- 一般用在windows server 服务端&#xff08;但是大多数企业不用这个&#xff09; 假如总公司内部的PC1要去访问分公司内部的PC2&#xff08;一般用在公司服务器有内网的服务&#…...

颠覆级AI:10秒生成超清视频

颠覆级AI&#xff1a;10秒生成超清视频 Pyramid-Flow 是一款开源 AI 视频生成神器&#x1f4bb;&#xff0c;只需文字或图片即可极速生成高清视频&#x1f3a5;&#xff01;高效、高清、资源需求低&#xff0c;适合创作广告、教学视频等多种用途&#x1f680;&#xff0c;快来…...

《西安科技大学学报》

《西安科技大学学报》主要刊载安全科学与工程、矿业工程、建筑与土木工程、地质与环境工程、测绘工程、材料科学与工程、化学与化工、机械工程、电气工程及自动化、通信与信息工程、计算机科学与工程、矿业经济管理等专业领域内具有创新性的学术论文和科研成果。 来稿必须符合以…...

redis详细教程(2.List教程)

List是一种可以存储多个有序字符串的数据类型&#xff0c;其中的元素按照顺序排列&#xff08;可以重复出现&#xff09;&#xff0c;可以通过数字索引来访问列表中的元素&#xff0c;索引可以从左到右或者从右到左。 Redis 列表可以通过两种方式实现&#xff1a;压缩列表&…...

电子电气架构 --- 电气系统工程

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...

15-4连续子串和的整除问题

问题描述 小M是一个五年级的小学生&#xff0c;今天他学习了整除的知识&#xff0c;想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1}&#xff0c;然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这…...

Spring源码:Bean创建、Bean获取

Bean是怎么被创建&#xff0c;如何获取Bean&#xff0c;基于Spring 5.3.24版本&#xff0c;Spring Boot 可用 2.7.6 结论&#xff1a; 创建&#xff1a;非懒加载的单实例bean在容器创建的时候创建&#xff0c;通过beanFactory的doGetBean方法&#xff0c;利用反射进行创建&…...

MetaArena推出《Final Glory》:引领Web3游戏技术新风向

随着区块链技术的日益成熟&#xff0c;Web3游戏成为了游戏产业探索的新方向&#xff0c;将去中心化经济与虚拟世界结合在一起&#xff0c;形成了一个全新的生态体系。然而&#xff0c;尽管Web3游戏展示了令人兴奋的可能性&#xff0c;但其背后的技术障碍依旧严峻&#xff0c;特…...

玩转Shodan:深度挖掘特定漏洞与脆弱资产的实战技巧

内容预览 ≧∀≦ゞ Shodan进阶使用之发现并解锁隐藏的脆弱资产声明导语VNC未授权访问查询被黑的网站查询思科未授权设备查询MongoDB未授权访问搜索后台管理页面结语 Shodan进阶使用之发现并解锁隐藏的脆弱资产 声明 笔记内容参考了B站UP主泷羽sec的学习视频&#xff0c;如有侵…...

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选择判断结构详解:逻辑分支与条件判断

目录 &#x1f354; if选择判断结构作用 1.1 if选择判断结构的基本语法 1.2 if选择结构案例 1.3 if...else...结构 1.4 if...elif...else多条件判断结构 1.5 if嵌套结构 &#x1f354; 综合案例&#xff1a;石头剪刀布 2.1 需求分析 2.2 代码实现 2.3 随机出拳 &…...

邮件系统SSL加密传输,保护你的电子邮件免受网络威胁

在互联网的浪潮中&#xff0c;企业数字化转型的步伐不断加快。企业邮箱作为数字化应用的重要组成部分&#xff0c;已成为员工沟通、协同工作和企业管理的关键工具。但是在公共网络安全性普遍较弱的背景下&#xff0c;黑客容易侵入企业网络&#xff0c;监控流量&#xff0c;截获…...

Redis_写时复制(cow)

Redis会根据配置&#xff0c;每隔一段时间中对Redis服务中当下的数据集进行快照。配置自动生成rdb文件&#xff0c;后台使用的是bgsave方式。 save 60 1000 //关闭RDB只需要将所有的save保存策略注释掉即可Redis借助操作系统提供的写时复制技术&#xff08;Copy-On-Write, COW…...

【mysql进阶】4-5. InnoDB 内存结构

InnoDB 内存结构 1 InnoDB存储引擎中内存结构的主要组成部分有哪些&#xff1f; &#x1f50d; 分析过程 从官⽹给出的InnoDB架构图中可以找到答案 InnoDB存储引擎架构链接&#xff1a;https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html ✅ 解答问题 InnoD…...

从零入门扣子Bot开发

从零入门扣子Bot开发 工作流简单介绍问题思考工作流实例 图像流简单介绍瘦脸图像流的设计创建图像流设计流程 总结参考链接 工作流简单介绍 工作流起源于生产组织和办公自动化领域&#xff0c;是指在计算机应用环境下&#xff0c;对业务过程的部分或整体进行自动化处理。它通过…...

中药是怎么计价的 复制药方文本划价系统操作教程

一、概述 【软件资源文件下载可以点文章最后卡片】 通过复制药方文本&#xff0c;快速划价并计算出总金额。 可以保存记录&#xff0c;如日期&#xff0c;客户名称&#xff0c;药方名称&#xff0c;金额等&#xff0c;便于查询统计或导出表格。 中药划价系统怎么收费 中药是…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...

CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14

什么是 Pattern Matching&#xff08;模式匹配&#xff09; ❝ 模式匹配就是一种“描述式”的写法&#xff0c;不需要你手动判断、提取数据&#xff0c;而是直接描述你希望的数据结构是什么样子&#xff0c;系统自动判断并提取。❞ 你给的定义拆解&#xff1a; ✴ Instead of …...