leetcode 5214 最长定差子序列

缘起

leetcode双周赛的题目, 群里讨论的热火朝天的~ 我瞄了一眼, 凑凑热闹哈~ leetcode 5214 最长定差子序列

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。

示例 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]。

提示：
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

此题比较简单, 和LCS问题类似的DP手段. （其实比LCS还简单） 本题比较水的原因是公差是定的, 和【1】不同.

1
2
dp[i]是]a[i]为结尾的最长定差子序列长度. 则
dp[i] = dp[a[i]-d对应的最大索引,当然这个索引必须<i]+1

所以问题的关键在于你怎么在O(1)时间就知道a[i]-d对应的最大索引是哪一个. 很简单, 只需要开一个int数组来维护某个值（[-1e4, 1e4]）出现的最晚时间戳就行了. 当然这个过程需要随着扫描的进行而同步进行.

什么? 为什么要取最晚时间? 因为你要求最长序列啊~ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
	int longestSubsequence(vector<int>& arr, int difference) {
		memset(t, -1, sizeof(t));
		t[arr[0]+10000] = 0;
		int n = arr.size(), ans = 1;
		fill(dp, dp+n, 1);
		for (int i = 1, prev; i<n; i++)
		{
			prev = arr[i]-difference; // 上一个数
			if (prev<-10000 || prev>10000) // 如果超过范围, 那肯定不可能出现过
			{
				t[arr[i]+10000] = i; // 更新完时间戳就走
				continue;
			}
			if (~t[prev+10000]) // 如果之前出现过
			{
				dp[i] = dp[t[prev+10000]]+1;
				ans= max(ans, dp[i]);
			}
			t[arr[i]+10000] = i; // 更新时间戳
		}
		return ans;
	}

private:
	int t[20005]; // t[i]表示i-10000出现的最晚时间戳
	int dp[100005]; // dp[i]表示以a[i]结尾的最长定差子序列元素个数
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
100 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗 :
16.5 MB
, 在所有 C++ 提交中击败了
100.00%
的用户

双百~ 四不四很吊，hiahiahia~

参考

【1】https://yfsyfs.github.io/2019/10/07/leetcode-1027-%E6%9C%80%E9%95%BF%E7%AD%89%E5%B7%AE%E5%AD%90%E5%BA%8F%E5%88%97/