数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 中最长的和谐子序列
假如我们有一个整数数组；我们必须在所有可能子序列中找出它最长的和谐子序列的长度。众所周知，和谐序列数组是一个数组，其中最大值和最小值之间的差正好为 1。
所以，如果输入像 [1,3,2,2,5,2,3,7]，那么输出将是 5，因为最长的和谐子序列是 [4,3,3,3,4]。
为了解决这个问题，我们将遵循以下步骤 -
定义一个映射 m
对于 nums 中的 n -
(使 m[n] 增加 1)
对于 m 中的键值对 (k,v) -
it := m 中 (k+1) 的位置
如果 'it' 在 m 中，则 -
max_:= max_ 和它最大的一个
返回 max_
示例
让我们看看以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findLHS(vector<int>& nums) {
unordered_map<int, int> m;
for (const int n : nums)
++m[n];
int max_{ 0 };
for (const auto & [ k, v ] : m) {
auto it = m.find(k + 1);
if (it != m.end())
max_ = max(max_, v + it->second);
}
return max_;
}
};
main(){
Solution ob;
vector<int> v = {2,4,3,3,6,3,4,8};
cout << (ob.findLHS(v));
}输入
{2,4,3,3,6,3,4,8}输出
5
更新时间：2020 年 6 月 11 日
408 次浏览
广告