力扣刷题学习1218. 最长定差子序列(C++)
2021/11/5 17:11:23
本文主要是介绍力扣刷题学习1218. 最长定差子序列(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
测试用例
示例一:
输入:arr = [1,2,3,4], difference = 1
输出:4
解释:最长的等差子序列是 [1,2,3,4]。
示例 二:
输入:arr = [1,3,5,7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。
示例三:
输入:arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出:4
解释:最长的等差子序列是 [7,5,3,1]。
提示:
- 1 <= arr.length <= 105
- -104 <= arr[i], difference <= 104
解答
此处用到动态规划的思路,首先从头开始遍历,
对于每个arr中的数,查找arr[i]-d的值存不存在,如果不存在,记录d[arr[i]]=1,若存在则记录d[arr[i]]=d[arr[i]-d]+1;如此遍历循环完整个arr[]数组,随后取max[d[arr[i]]]即为题解。
class Solution { public: int longestSubsequence(vector<int> &arr, int difference) { int ans = 0; unordered_map<int, int> dp; for (int v: arr) { dp[v] = dp[v - difference] + 1; ans = max(ans, dp[v]); } return ans; } };
复杂度分析
- 时间复杂度:O(n)O(n),其中 nn 是数组 \textit{arr}arr 的长度。
- 空间复杂度:O(n)O(n)。哈希表需要 O(n)O(n) 的空间。
这篇关于力扣刷题学习1218. 最长定差子序列(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08测试人员在 Scrum 中的角色是什么?
- 2024-07-07Dify + TiDB Vector,快速构建你的AI Agent
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享