354. Russian Doll Envelopes

LeetCode hard оригинал: C# #array #csharp #dynamic-programming #hard #leetcode #search #sort

LeetCode Static

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.

Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]

Output: 3

Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

C# решение

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

using System;
using System.Collections.Generic;
public class Solution {
    public int LengthOfLIS(int[] nums) {
        var dp = new List<int>();
        foreach (var num in nums) {
            int i = dp.BinarySearch(num);
            if (i < 0) i = ~i;
            if (i < dp.Count) dp[i] = num;
            else dp.Add(num);
        }
        return dp.Count;
    }
    public int MaxEnvelopes(int[][] envelopes) {
        Array.Sort(envelopes, (arr1, arr2) => arr1[0] == arr2[0] ? arr2[1].CompareTo(arr1[1]) : arr1[0].CompareTo(arr2[0]));
        var secondDim = new int[envelopes.Length];
        for (int i = 0; i < envelopes.Length; i++) {
            secondDim[i] = envelopes[i][1];
        }
        return LengthOfLIS(secondDim);
    }
}

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 LengthOfLIS(vector<int>& nums) {
        var dp = new List<int>();
        foreach (var num in nums) {
            int i = dp.BinarySearch(num);
            if (i < 0) i = ~i;
            if (i < dp.size()) dp[i] = num;
            else dp.push_back(num);
        }
        return dp.size();
    }
    public int MaxEnvelopes(int[][] envelopes) {
        Array.Sort(envelopes, (arr1, arr2) => arr1[0] == arr2[0] ? arr2[1].CompareTo(arr1[1]) : arr1[0].CompareTo(arr2[0]));
        var secondDim = new int[envelopes.size()];
        for (int i = 0; i < envelopes.size(); i++) {
            secondDim[i] = envelopes[i][1];
        }
        return LengthOfLIS(secondDim);
    }
}

Java решение

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

class Solution {

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }

    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0]) {
                    return arr2[1] - arr1[1];
                } else {
                    return arr1[0] - arr2[0];
                }
            }
        });
        int[] secondDim = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; ++i) secondDim[i] = envelopes[i][1];
        return lengthOfLIS(secondDim);
    }
}

JavaScript решение

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

class Solution {
    lengthOfLIS(nums) {
        const dp = [];
        for (const num of nums) {
            let i = this.binarySearch(dp, num);
            if (i < 0) i = -(i + 1);
            if (i < dp.length) dp[i] = num;
            else dp.push(num);
        }
        return dp.length;
    }

    binarySearch(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left < arr.length && arr[left] === target ? left : -(left + 1);
    }

    maxEnvelopes(envelopes) {
        envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
        const secondDim = envelopes.map(envelope => envelope[1]);
        return this.lengthOfLIS(secondDim);
    }
}

Python решение

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

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []
        for num in nums:
            i = bisect_left(dp, num)
            if i < len(dp):
                dp[i] = num
            else:
                dp.append(num)
        return len(dp)

    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        second_dim = [e[1] for e in envelopes]
        return self.lengthOfLIS(second_dim)

Go решение

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

import (
    "sort"
)

func lengthOfLIS(nums []int) int {
    dp := []int{}
    for _, num := range nums {
        i := sort.Search(len(dp), func(i int) bool { return dp[i] >= num })
        if i < len(dp) {
            dp[i] = num
        } else {
            dp = append(dp, num)
        }
    }
    return len(dp)
}

func maxEnvelopes(envelopes [][]int) int {
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    secondDim := make([]int, len(envelopes))
    for i, envelope := range envelopes {
        secondDim[i] = envelope[1]
    }
    return lengthOfLIS(secondDim)
}

Algorithm

Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

Извлеките вторую размерность (высоты) отсортированного массива.

Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎

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

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

Все вакансии

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