1218. 最长定差子序列-北京尧图网络

题目描述给你一个整数数组arrarrarr和一个整数differencedifferencedifference请你找出并返回arrarrarr中最长等差子序列的长度该子序列中相邻元素之间的差等于differencedifferencedifference。子序列是指在不改变其余元素顺序的情况下通过删除一些元素或不删除任何元素而从arrarrarr派生出来的序列。示例 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]。算法原理子序列问题可用动态规划解决状态表示dp[i]dp[i]dp[i]表示以iii为结尾的所有等差子序列中最长等差子序列的长度状态转移方程由于题目给定了差值differencedifferencedifference所以在知道arr[i]aarr[i] aarr[i]a的情况下可以推出它前面的那个值等于a−differenceba - difference ba−differenceb。因此当获得值aaa时就去arrarrarr的[0,i−1][0, i-1][0,i−1]区间中找一个值bbb根据bbb的情况有两种状态[0,i−1][0, i-1][0,i−1]区间中不存在bbb此时aaa自己为一个等差子序列dp[i]1dp[i] 1dp[i]1[0,i−1][0, i-1][0,i−1]区间中存在bbb此时aaa要跟在以bbb为结尾的等差子序列之后假设0ji−10 j i-10ji−1以bbb为结尾的等差子序列它的长度为dp[j]dp[j]dp[j]以aaa为结尾的等差子序列它的长度就是dp[j]1dp[j] 1dp[j]1但是如果这样做就要去遍历[0,i−1][0, i-1][0,i−1]区间了效率太低我们进行优化由于差值固定为differencedifferencedifference当得到arr[i]aarr[i] aarr[i]a时在[0,i−1][0, i-1][0,i−1]区间内找任意一个bbb均可得到以aaa为结尾的最长等差子序列长度所以使用一个哈希表hashhashhash保存某等差子序列最后一个值和该等差子序列长度的映射关系当得到aaa时在hashhashhash中查找bbbbbb不存在就保存hash[a]1hash[a] 1hash[a]1。bbb存在就保存hash[a]hash[b]1hash[a] hash[b] 1hash[a]hash[b]1并更新结果初始化刚开始哈希表什么都没有i0i 0i0时会得到aarr[0]a arr[0]aarr[0]在哈希表中查找[0,−1][0, -1][0,−1]区间上的值bbb肯定是找不到的此时会填入arr[0]0arr[0] 0arr[0]0所以哈希表不需要初始化填表顺序从左到右遍历arrarrarr填充哈希表返回值哈希表中的最大值代码classSolution{public:intlongestSubsequence(vectorintarr,intdifference){unordered_mapint,inthash;// 某等差子序列最后一个值 - 该等差子序列的长度intans1;for(inti0;iarr.size();i){intaarr[i];intba-difference;if(hash.find(b)!hash.end())// 之前有以 b 为结尾的子序列{intlenhash[b];hash[a]len1;// 在以 b 为结尾的子序列之后带上 aansmax(ans,len1);}else// 之前没有以 b 为结尾的子序列{hash[a]1;}}returnans;}};

1218. 最长定差子序列

相关推荐

金融风控场景下Qwen-7B大模型微调实战指南

视频本地化混合翻译方案：AI与人工的黄金比例

如何为Nodejs后端服务配置Taotoken统一大模型调用接口

更多资讯

孟津电工证复审怎么搞？实操考试心里没底怕挂科？全国通用证书你必须知道的事

国际电工证有几种类型在哪考？特种作业证上岗必备全解析

河南特种作业证操作证过期了怎么处理？全国通用证书复审全攻略

低压电工证啥时候报名千万别踩坑

河南特种作业证操作证别怕考不过白交培训费?电子证书帮你稳过

深圳哪里有办理电工证在哪考别再踩坑了

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？