資料結構
網路
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 次瀏覽
廣告