您现在的位置是:首页 >技术杂谈 >LeetCode 1218. Longest Arithmetic Subsequence of Given Difference【哈希表,动态规划】中等网站首页技术杂谈
LeetCode 1218. Longest Arithmetic Subsequence of Given Difference【哈希表,动态规划】中等
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
Given an integer array arr
and an integer difference
, return the length of the longest subsequence in arr
which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference
.
A subsequence is a sequence that can be derived from arr
by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
题意:给定一个数组 arr
和一个公差 difference
,在数组 arr
中寻找公差为 difference
的最长等差子数列的长度。
解法 哈希表+动态规划
我们定义状态为: d p [ i ] dp[i] dp[i] 为考虑前 i i i 个数(第 i i i 个数必选)时,得到的最长定差子序列长度。不失一般性考虑 d p [ i ] dp[i] dp[i] 该如何转移,分情况讨论:
- d p [ i ] dp[i] dp[i] 独立成为一个子序列,此时有 d p [ i ] = 1 dp[i]=1 dp[i]=1 ;
- a r r [ i ] arr[i] arr[i] 接在某一个数的后面,由于给定了差值 d i f f e r e n c e difference difference ,可直接算得上一位的值为 p r e v = a r r [ i ] − d i f f e r e n c e prev = arr[i] - difference prev=arr[i]−difference ,此时应找到为 p r e v prev prev 的 a r r [ j ] arr[j] arr[j] 的最新位置(下标最大,同时满足 j < i j<i j<i ),在此基础上加一即可,即有: d p [ i ] = d p [ r e c [ p r e v ] ] + 1 dp[i]=dp[rec[prev]]+1 dp[i]=dp[rec[prev]]+1
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n = arr.size(), ans = 0;
int dp[n];
unordered_map<int, int> rec;
for (int i = 0; i < n; ++i) {
dp[i] = 1;
int prev = arr[i] - difference;
if (rec.find(prev) != rec.end()) dp[i] = dp[rec[prev]] + 1;
ans = max(ans, dp[i]);
rec[arr[i]] = i;
}
return ans;
}
};
解法2 (哈希表)值域形式的动态规划
解法1中使用 d p [ i ] dp[i] dp[i] 记录以 n u m s [ i ] nums[i] nums[i] 结尾的最长定差子序列长度, r e c [ n u m s [ i ] ] rec[nums[i]] rec[nums[i]] 则记录 n u m s [ i ] nums[i] nums[i] 出现的下标。不妨将二者结合,设 d p [ n u m s [ i ] ] dp[nums[i]] dp[nums[i]] 为以 n u m s [ i ] nums[i] nums[i] 结尾的最长定差子序列长度,用哈希表作为 d p dp dp ,简化代码书写:
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n = arr.size(), ans = 0;
unordered_map<int, int> dp;
for (int i = 0; i < n; ++i) {
int prev = arr[i] - difference;
dp[arr[i]] = dp[prev] + 1;
ans = max(ans, dp[arr[i]]);
}
return ans;
}
};