594. Longest Harmonious Subsequence

LeetCode easy оригинал: C# #array #csharp #easy #hash-table #leetcode #math #search

LeetCode Static

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

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

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

Пример:

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

Output: 5

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

C# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.