阿里巴巴国际站运营培训,专业网站是指什么,惠东网站设计,天津塘沽爆炸目录
编辑
一#xff0c;最长定差子序列
1.题目
2#xff0c;题目接口 3#xff0c;解题思路及其代码 一#xff0c;最长定差子序列
1.题目 给你一个整数数组 arr 和一个整数 difference#xff0c;请你找出并返回 arr 中最长等差子序列的长度#xff0c;该子序列…
目录
编辑
一最长定差子序列
1.题目
2题目接口 3解题思路及其代码 一最长定差子序列
1.题目 给你一个整数数组 arr 和一个整数 difference请你找出并返回 arr 中最长等差子序列的长度该子序列中相邻元素之间的差等于 difference 。 子序列 是指在不改变其余元素顺序的情况下通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。 示例 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]。 2题目接口
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {}
}; 3解题思路及其代码 1.状态转移方程: 这道题要我们求的是最长定差子序列问题不再是最长子序列。这里的关键便是定差也就是说在我们知道差以后我们便可以知道第2个数的值。我们的dp[i] 表示为以i位置为结尾的最长等差子序列。 2.初始化 当我们的每个nums[i]单独构成一个子序列时长度为1所以我们初始化时边初始化为1即可。 在明确好这些后便可以写出如下代码 class Solution {
public:int longestSubsequence(vectorint arr, int difference) {int n arr.size();vectorintdp(n,1);int Maxlenth 1;for(int i 0;in;i){int num arr[i]difference;//找定差for( int j i1;jn;j){if(arr[j] num){dp[j] dp[i]1;}}Maxlenth max(Maxlenth,dp[i]);//每次都要更新一下最大值}return Maxlenth;}
}; 但是这个代码是过不了的。因为这个代码的时间复杂度为O(n^2)。所以我们要对这个代码做一些优化。优化的秘诀便是hash表unordered_map。改进思路如下 1.先创建一个hash表。 2.将arr里面的所有元素和元素的对应下标放到hash表中构成映射arr[i]作key下标作value。 现在改进代码如下 class Solution {
public:int longestSubsequence(vectorint arr, int difference) {unordered_mapint,int hash;//在hash表里做dpint n arr.size();int Max 1;hash[arr[0]] 1;for(int i 1;in;i){hash[arr[i]] hash[arr[i]-difference]1;//如果arr[i]-difference那也会访问最后一个arr[i]-difference的值。因为hash的底层插入是头插Max max(Max,hash[arr[i]]);}return Max;}
}; 提交过啦
