Еженедельный конкурс Leetcode 188 — Решения
На этой неделе я занял 194 место, ~55 минут в конкурсе 188. Мой последний семестр младшего года подходит к концу, поэтому я, вероятно, буду чаще создавать еженедельные решения для каждого конкурса Leetcode.
В этом конкурсе было несколько забавных задач, в том числе математическая задача, задача с деревом и сложная (очевидно, интервью Google из Японии? удивительно сложная для вопроса Google, IMO) задача DP. Я сделаю руководство среднего уровня (предполагается средний уровень знаний стиля Leetcode или стиля конкурентного программирования) для первых 3 простых вопросов и действительно проведу вас через последнюю сложную проблему, которую большинство людей не могут решить.
Задача A: 1441. Построить массив с помощью операций со стеком (просто)
Проблема:
https://leetcode.com/contest/weekly-contest-188/problems/build-an-array-with-stack-operations/
Дан массив target и целое число n. На каждой итерации вы будете считывать число из list = {1,2,3..., n}.
Создайте массив target, используя следующие операции:
Push: прочитайте новый элемент с начала list и поместите его. в массиве.
Извлечь: удалить последний элемент массива
Если целевой массив уже построен, прекратить чтение дополнительных элементов.
Вам гарантируется, что целевой массив строго увеличивается и содержит только числа от 1 до n включительно.
Возвращает операции для построения целевого массива. Вы гарантируете, что ответ уникален.
Решение:
Перебор O(N) времени + пробел:
Предположим, что нам дан целевой массив, оканчивающийся цифрой j. Сначала мы бросаем числа целевого массива в набор и итерируем с числа 1,2,3…j. Для каждого числа i от 1 до j, которого нет в наборе, мы будем писать push + pop. В противном случае напишите push.
Задача B: 1442. Подсчитайте триплеты, которые могут образовывать два массива с одинаковым исключающим ИЛИ (средний)
Проблема:
Дан массив целых чисел arr.
Мы хотим выбрать три индекса i, j и k, где (0 <= i < j <= k < arr.length).
Определим a и b следующим образом:
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
Обратите внимание, что ^ обозначает операцию побитовое исключающее ИЛИ.
Возвращает количество троек (i, j и k) Где a == b.
Решение:
Перебор с префиксом O(N³) Time + O(1) пробел:
В соревнованиях всегда важно смотреть на размер ввода. Обычно, если размер входных данных составляет сотню или тысячу, то грубой силы или слегка оптимизированной грубой силы достаточно, чтобы быть принятым. ,j,k, и проверка того, что XOR между i и j-1 и XOR между j и k равны. Нам нужно отслеживать префикс XOR, чтобы сделать его O(N³) вместо O(N⁴). В противном случае вы будете превышены сроки (TLE).
Оптимизированное решение: O(N²) времени + O(N) места:
Мы можем посмотреть на эту проблему по-другому. Обратите внимание, что задача запрашивает подмассив [i,j-1] и подмассив [j,k], чтобы эти два XOR были равны. Что ж, равенство двух XOR означает, что если вы XOR этих двух, вы получите 0. На самом деле, альтернативный взгляд на эту проблему заключается в том, что мы ищем подмассив [i,k], такой что XOR этого подмассива равен 0. Как только мы сделать это, мы можем просто подсчитать, на сколько j мы можем разделить подмассив [i,k] (это просто ki-1, потому что его длина -1). Если вам интересно, будет ли разделение любого j между i,k по-прежнему выполнять условие, что XOR между i и j-1 и XOR между j и k равны, тогда будьте уверены, они всегда будут равны. Вы можете попробовать это сами!
Давайте построим решение сейчас. Сначала мы можем построить префиксный массив XOR за время O(N). Затем мы будем использовать этот массив XOR префикса и проверять каждую пару значений префикса за время O (N²), чтобы увидеть, равны ли какие-либо два. Если да, то подсчитайте j в нем за время O(1).
Наилучшее оптимизированное решение: O(N) Time + O(N) space:
Если вы знаете или слышали о хешировании, то, вероятно, сможете разобраться с этим. Взгляните на задачу Subarray Sum Equals K. По сути, это тот же метод, который используется здесь. Мы просто сохраняем хэш-карту префиксных XOR, но на этот раз нам также нужна хэш-карта соответствующей суммы инцидентов. Это требует некоторой математики, но вы можете проверить это для деталей: https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/discuss/623747/JavaC %2B%2BPython-One-Pass-O(N4)-to-O(N)
Задача C: 1443. Минимальное время, чтобы собрать все яблоки с дерева (среднее)
Проблема
Дано неориентированное дерево, состоящее из n вершин, пронумерованных от 0 до n-1, в вершинах которого есть яблоки. Вы тратите 1 секунду, чтобы перешагнуть край дерева. Возвращает минимальное время в секундах, которое вам нужно потратить, чтобы собрать все яблоки в дереве, начиная с вершины 0 и возвращаясь к этой вершине.
Ребра неориентированного дерева заданы в массиве edges, где edges[i] = [fromi, toi] означает, что существует ребро, соединяющее вершины fromi и toi. Кроме того, имеется логический массив hasApple, где hasApple[i] = true означает, что в вершине i есть яблоко, иначе яблока в ней нет.
Решение:
2 DFS — O(N) Time + O(N) Space
Мое решение интуитивно понятно. Обратите внимание, что нам нужно посетить узел тогда и только тогда, когда в этом узле есть яблоко или в его потомке есть яблоко. Это означает, что нам нужно иметь дополнительную информацию, которая не дана: есть ли у узла яблоки в его потомках. Мы можем хранить эти данные в массиве с именем hasDescendantApples[]. Мы получим эту информацию в O(N) пространстве и времени, используя поиск в глубину снизу вверх. По сути, сначала мы вернемся к листу, а затем наша работа будет состоять в том, чтобы проверить, является ли дочерний элемент hasDesendantApples истинным или сам дочерний элемент является яблоком.
Когда у нас есть эта информация, сама проблема решается легко. . Давайте создадим функцию DFS, которая будет возвращать, сколько секунд потребуется, чтобы получить все яблоки из текущего узла. Мы будем использовать эту функцию рекурсивно. Мы запустим DFS из корня и выполним рекурсию следующим образом: если hasDescentApples текущего узла равно false, то вернём 0. В противном случае мы выполним рекурсию к левому узлу и правому узлу, если какой-либо из них является яблоком или любым из них. имеет потомка Apple. Мы просто добавим 2 + рекурсивно DFS (дочерний), где 2 происходит от перехода к этому узлу и возврата к текущему узлу.
Задача D: 1444. Количество способов разрезать пиццу (сложная)
Проблема
Дана прямоугольная пицца, представленная в виде матрицы rows x cols, содержащей следующие символы: 'A' (яблоко) и '.' (пустая ячейка), и задано целое число k. Вы должны разрезать пиццу на k кусочков, используя k-1 разрезов.
Для каждого разреза вы выбираете направление: вертикальное или горизонтальное, затем выбираете положение разреза на границе ячейки и разрезаете пиццу на две части. Если вы разрезаете пиццу вертикально, отдайте левую часть пиццы человеку. Если вы разрезаете пиццу горизонтально, отдайте верхнюю часть пиццы человеку. Отдайте последний кусок пиццы последнему человеку.
Вернуть количество способов разрезать пиццу таким образом, чтобы каждый кусок содержал по крайней мере одно яблоко. Поскольку ответ может быть огромным числом, верните его по модулю 10⁹ + 7.
Решение
DFS + Memoization (упрощенное динамическое программирование) —
Эта проблема напрашивается на DFS + Memoization/DP. Если вы не знакомы или плохо разбираетесь в DP, вы попали по адресу. Я объясню шаг за шагом, как прийти к оптимальному решению и решить любой вопрос DP во всех интервью и большинстве соревнований. Давайте начнем:
Грубая сила — поиск с возвратом/DFS: (TLE): O(K*M^N) Мой первый инстинкт в любой из подобных задач, где нас просят минимизировать/максимизировать какое-то число, — сначала напишите решение грубой силы. Конечно, решение грубой силы превысит лимит времени (TLE), но это ступенька к оптимальному решению.
Мы можем использовать брутфорс следующим образом:
Состояние. Во-первых, нам нужен способ представления нашего текущего прогресса. В данном случае это размер пиццы, с которой мы работаем. Поскольку пицца представляет собой прямоугольник, мы будем представлять текущий кусок пиццы с верхней левой точкой и нижней правой точкой для представления прямоугольника. Это обычный трюк в программировании для представления прямоугольников с двумя точками. Нам также нужно отслеживать количество сделанных разрезов.
Проверка возможных ходов:Наши возможные ходы, согласно задаче, — разделить пиццу по горизонтали и по вертикали. Таким образом, мы будем делать именно это. Мы будем делить пиццу разными способами и рекурсивно работать с этими кусочками пиццы. Для горизонтального разрезания это будет просто итерация по каждой строке и «разрезание пиццы» путем повторения на меньшей строке. Аналогично для вертикальных, но со столбцами. Мы тоже
Базовый вариант: если мы сократим k-1 раз, мы поймем, что все готово. Нам просто нужно k кусочков, поэтому разрезание k-1 раз означает, что мы разделили правильное количество раз.
Собираем все вместе: мы начинаем с вызова всей пиццы, то есть от (0,0) до (m-1,n-1) с cut = 0. Затем мы повторяем каждую возможные сокращения и рекурсия на эти новые кусочки пиццы. Нам нужно следить за тем, чтобы каждый разрез ДОЛЖЕН содержать яблоко. Чтобы определить, есть ли в прямоугольнике яблоко за время O(1), мы можем сделать это, используя другую таблицу DP. Если мы не используем DP, временная сложность увеличится на O(MN), поэтому нам нужно реализовать эту простую таблицу. Это называется Immutable 2D Querying, и вы можете проверить это здесь: https://leetcode.com/problems/range-sum-query-2d-immutable/
Как только мы доберемся до нашего базового случая, т.е. мы сделали k-1 разрезов, нам нужно проверить, есть ли на этом прямоугольном кусочке яблоко. Если это так, мы добавляем 1 к нашей глобальной возвращаемой переменной. Если нет, то просто вернитесь и закончите рекурсивную ветвь здесь.
Принято: O(MNK) — DFS с Memoizing:
Во-первых, нам нужно сделать что-то умное. Обратите внимание, как наша грубая сила отслеживает 5 переменных для состояния. Верхняя левая точка, которая состоит из двух переменных строки и столбца, нижняя правая точка, которая также является еще двумя переменными, и 5-я переменная, количество сделанных разрезов. Мы можем уменьшить количество переменных, чтобы сохранить состояния, заметив, что задача говорит о том, что для каждого разреза, который мы делаем, мы сохраняем правую половину, когда разрезаем вертикально, или сохраняем нижнюю половину, когда разрезаем горизонтально. Это означает, что наш кусок пиццы всегда будет содержать точку (m-1,n-1), то есть правую нижнюю часть пиццы. Таким образом, нет необходимости больше отслеживать нижнюю правую точку, поскольку она всегда будет (m-1,n-1). Таким образом, наше новое состояние — это верхняя левая точка и количество разрезов.
Теперь нам просто нужно преобразовать наш DFS Bruteforce в запоминание. Это делается путем сохранения значения каждого рекурсивного вызова и возврата суммы этих рекурсивных вызовов в конце. Нам также нужно сохранить его в глобальной таблице DP для кэширования вызовов. В начале каждого рекурсивного вызова мы сначала проверяем, было ли это состояние решено ранее. Если это было, то просто вернули это. Сделанный! Вы только что решили вопрос!
Контакт
Пишите мне по адресу [email protected], если у вас есть вопросы или код! Обязательно поставьте лайк этому посту и оставьте отзыв о будущих загрузках!
