Решение: русские конверты куклов

LeetCode Solutions (161 серия деталей)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Задача leetcode #354 (Hard): российские конверты куклов

Описание:

( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++

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

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

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

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

Примеры:

Ограничения:

• 1. длиной
• конверты [i].
• 1, Привет^4

Идея:

( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++

Наивный подход здесь заключается в том, чтобы попробовать каждую перестановку нашего массива конверта ( e ), но это будет Сложность времени из НА!) что, честно говоря, непостижимое число, когда N подходит к 5000 Анкет

Поскольку наивный подход будет включать повторение многих из тех же отдельных сравнений снова и снова, мы можем быстро увидеть, что динамическое программирование ( dp ) Решение было бы полезным.

Однако для того, чтобы решение DP было эффективным, нам нужно было бы найти способ прогрессировать из самой простой подборе и построить оттуда для каждой последовательной более сложной подборе. Лучший способ сделать это – сортировать Е – первым по ширина ( e [i] [0] ), а затем по высота ( e [i] [1] ).

Затем мы могли бы начать с самого маленького конверта и пройти путь вверх, сохраняя в нашем массиве DP ( dp ) результат того, сколько меньших конвертов можно вписать в соответствующий конверт. Таким образом, мы могли бы упростить каждую итерацию, чтобы проверить, какие из записей в DP Соответствует более мелким конвертам является самым большим. Это снизит сложность времени до O (n^2) , что является определенным улучшением.

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

Если мы уже отсортировали E В первую очередь по ширине мы должны быть в состоянии рассмотреть соответствующий массив только высоты и понять, что решение будет определено как Самое длинное увеличение подпоследовательности того, что.

Единственная трудность была бы для последовательных конвертов с то же самое отсортированная ширина. Чтобы избежать этого, мы можем просто убедиться, что наша функция сортировки сортирует высоту в порядке убывания, чтобы первый конверт, столкнутый для любой указанной ширины, был самым большим.

В конце самого длинного увеличения алгоритма последующей последовательности длины DP равен длине последующей. Из -за функции сорта и двоичных поисков, необходимых для алгоритма, временная сложность теперь сокращается до O (n log n) Анкет

Реализация:

Python имеет встроенную бинарную функцию поиска, bisect () Анкет

Java также имеет встроенную бинарную функцию поиска ( Arrays.binarySearch () ), но для того, чтобы использовать более производительный int [] а не Список , нам нужно указать максимальную длину для DP и затем следите за текущим индексом самой длинной последующей последовательности отдельно в Ответ .

C ++ имеет встроенную бинарную функцию поиска, lower_bound () Анкет

Код JavaScript:

( Прыгните к : Описание задачи Идея решения

var maxEnvelopes = function(E) {
    E.sort((a,b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])
    let len = E.length, dp = []
    for (let i = 0; i < len; i++) {
        let height = E[i][1], left = 0, right = dp.length   
        while (left < right) {
            let mid = (left + right) >> 1
            if (dp[mid] < height) left = mid + 1
            else right = mid
        }
        dp[left] = height
    }
    return dp.length
};

Код Python:

( Прыгните к : Описание задачи Идея решения

class Solution:
    def maxEnvelopes(self, E: List[List[int]]) -> int:
        E.sort(key=lambda x: (x[0], -x[1]))
        dp = []
        for _,height in E:
            left = bisect_left(dp, height)
            if left == len(dp): dp.append(height)
            else: dp[left] = height
        return len(dp)

Код Java:

( Прыгните к : Описание задачи Идея решения

class Solution {
    public int maxEnvelopes(int[][] E) {
        Arrays.sort(E, (a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] dp = new int[E.length];
        int ans = 0;
        for (int[] env : E) {
            int height = env[1];
            int left = Arrays.binarySearch(dp, 0, ans, height);
            if (left < 0) left = -left - 1;
            if (left == ans) ans++;
            dp[left] = height;
        }
        return ans;
    }
}

C ++ Код:

( Прыгните к : Описание задачи Идея решения

class Solution {
public:
    int maxEnvelopes(vector>& E) {
        sort(E.begin(), E.end(), [](vector& a, vector& b) 
             -> bool {return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];});
        vector dp;
        for (auto& env : E) {
            int height = env[1];
            int left = lower_bound(dp.begin(), dp.end(), height) - dp.begin();
            if (left == dp.size()) dp.push_back(height);
            dp[left] = height;
        }
        return dp.size();
    }
};

LeetCode Solutions (161 серия деталей)

Оригинал: “https://dev.to/seanpgallivan/solution-russian-doll-envelopes-459i”