Конкурс LeetCode раз в две недели 85: Перемещение букв II
Мы можем преобразовать задачу в следующую:
Учитывая массив длины n (равный входной строке) и q запросов, каждый запрос содержит диапазон [l, r] и +1 или -1. Для всех запросов увеличивайте или уменьшайте элементы в заданном диапазоне, а в конце всех запросов возвращайте значение для каждого индекса. Изначально все значения в массиве равны 0.
Грубым способом сделать это будет увеличение/уменьшение всех элементов в заданном диапазоне для всех запросов. Временная сложность обработки одного запроса будет O(n). Таким образом, общая временная сложность будет O(n*q). Это решение не пройдет, и мы должны найти лучшее решение.
Мы будем использовать алгоритм линейной развертки (scanline).
Мы инициализируем массив длины n + 1, называемый строкой, со всеми значениями, установленными в 0. У нас есть запрос [l, r, val]. Нам нужно добавить val(+1 или -1 в нашем случае) ко всем элементам в диапазоне. Для этого делаем следующее:
строка[l] += значение
строка[r + 1] -= значение
Приведенная выше операция занимает O(1) времени для обработки одного запроса. Таким образом, мы можем решить все запросы за время O(q). В конце концов, чтобы вычислить конечное значение по каждому индексу, мы находим сумму префиксов. Таким образом, окончательная сумма изменения по индексу i = prefix_sum_line[i].
Почему это работает?
Мы должны добавить val к диапазону [l, r]. Если есть массив pre со всеми нулями, мы добавляем val к pre[l] и -val к pre[r].
Для элементов в диапазоне [0, l) сумма префикса будет равна 0.
Для элементов в диапазоне [l, r] сумма префикса будет равна val.
Для элементов в диапазон [r+1, n), сумма префикса будет равна 0 из-за +val и -val.
Этот прием добавляет val к диапазону [l, r). Это хорошо работает для вопросов, на которые нам не нужно отвечать немедленно, но мы можем выполнить все запросы и дать комбинированный ответ после всех запросов.
Код для описанного выше подхода:
Мы также можем деревья Фенвика/деревья сегментов для вышеуказанной проблемы. Временная сложность будет O(qlogn), но это важные структуры данных для обновления диапазона и проблем с запросами. Подробнее об этих структурах данных можно узнать здесь: Дерево Фенвика, Дерево сегментов (Часть 1, Часть 2)
LeetCode Biweekly Contest 85: Максимальная сумма сегмента после удалений
Мы можем понять, что после обработки каждого запроса количество сегментов может увеличиться на 1. Может случиться так, что сегмент с максимальной суммой перед i-м запросом был затронут i-м запросом, или какой-то другой сегмент был изменен из-за i-го запроса . В первом случае нам придется смотреть на сумму всех отрезков после i-го запроса, чтобы получить максимальную сумму. Тогда как во втором случае максимальная сумма останется прежней.
Хитрость для решения этой проблемы заключается в том, чтобы думать наоборот! Если предположить, что изначально мы удалили все элементы. Таким образом, мы можем начать без сегментов, добавлять элементы в обратном порядке (как при удалении) и создавать/объединять сегменты. Есть три возможности после добавления элемента:
- Добавление текущих элементов приводит к созданию нового сегмента. Например: [x x x] _ _ _ _ [новый]
- Новые элементы присоединяются к существующему сегменту слева или справа. Например: [x x x][новый] _ _ _ _ [x x] -› [x x x новый] _ _ _ _ [x x], [x x x]_ _ _ _ _ [новый][x x] -› [x x x]_ _ _ _ _ [новый х х]
- Новый элемент объединяет два сегмента слева и справа. Например: [x x x][новый][x x] -> [x x x новый x x]
Мы можем сделать это с помощью Union-Find. Первоначально родительские элементы по всем индексам равны -1, что указывает на отсутствие сегмента. Теперь обрабатываем запросы в обратном порядке. После i-го запроса мы проверяем, можно ли объединить текущий элемент с сегментом соседних элементов (q[i]-1 и q[i]+1). Если да, мы объединяем сегменты и обновляем сумму сегмента. После обработки i-го запроса максимальная сумма из всех отрезков будет равна предыдущей максимальной сумме или сумме текущего отрезка.
Код для описанного выше подхода:
Еженедельный конкурс LeetCode 307: Найди K-сумму массива
Это сложная проблема. Обратите внимание на ограничения на k, k относительно невелико, поэтому мы можем генерировать подпоследовательности с максимальной суммой от 1 до k. Чему равна сумма максимальной суммы подпоследовательности? Это сумма всех положительных элементов массива. Теперь, какова вторая по величине сумма подпоследовательности? Постарайтесь получить его из максимальной суммы подпоследовательности. У нас есть два варианта: удалить наименьший положительный элемент из максимальной суммы подпоследовательности или добавить наибольшее отрицательное значение из массива к максимальной сумме подпоследовательности. Мы поймем это на примере. У нас есть следующий массив: [-1, 2, -3, 4, 5]. Максимальная сумма подпоследовательности — это сумма положительных элементов массива, равная 2+4+5=11. Теперь вторая по величине сумма подпоследовательности равна max(11–2, 11+-1) = 11+-1=10. Мы можем использовать максимальную кучу для генерации верхней суммы k подпоследовательностей.
У нас есть массив abs_nums, содержащий абсолютное значение всех элементов, присутствующих в массиве, отсортированных в порядке возрастания. Изначально max_sum — это сумма всех положительных элементов входного массива, а максимальная куча содержит один элемент (max_sum — abs_nums[0], 0). Это вторая по величине сумма подпоследовательности, которую мы видели в примере ранее. Пока мы не получаем k элементов(включая max_sum), делаем следующее:
- pop (next_sum, i) из max_heap
- если i + 1 ‹ N:
push (next_sum + abs_nums[i]-abs_nums[i + 1], i + 1) в max_heap
push (next_sum -abs_nums[i + 1], i + 1) в max_heap
Чтобы понять, как это работает, попробуйте подумать, как решить задачу, если нам нужно найти k-ю наименьшую сумму подпоследовательности. Первоначально нам нужно будет начать с наименьшего элемента и добавить элементы, аналогичные описанному выше методу, в мини-кучу.
Код для описанного выше подхода:
Еженедельный конкурс LeetCode 307: Построить матрицу с условиями
Предположим, что нам нужно расположить k элементов в массиве и иметь только условия строки. Условие строки [выше, ниже] дает нам порядок для двух элементов. Элемент выше должен стоять перед элементом перед. Мы можем смоделировать это как направленное ребро в графе. Мы можем сделать это для всех условий строки и построить ориентированный граф. Когда мы не можем расположить все k элементов массива в соответствии с заданными условиями? Мы не можем расположить элементы в массиве, когда в ориентированном графе есть цикл. Если граф является ориентированным ациклическим графом, мы можем использовать топологическую сортировку, чтобы упорядочить элементы в соответствии с заданными ограничениями.
Идея топологической сортировки проста, мы начинаем с узлов, имеющих нулевую степень вхождения. Эти элементы могут находиться в начале массива, поскольку они не зависят ни от каких предыдущих элементов. Если граф ациклический, в нем всегда будет хотя бы один узел с нулевой степенью вхождения. Поместив эти элементы в начало массива, мы можем уменьшить степень вхождения их соседей на единицу, и в этом процессе степень вхождения некоторых узлов будет равна 0. Мы можем разместить эти узлы в массиве так, как они были только одна зависимость, которая была разрешена на первом шаге. Мы делаем это итеративно, пока все k узлов не будут размещены в массиве. Временная сложность этого алгоритма составляет O(n), где n — количество узлов, k в нашем случае.
Возвращаясь к исходной задаче, мы обработали условия строк и получили порядок элементов, удовлетворяющих им. Мы можем обрабатывать условия столбца таким же образом и получить номер столбца, соответствующий каждому элементу, используя топологическую сортировку. Таким образом, мы получаем (строку, столбец) для каждого элемента, удовлетворяющего условиям.
Код для вышеуказанного подхода.
