leetcode 1027 最长等差子序列

缘起

假期快完了, 所以抓紧时间浪费生命~ leetcode 1027 最长等差子序列

分析

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
给定一个整数数组 A，返回 A 中最长等差子序列的长度。

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= 
A.length-1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列B是等差的。

示例 1：

输入：[3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。
示例 2：

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：

输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：
2 <= A.length <= 2000
0 <= A[i] <= 10000

既然A的长度仅仅到2000, 说明可以DP O(n^2)来搞啦~

本题关键是公差不知道是多少. 这和【1】不同. 但是没关系啊~ n小啊~ 可以各种暴力，各种瞎搞~

令 dp[i][j] （0<=j<i<n）是a[i]为结尾，a[i]前一个元素是a[j]的等差数列的元素个数. 类似于LCS问题中的DP手法.

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
class Solution {
public:
	int longestArithSeqLength(vector<int>& A) {
		int n = A.size(), ans = 0;
		for (int i = 1;i<n; i++)
		{
			memset(v,0,sizeof(v));
			for (int j = i-1,d; ~j; j--)
			{
				d = A[i]-A[j]; 
				if (v[d+10000]) // 因为公差的范围是[-10000,10000], 所以v开了20000,然后这里+10000,之所以该公差已经出现过了就不必再考虑了是因为这里的j是反向的. 因为你要求最长啊~
				{
					continue;
				}
				v[d+10000] = true;
				bb[P(i,d)] = bb[P(j,d)]+1;
				ans = max(ans, bb[P(i,d)]); // 更新答案
			}
		}
		return ++ans;
	}
private:
	bool v[20005];
	typedef pair<int, int> P;
	map<P, int> bb;
};

ac情况(水过水过~)

分钟前 通过 5960 ms 373.3 MB Cpp

参考

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