ДЕЛО 013: Вы можете просто разобрать его?
Подпоследовательности всегда были концепцией, которая меня немного сбивала с толку. Не знаю почему. Но, как и в любом другом случае, чем больше времени я трачу на работу с подпоследовательностями, тем медленнее я учусь и привыкаю к ним.
В любом случае проблема, которую мы собираемся решить сегодня, на первый взгляд может показаться сложной и станет хорошим испытанием для наших навыков критического мышления (надеюсь).
Итак, приступим к решению.
ЭТА ПРОБЛЕМА
Вот ссылка на проблему на LeetCode
Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence. If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.
ОГРАНИЧЕНИЯ
Предоставленные ограничения на самом деле не дают какой-либо важной информации, но, как всегда, давайте рассмотрим каждое из них и посмотрим, сможем ли мы найти какие-либо подсказки к решению:
1 <= nums.length <= 500
Первое ограничение дает нам диапазон чисел, который мы должны ожидать в массиве nums. С нижним пределом 1 <= nums.length нам не нужно беспокоиться о том, что nums будет пустым или не будет содержать никаких элементов. Верхний предел nums.length <= 500 также не дает нам никакой конкретной информации, кроме наибольшего количества элементов, которые нам нужно будет перебрать.
1 <= nums[i] <= 100
Второе ограничение - это диапазон элементов в nums. Мы узнаем, что нам не придется иметь дело с отрицательными числами или если элемент в nums равен 0, так как нижний предел элементов в nums равен 1 <= nums[i]. С верхним пределом nums[i] <= 100 нам также не нужно беспокоиться о каких-либо действительно больших числах. Условно говоря, верхний предел в 100 довольно мал.
ИСПЫТАНИЯ
ПРОРЫВ
Эта проблема состоит из множества мелких деталей, которые, как говорилось ранее, могут сделать minSubsequences сложным. Но, как обычно, если мы рассмотрим каждую предоставленную нам информацию, я думаю, мы сможем упростить и организовать вещи таким образом, чтобы все было легче понять:
Given the array nums
Наш аргумент для minSubsequences всегда будет массивом, элементы которого всегда будут целыми числами. Достаточно просто.
obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.
Здесь все становится немного сложнее.
Вот наша задача. Нам нужно найти группу чисел в nums, где, если мы сложим все числа в группе вместе, сумма будет больше, чем остальные числа в nums, которые не включены в группу.
Первое, что это говорит мне, это то, что нам нужно будет сохранить текущую сумму подпоследовательности, которую мы строим, и вычесть эту текущую сумму из общей суммы элементов в nums.
If there are multiple solutions, return the subsequence with minimum size
У нас могут быть сценарии, в которых nums будет иметь несколько подпоследовательностей разного размера. Это может означать, что нам придется отслеживать каждую найденную подпоследовательность и помещать каждую подпоследовательность в массив для их сравнения. То есть, если мы даже хотим отслеживать каждую подпоследовательность.
...if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements.
Это дает мне бешеный ключ к разгадке. Мы можем избежать отслеживания каждой найденной подпоследовательности, если отсортируем nums в неубывающем порядке (или от наименьшего к наибольшему). Затем мы можем пройти по отсортированному nums от последнего элемента к первому (или в обратном направлении).
Это позволит нам найти подпоследовательность с минимальным размером и максимальной общей суммой любой подпоследовательности в числах.
Если мы посмотрим, например, на Контрольный пример №1:
[4,3,10,9,8]
и отсортируйте Test Case # 1 в неубывающем порядке:
[3,4,8,9,10]
Мы можем перебирать nums, начиная с последнего элемента 10, и работать в обратном направлении:
1st iteration: subsequence : [10] subsequence sum: 10 nums sum: 34 elements in nums not included in subsequence: [3,4,8,9] nums sum excluding subsequence sum: 24
~
2nd iteration: subsequence : [10, 9] subsequence sum: 19 nums sum: 34 elements in nums not included in subsequence: [3,4,8] nums sum excluding subsequence sum: 15
На второй итерации мы уже нашли подпоследовательность, сумма которой больше суммы остальных элементов в nums: [10, 9]
Поскольку мы уже отсортировали nums в порядке неубывания, [10,9] - это подпоследовательность, длина которой равна минимально возможному размеру всех возможных подпоследовательностей, когда сумма подпоследовательности строго больше суммы не включенных элементов. Мы знаем это, потому что любая другая подпоследовательность должна иметь как минимум 2 элемента.
И поскольку отсортированный массив nums сортируется в порядке неубывания, [10,9] также является наименьшей подпоследовательностью, сумма которой является максимальной суммой всех возможных подпоследовательностей, когда сумма подпоследовательности строго больше суммы не включенных элементов.
Все другие возможные подпоследовательности должны иметь как минимум 2 элемента, и даже если бы они были, их сумма не может быть больше, чем [10,9], поскольку [10,9] - два самых больших числа в nums.
Я думаю, мы здесь кое-что находим.
A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.
Я проигнорирую эту информацию. Это может быть полезно для альтернативного решения, но остается нерелевантным для потенциального решения, которое я начал обрисовывать выше. Отметьте это как первый раз, когда я передаю часть предоставленной нам информации.
Note that the solution with the given constraints is guaranteed to be unique.
Это говорит мне, что мы всегда будем возвращать только одну подпоследовательность. Каждый экземпляр nums будет иметь только 1 ответ. Это помогает усилить то, что я объяснял ранее, поскольку приведенное выше решение с сортировкой и итерацией через сортировку nums назад будет строить только одну подпоследовательность.
Also return the answer sorted in non-increasing order.
Вот кикер. Если мы отсортируем nums в неубывающем порядке, а затем переберем отсортированный nums от последнего элемента к первому (или в обратном направлении), мы сможем построить нашу подпоследовательность минимального размера и максимальной суммы, поместив каждое число в пустой массив. Это естественным образом отсортирует их в порядке невозрастания.
ПОДОЗРЕВАЕМЫЙ
Порядок, в котором мы выполняем различные операции на каждой итерации до nums, будет иметь значение. Что может сделать minSubsequences более запутанным, так это то, что объяснение проблемы дает нам много информации, которая не соответствует порядку относительно того, как нам нужно будет выполнять каждую часть.
В связи с этим я собираюсь обрисовать в общих чертах каждую вещь, которую мы должны сделать, когда мы повторяем nums в том порядке, в котором мы должны это делать, и дам некоторые объяснения каждой части. Затем мы можем пройти через некоторый псевдокод, чтобы лучше понять, как должно работать наше решение:
1.) Find the total sum of nums, store it as a variable named sum
Во-первых, нам нужна отправная точка. Нам нужно найти общее sum из nums, прежде чем делать что-либо еще. Поскольку нам нужно вычесть сумму создаваемой подпоследовательности из общего sum, нам нужно сохранить sum как переменную.
Есть несколько разных способов найти общую сумму nums, прежде чем мы сделаем что-нибудь еще, но я собираюсь использовать .reduce().
2.) Create 2 extra variables: sub (an empty array), and subSum (an integer)
Нам нужен пустой массив для построения нашей подпоследовательности, и мы можем назвать его sub. Мы также вернем sub в конце нашего решения.
По мере того, как мы перебираем отсортированный nums, мы захотим протолкнуть элементы из nums в sub, который будет инициализирован как пустой массив.
Нам также нужна другая переменная с именем subSum, чтобы отслеживать сумму подпоследовательности, которую мы встраиваем в sub. На каждой итерации мы будем помещать nums[i] (или каждый элемент) в sub и добавлять nums[i] к subSum.
3.) Sort nums in non-decreasing order
Нам нужно отсортировать элементы в nums от наименьшего к наибольшему. Нам не нужно сохранять это в переменной, поскольку .sort() изменит массив, для которого он вызывается.
4.) Iterate through nums (which is now sorted) backwards
Чтобы найти подпоследовательность минимального размера и суммирования с максимальной суммой, мы можем выполнить итерацию по отсортированному nums назад, начиная с последнего элемента (который теперь является наибольшим числом) до первого элемента (который теперь является наименьшим числом) в массиве.
5.) On each iteration, check to see if sum is greater than or equal to subSum
На каждой итерации мы будем проверять, есть ли sum >= subSum. Если это не так, мы должны продолжить поиск подпоследовательности nums, сумма которой больше, чем сумма не включенных элементов в nums.
Это означает, что нам придется сделать кучу вещей:
5a.) Add nums[i] to subSum
Это увеличит subSum в зависимости от каждого элемента в отсортированном nums. На каждой итерации, если subSum меньше sub, мы хотим протолкнуть nums[i] в sub, пока не найдем набор чисел, сумма которых больше суммы не включенных элементов в nums.
5b.) Subract nums[i] from Sum
Хотя subSum меньше sum, мы также хотим вычесть nums[i] из sum. Это позволит отслеживать общую сумму чисел, которые мы продолжаем исключать из строящейся подпоследовательности.
5c.) Push nums[i] into sub
Это строит нашу подпоследовательность. Мы хотим продолжить строительство sub, пока subSum меньше sum. Когда subSum больше sum, мы нашли подпоследовательность, сумма элементов которой больше суммы не включенных элементов.
6.) Break out of the iteration once sum is less than subSum
Как только мы обнаружили, что нашли подпоследовательность, сумма элементов которой больше суммы не включенных элементов, у нас больше нет необходимости продолжать итерацию по отсортированному nums. Это означает, что мы можем выйти из цикла for.
7.) Return sub
Поскольку мы отсортировали nums в неубывающем порядке, и поскольку мы выполняем итерацию по отсортированному nums в обратном порядке, как только мы нашли подпоследовательность, сумма элементов которой больше суммы не включенных элементов, мы также нашли минимальный размер / максимально суммированное подпосущество.
sub будет представлять эту подпоследовательность, поэтому мы можем ее вернуть.
ПЛАН
Прежде чем мы что-либо помещаем в код, давайте напишем некоторый псевдокод, чтобы попытаться визуализировать наше решение немного лучше:
КОД
Хорошо, давайте попробуем применить наше решение на практике и посмотрим, работает ли оно:
Во-первых, давайте начнем с определения трех переменных, которые нам понадобятся: sum, sub и subSum:
Давайте также отсортируем nums:
Затем давайте настроим цикл for, который будет повторять nums в обратном порядке:
Затем мы можем добавить оператор if, который проверяет, больше ли sum или равно subSum. Если это не так, прервите итерацию:
Затем мы можем добавить наши три операции: добавление nums[i] к subSum, вычитание nums[i] из sum и нажатие nums[i] на sub:
Наконец, мы можем добавить возвращаемое значение sub:
Посмотрим, работает ли это:
Отлично.
ЗАКЛЮЧИТЕЛЬНОЕ РЕШЕНИЕ
Давайте в последний раз взглянем на наше решение без комментариев и очистим наш синтаксис:
ЗАДАНИЕ ВЫПОЛНЕНО
Мне очень понравилась эта задача, потому что она заставила меня выйти из зоны комфорта. Я чувствовал, что это решение было одним из наиболее эффективных решений, о которых я писал, и определенно подтолкнуло меня к работе над визуализацией решения, прежде чем писать его.
Я определенно понимаю, что мои решения не будут лучшими или наиболее эффективными, но в любом случае я надеюсь, что они помогут вам или кому-то еще найти способ решить проблему, с которой вы столкнетесь на этом пути, который мы называем JavaScript.
В любом случае, я надеюсь, что вы получили некоторую полезную информацию, и пусть все ваши функции вернут истину, а все ваши запросы будут отвечать 200.
Оставайся в безопасности ... оставайся здоровым ... и продолжай вести добрый бой.
