专业网站设计 软件,百度网站推广服务商,宁波网红打卡地,h5页面有哪些1.题目解析 题目来源#xff1a;1218.最长定差子序列——力扣 测试用例 2.算法原理 1.状态表示
本题可以看作是寻找一个等差序列#xff0c;并且公差给出#xff0c;这里并不是普通的使用一个dp表#xff0c;而是将arr与dp表同时存储于一个哈希表#xff0c;arr[i]映射dp… 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(vectorint arr, int difference) {int n arr.size();unordered_mapint,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;}
};
