594. 最長和諧子序列（Python）

題目

難度：★☆☆☆☆
類型：數(shù)組

和諧數(shù)組是指一個數(shù)組里元素的最大值和最小值之間的差別正好是1。

現(xiàn)在，給定一個整數(shù)數(shù)組，你需要在所有可能的子序列中找到最長的和諧子序列的長度。

示例

輸入: [1,3,2,2,5,2,3,7]
輸出: 5
原因: 最長的和諧數(shù)組是：[3,2,2,2,3].
說明: 輸入的數(shù)組長度最大不超過20,000.

解答

這道題有一個好處是不需要考慮數(shù)組中元素的先后順序，大大簡化了分析流程，我們可以把數(shù)組當(dāng)成一個集合處理。

統(tǒng)計數(shù)組中每個元素出現(xiàn)的次數(shù)，并存放在字典當(dāng)中，對于字典中每一條記錄，查看某一元素num+1后是否出現(xiàn)在字典中，如果也出現(xiàn)在字典中，則num與num+1可以組成和諧數(shù)組，計算所有和諧數(shù)組長度的最大值即可。

這里我們使用python中的Counter函數(shù)進(jìn)行元素的快速統(tǒng)計。

class Solution:
    def findLHS(self, nums):
        num_count, res = Counter(nums), 0                           # 統(tǒng)計列表中各個元素出現(xiàn)次數(shù)，并初始化結(jié)果為零
        for num, count in num_count.items():                        # 考察字典中每一條數(shù)字-次數(shù)對
            if num+1 in num_count.keys():                           # 如果數(shù)字+1也在字典中
                res = max(num_count[num]+num_count[num+1], res)     # 組成和諧數(shù)組并統(tǒng)計當(dāng)前最大長度
        return res

如有疑問或建議，歡迎評論區(qū)留言~

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容