594. Longest Harmonious Subsequence

LeetCode easy original: C# #array #csharp #easy #hash-table #leetcode #math #search

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

Мы определяем гармоничный Array как Array, в котором разница между его максимальным и минимальным значением составляет ровно 1.

Дан Ganzzahl Array nums, return длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.

subsequence Arrayа - это последовательность, которую можно получить из Arrayа, удалив некоторые или никакие elementы, не изменяя порядок оставшихся elementов.

Beispiel:

Input: nums = [1,3,2,2,5,2,3,7]

Output: 5

Explanation: The longest harmonious subsequence is [3,2,2,2,3].

C# Lösung

zugeordnet/original

using System;
using System.Collections.Generic;
public class Solution {
    public int FindLHS(int[] nums) {
        var count = new Dictionary<int, int>();
        int res = 0;
        
        foreach (var num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
            if (count.ContainsKey(num + 1)) {
                res = Math.Max(res, count[num] + count[num + 1]);
            }
            if (count.ContainsKey(num - 1)) {
                res = Math.Max(res, count[num] + count[num - 1]);
            }
        }
        
        return res;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindLHS(vector<int>& nums) {
        var count = new unordered_map<int, int>();
        int res = 0;
        
        foreach (var num in nums) {
            if (count.count(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
            if (count.count(num + 1)) {
                res = max(res, count[num] + count[num + 1]);
            }
            if (count.count(num - 1)) {
                res = max(res, count[num] + count[num - 1]);
            }
        }
        
        return res;
    }
}

Java Lösung

zugeordnet/original

public class Solution {
    public int findLHS(int[] nums) {
        HashMap < Integer, Integer > map = new HashMap < > ();
        int res = 0;
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.containsKey(num + 1))
                res = Math.max(res, map.get(num) + map.get(num + 1));
            if (map.containsKey(num - 1))
                res = Math.max(res, map.get(num) + map.get(num - 1));
        }
        return res;
    }
}

JavaScript Lösung

zugeordnet/original

var findLHS = function(nums) {
    const count = new Map();
    let res = 0;
    
    for (let num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
        if (count.has(num + 1)) {
            res = Math.max(res, count.get(num) + count.get(num + 1));
        }
        if (count.has(num - 1)) {
            res = Math.max(res, count.get(num) + count.get(num - 1));
        }
    }
    
    return res;
};

Python Lösung

zugeordnet/original

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = {}
        res = 0
        
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if num + 1 in count:
                res = max(res, count[num] + count[num + 1])
            if num - 1 in count:
                res = max(res, count[num] + count[num - 1])
        
        return res

Go Lösung

zugeordnet/original

func findLHS(nums []int) int {
    count := make(map[int]int)
    res := 0
    
    for _, num := range nums {
        count[num]++
        if count[num+1] > 0 {
            res = max(res, count[num]+count[num+1])
        }
        if count[num-1] > 0 {
            res = max(res, count[num]+count[num-1])
        }
    }
    
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Пройдитесь по Arrayу, создавая словарь для подсчета частоты каждого elementа.

На каждой итерации проверьте, существуют ли в словаре elementы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.

return максимальную длину гармоничной подпоследовательности.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.