[leetcode]: 594. Longest Harmonious Subsequence

悠悠 2022-06-15 07:07 120阅读 0赞

# 1.题目 #

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.  
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.  
定义和谐数组为数组内最大元素和最小元素的差刚好为1  
给一个整数数组，求最长和谐子序列的长度。  
Example 1:  
Input: \[1,3,2,2,5,2,3,7\]  
Output: 5  
Explanation: The longest harmonious subsequence is \[3,2,2,2,3\].

# 2.分析 #

对数组中每个元素计数，统计相邻大小元素的个数之和，返回最大的值。  
实现方法：  
c++ 借助map, map默认按key值大小升序排列  
python 借助Counter

# 3.代码 #

c++

int findLHS(vector<int>& nums) {
        map<int, int> counts;
        for (int n : nums)
            counts[n]++;
        int maxc = 0;
        int preV = 0;
        int preC = 0;
        for (auto p : counts) {
            if (preC&&preV + 1 == p.first)
                maxc = preC + p.second > maxc ? preC + p.second : maxc;
            preC = p.second;
            preV = p.first;
        }
        return maxc;
    }

python

def findLHS(self, nums):
        counts=collections.Counter(nums)
        return max([counts[i]+counts[i+1] for i in counts if counts[i+1]] or [0])

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode #4 Longest Common Subsequence

Question Given two strings `text1` and `text2`, return the length of their longest co

喜欢ヅ旅行/ 2023年08月17日 17:47/ 0 赞/ 107 阅读

相关 LeetCode - Medium - 1143. Longest Common Subsequence

Topic Dynamic Programming Description [https://leetcode.com/problems/longest-c

心已赠人/ 2022年10月22日 10:47/ 0 赞/ 123 阅读

相关 leetcode 594. Longest Harmonious Subsequence | 594. 最长和谐子序列

题目 [https://leetcode-cn.com/problems/longest-harmonious-subsequence/][https_leetcode-

向右看齐/ 2022年10月16日 15:23/ 0 赞/ 118 阅读

相关 LeetCode300——Longest Increasing Subsequence

LeetCode300——Longest Increasing Subsequence 题意：最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没

青旅半醒/ 2022年08月09日 19:30/ 0 赞/ 55 阅读

相关 leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

今天药忘吃喽~/ 2022年07月28日 01:20/ 0 赞/ 157 阅读

相关 [leetcode]: 594. Longest Harmonious Subsequence

1.题目 We define a harmonious array is an array where the difference between its maximu

悠悠/ 2022年06月15日 07:07/ 0 赞/ 121 阅读

相关 leetcode 594. Longest Harmonious Subsequence 最长和谐子序列 + Map遍历统计

We define a harmonious array is an array where the difference between its maximum value

电玩女神/ 2022年06月03日 04:45/ 0 赞/ 140 阅读

相关 leetcode 521. Longest Uncommon Subsequence I

Given a group of two strings, you need to find the longest uncommon subsequence of this

野性酷女/ 2022年04月10日 11:49/ 0 赞/ 144 阅读

相关 LeetCode-Longest Palindromic Subsequence

文章目录 Longest Palindromic Subsequence 题目描述思路分析 C++实现 Sc

太过爱你忘了你带给我的痛/ 2022年03月20日 04:46/ 0 赞/ 107 阅读

相关 lc594. Longest Harmonious Subsequence

1. Longest Harmonious Subsequence Easy 423 57 Favorite Share We define a harmouniou

男娘i/ 2022年01月12日 01:55/ 0 赞/ 104 阅读