У нас есть numCourses курсов, пронумерованных от 0 до numCourses - 1.
Даны:
Массив prerequisites, где prerequisites[i] = [a, b] указывает, что курс a необходимо пройти перед курсом b.
Массив запросов queries, где queries[j] = [u, v] спрашивает: является ли курс u предшественником курса v.
Нужно вернуть массив булевых значений, где для каждого запроса ответ — true, если курс u является прямым или косвенным предшественником курса v; или false, если нет.
💡 Идея
Представим зависимости курсов в виде графа, где вершины — это курсы, а ребра указывают на зависимости между ними. Наша цель — определить, существует ли путь между двумя вершинами графа. Для этого можно использовать алгоритм Флойда-Уоршелла, чтобы вычислить транзитивное замыкание графа.
🛠️ Подробности подхода
Инициализация матрицы зависимостей: Создаем булевую матрицу n x n, где dep_matrix[i][j] обозначает, что курс i является предшественником курса j.
Заполнение прямых зависимостей: На основе массива prerequisites отмечаем прямые зависимости в матрице.
Дан массив положительных чисел nums и положительное число limit.
Разрешено менять местами элементы массива nums[i] и nums[j], если выполняется условие: |nums[i] - nums[j]| <= limit.
Необходимо получить лексикографически минимальный массив, выполняя такие операции любое количество раз.
Лексикографический порядок: Массив a меньше массива b, если на первой позиции i, где они различаются, a[i] < b[i].
💡 Идея:
Будем эксплуатировать следующие замечания:
Элементы могут менять местами только внутри определённых групп, где (после её вырезания и сортировки) выполняется условие: |nums[group[i+1]] - nums[group[i]]| <= limit.
Индексная сортировка по значениям nums поможет нас найти группы, внутри которых возможны перестановки.
Сортировка каждой из этих групп может быть эффективно выполнена с помощью дополнительного индексного массива.
🔍 Детали подхода:
Сортировка индексов: На первом шаге создаём массив sorted_indices, заполняя его значениями [0, 1, ..., n-1]. Затем сортируем этот массив по значениям массива nums, чтобы определить относительный порядок элементов.
В очередной задаче для обзора - 802. Find Eventual Safe States нам предстоит найти вершины, не попадающие в циклы графа.
📋 Описание задачи
Нужно определить безопасные вершины в ориентированном графе.
Безопасная вершина — это такая вершина, из которой невозможно попасть в цикл. Если из вершины можно попасть только в терминальные вершины или другие безопасные, она считается безопасной.
Граф представлен в виде списка смежности, где graph[i] содержит все вершины, в которые можно попасть из вершины i.
Вернуть необходимо список всех безопасных вершин в возрастающем порядке.
Граф из примера имеет безопасными вершины: [4,5,6]
💡 Идея
Задача решается с помощью обхода графа в глубину (DFS) и вектора состояний.
Каждому узлу присваивается одно из трёх состояний:
Unseen (ещё не обработан);
Processing (в процессе обработки; узлы, являющиеся частью цикла, остаются в этом состоянии и после обработки);
В нашей новой задаче - 1765. Map of Highest Peak продолжим закреплять работу с семейством простых графовых алгоритмов.
📜 Описание задачи
Вам дана матрица isWater размером m×n, где:
isWater[i][j] == 1 указывает, что клетка — это вода.
isWater[i][j] == 0 указывает, что клетка — это суша.
Требуется назначить высоты каждой клетке таким образом, чтобы:
Высота каждой клетки была неотрицательной.
Высота любой клетки с водой была равна 0.
Абсолютная разница высот у соседних клеток не превышала 1.
Максимальная высота в назначенной карте была как можно больше.
💡 Идея
Мы используем поиск в ширину с несколькими источниками (multi-source BFS), начиная с клеток воды (высота 0).
На каждом шаге ближайшие клетки суши получают высоту на 1 больше текущей.
Этот метод гарантирует, что все клетки суши получают наилучшую из возможных высот, что приводит к максимизации самой высокой высоты в матрице.
🛠 Подробности подхода
Инициализация:
Создаём очередь и добавляем в неё все клетки воды, помечая их высотой 0.
Сегодня в нашей задаче 2017. Grid Game требуется рассчитать оптимальную стратегию в игре с 2 участниками. И большая часть решения опять – "размышления на салфетке".
🖍️ Условие задачи
Дано: двумерный массив grid размером 2 x n, где grid[r][c] представляет количество очков в ячейке (r, c).
Два робота начинают игру в ячейке (0, 0) и должны достичь ячейки (1, n-1).
Оба робота могут двигаться только вправо или вниз.
Первый робот проходит от начальной точки до финиша, собирая все очки на своём пути.
Затем второй робот выполняет аналогичный маршрут, при этом очки с пройденных первым роботом ячеек обнуляются.
Цель первого робота: минимизировать максимальное количество очков, которые сможет собрать второй робот.
💡 Идея
Легко увидеть, что только две стратегии второго робота могут оказаться оптимальными:
Право → Вниз: Сначала пройти весь верхний ряд, а затем спуститься вниз на последней колонке.
Вниз → Право: Спуститься вниз сразу, а затем двигаться вправо вдоль нижнего ряда.
В следующей задаче - 2661. First Completely Painted Row or Column можно не симулировать в лоб, и за счёт этого сэкономить память при решении (хоть и не получится асимптотически лучше).
📋 Описание задачи
Нам дан массив arr и матрица mat, содержащие числа от 1 до m * n.
Массив arr задаёт порядок закраски ячеек матрицы mat (закрашивается ячейка, содержащая указанное число).
В следующем примере: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Необходимо найти первый такой индекс i в массиве arr, при котором:
Либо вся строка, либо весь столбец матрицы окажется закрашенным.
💡 Идея
Задачу можно переформулировать:
Каждая строка и каждый столбец закрашиваются, если все элементы строки/столбца обработаны в порядке массива arr.
Получается, что для решения задачи нужно:
Найти максимальный индекс появления значений из arr для каждой строки/столбца.
Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
Представление и сортировка:
Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
Сортируем ячейки по высоте в порядке возрастания.
Структура объединения множеств:
Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
У нас есть поле размером m×n, где каждая клетка содержит указание направления движения. Необходимо найти минимальную стоимость перехода из левого верхнего угла (0, 0) в правый нижний угол (m−1,n−1).
Каждая клетка указывает направление движения:
1 — вправо,
2 — влево,
3 — вниз,
4 — вверх.
Изменение направления перехода возможно, но со стоимостью 1, и его можно выполнить только один раз для каждой клетки.
💡 Идея
Поле можно рассматривать как ориентированный граф, где клетки являются вершинами, а направления задают ребра. Наша цель — найти минимальную стоимость пути из начальной клетки в конечную. Для этого используется модифицированный BFS с двумя очередями, где приоритет отдается движениям без изменения направления.
Наша новая задача – 2425. Bitwise XOR of All Pairings решается "размышлениями на салфетке" и потом очень быстро и просто программируется.
📋 Описание задачи
Даны два массива nums1 и nums2, содержащие неотрицательные числа. Для каждой пары чисел, взятых из этих массивов, вычисляется побитовый XOR. Нужно вернуть результат XOR всех таких пар.
🧠 Идея
XOR обладает полезными свойствами:
Результат XOR числа с самим собой равен 0(a ^ a = 0).
XOR ассоциативен и коммутативен, что позволяет упрощать вычисления.
Только если длина одного массива нечётная, элементы второго массива оказывают влияние на результат, так как они "непарные".
В итоге вклад в результат зависит от длины второго массива для каждого массива из входной пары.
😃 Детали подхода
Найти длины массивов nums1 и nums2.
Если длина nums2 нечётная, XOR всех элементов nums1 добавляется в результат.
Если длина nums1 нечётная, XOR всех элементов nums2 добавляется в результат.
Возвратить результат как итоговый XOR.
⏱️ Асимптотика
Время:
O(n + m), где n и m — длины массивов nums1 и nums2.
XOR всех элементов каждого массива занимает линейное время.
Память:
O(1), используется небольшое число дополнительных переменных.
💻 Исходный код
usestd::ops::BitXor;implSolution{pubfnxor_all_nums(nums1: Vec<i32>,nums2: Vec<i32>) -> i32{letlen_nums1=nums1.len();letlen_nums2=nums2.len();// Initialize result as 0letmutresult=0;// If nums1 has an odd number of elements, XOR all elements of nums2iflen_nums1%2==1{result^=nums2.into_iter().fold(0,i32::bitxor);}// If nums2 has an odd number of elements, XOR all elements of nums1iflen_nums2%2==1{result^=nums1.into_iter().fold(0,i32::bitxor);}result}}
Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.
📜 Описание задачи
Дано два положительных числа num1 и num2. Нужно найти число x, такое что:
Количество установленных битов в числе x равно количеству установленных битов в num2.
Результат операции XOR между x и num1 минимален.
💡 Идея
Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.
✨ Детали подхода
Подсчёт установленных битов:
Используем метод count_ones, чтобы подсчитать количество установленных битов в числе num2.
Сохранение старших битов:
Проходим по битам num1 с самого старшего до младшего.
Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
Дана строка s, состоящая только из символов '(' и ')', и строка locked длины n, состоящая из символов '0' и '1'. Каждая позиция в locked указывает, можно ли изменить символ в s на этой позиции:
Если locked[i] == '1', символ s[i] нельзя менять.
Если locked[i] == '0', символ s[i] можно изменить на '(' или ')'.
Нужно определить, можно ли сделать строку s корректной скобочной записью.
💡 Идея
Решение основывается на двух проходах по строке:
- Прямой проход: Проверяем баланс открывающих и закрывающих скобок слева направо, учитывая символы, которые можно менять.
- Обратный проход: Инвертируем строку (меняем '(' на ')' и наоборот) и проверяем баланс справа налево.
При каждом проходе используем два счётчика:
- balance для отслеживания текущего баланса скобок.
- free для отслеживания количества символов, которые можно изменить.
Если на любом этапе баланс становится отрицательным, и его нельзя компенсировать изменением свободных символов, строка не может быть сделана валидной.
Даны две перестановки целых чисел A и B длины n. Необходимо вычислить массив общего префикса C, где C[i] равен количеству чисел, присутствующих в обеих перестановках на индексах от 0 до i.
Пример:
Input:A = [1,3,2,4], B = [3,1,2,4]
Output:[0,2,3,4]
💡 Идея
Чтобы быстро подсчитать количество общих элементов в префиксе, мы будем использовать два булевых массива для отслеживания того, какие элементы уже встречались в каждой из перестановок. Это позволит эффективно определять, какие элементы являются общими на каждом шаге.
📋 Подробности подхода
Создаем два булевых массива seen_in_a и seen_in_b длины n + 1 для отслеживания элементов, уже встреченных в A и B.
Проходим по массивам A и B одновременно:
Помечаем текущие элементы A[i] и B[i] как "увиденные".
Увеличиваем счетчик общих элементов, если текущий элемент уже был встречен в другом массиве.
На каждом шаге добавляем текущее значение счетчика общих элементов в результат.
Страшилку "серой слизи" изобрел футуролог Эрик Дрекслер еще в прошлом веке. Суть идеи в том, что самовоспроизводящиеся наноботы, если упустить их из лаборатории, могут начать бесконечно копировать себя, и в результате Земля превратится в бесформенную "серую слизь", состоящую из гигантской массы нанороботов.
В 2024 году даже самые параноидальные исследователи экзистенциальных рисков относятся к "серой слизи" не слишком всерьёз. Мы не умеем делать самовоспроизводящихся наноботов и вряд ли научимся до того, как изобретём сильный искусственный интеллект который все равно нас уничтожит, с наноботами или без них.
Да?
Нет, первый реалистичный кандидат на роль "серой слизи" уже активно обсуждается, и именно в контексте "давайте сразу запретим, не дожидаясь, пока это начнут делать".
Чтобы понятно было, что это за зверь, почему его создание относительно реалистично, и чем всё это страшно, для начала напомню про понятие хиральности. Сложные органические молекулы могут быть несимметричными. В этом случае зеркальное отражение той же молекулы будет от неё отличаться. Например, для человека молекула "левой" хиральности может быть нормальным участником его метаболизма, а "правая" будет токсична.
Почему так происходит, ведь вроде бы законы химии инвариантны относительно зеркальной симметрии? Дело в том, в этом смысле почему-то несимметричны все живые существа. Аминокислоты, из которых состоят белки, в природе существуют почти исключительно в "левой" форме, а сахара, например, глюкоза, только в "правой". Хотя при замене хиральности у всех молекул, участвующих в реакции, ничего не поменялось бы, если заменить хиральность только у части из них, она может пойти совсем иначе, поэтому то, что жизнь несимметрична, важно.
Для задачи 769. Max Chunks To Make Sorted у меня есть очень короткое решение, а значит и разбор не стоит делать длинным ;)
Задача: Максимальное количество отсортированных блоков 🧩
Дана перестановка arr длины n. Нужно разделить массив на максимальное количество блоков, таких, что, отсортировав каждый блок по отдельности и объединив их, получится полностью отсортированный массив.
Идея
Вводим функцию баланса, зависящую от частичных сумм по индексам и значениям. Каждый новый блок формируем при нулевых балансах.
Подход
Напишем код самым коротким и непонятным читателю образом, как только умеем.
Задача: найти все строки из words1, которые являются универсальными относительно всех строк из words2.
Условие универсальности:
Строка a из words1универсальна, если для каждой строки b из words2 строка b является подмножеством строки a (Подмножество строки: строка b является подмножеством строкиa, если каждая буква в b встречается в a как минимум столько же раз).
Пример:
["warrior", "world"] и ["wrr"] Ответ:["warrior"], так как только warrior покрывает все буквы из wrr.
💡 Идея
Для эффективного решения задачи:
- Определим максимальное количество вхождений каждой буквы по всем строкам из words2.
- Для каждой строки из words1 проверим, удовлетворяет ли она этим требованиям.
notq - коллективный блог. Я сделал его для людей, которые мне нравятся. Скорее всего, это и вы.
И лентой, и ранжированием комментариев управляют посетители с помощью голосования (примерно как на hackernews или на старом реддите). Пишите о чем угодно и как угодно. Вообще-то все свои, но некоторые иногда стесняются, поэтому можете писать анонимно.
Действует единственное правило: не пишите чего-нибудь такого, за что меня или вас посадят. Модерация есть, но предназначена только для решения этой задачи. Upd: правило отменено
notq - проект личный, некоммерческий, не связанный ни с какой компанией или организацией. Честно!
Баги и предложения о развитии можете кидать в комментарии.
Peace.
Почему notq?В честь моей бывшей. В каком-то смысле. Потому что всего 4 буквы, не занято, вполне приличные ассоциации с нотами и заметками. Читается "нотка", а впрочем, читайте как хотите
Задача на сегодня 2381. Shifting Letters II - решается несложно, но используемая идея мне лично кажется интересной и симпатичной.
Описание задачи 🔎
Дана строка s и список операций shifts, где каждая операция задаёт начало и конец диапазона, а также направление (вперёд или назад).
Ваша задача — применить все сдвиги к строке и вернуть окончательный результат.
Идея 🔄
Для оптимизации решения и избежания повторных расчётов сдвигов, мы используем алгоритм, основанный на префиксных суммах. Это позволяет эффективно сохранять кумулятивный эффект от всех сдвигов в отдельном массиве и применять их конечному результату за один проход.
Детали решения 📝
Создадим массив net_shifts, где будут храниться чистые значения сдвигов для каждой позиции в строке.
Пройдемся по всем операциям и обновим массив net_shifts, добавляя значения в начале диапазона и вычитая их сразу после его окончания.
Произведем один последовательный проход по строке, вычисляя кумулятивные сдвиги и применяя их для каждого символа.
Асимптотика ⏳
Время: O(n + m), где n — длина строки, m — количество операций.
Дана строка s. Необходимо определить количество уникальных палиндромов длины 3, которые являются подпоследовательностями строки.
Подпоследовательность — это строка, полученная из исходной строки удалением некоторых (возможно, нуля) символов без изменения их порядка. Например, для строки "abcde" строка "ace" является подпоследовательностью.
Палиндром — это строка, которая читается одинаково в прямом и обратном направлениях.
💡 Идея
Основная идея заключается в том, что палиндром длины 3 определяется первыми и последними символами, которые совпадают, а также любым допустимым символом посередине.
Мы можем эффективно отслеживать такие пары (первый и последний символы) с помощью битового массива (bitset), что позволяет минимизировать использование памяти.
🔍 Детали подхода
Массивы частот:
prefix_frequency: хранит частоты символов слева от рассматриваемого.
suffix_frequency: хранит частоты символов справа от рассматриваемого.
Дан массив целых чисел nums длины n. Требуется найти количество индексов i, где выполняются следующие условия:
Сумма первых i+1 элементов массива больше или равна сумме оставшихся элементов.
Индекс i удовлетворяет 0≤i<n−1, то есть правая часть должна содержать хотя бы один элемент.
Идея 💡
Вместо того чтобы каждый раз вычислять суммы левой и правой частей массива, мы используем баланс для их трекинга.
Изначально баланс равен −total_sum, где total_sum — сумма всех элементов массива. На каждом шаге баланс обновляется с помощью текущего элемента, а проверка условий выполняется через простое сравнение баланса с нулём.
Подробности подхода 🛠️
Вычислить сумму всех элементов массива и сохранить её в total_sum.
Проитерироваться по массиву до предпоследнего элемента:
Обновить баланс, добавляя 2×текущий элемент.
Если баланс становится больше или равен нулю, увеличивать счётчик допустимых разбиений.
Вернуть итоговый счётчик, который отражает количество валидных разбиений.
Нам дан массив строк words и массив запросов queries, где каждый запрос задаётся парой [li, ri]. Необходимо для каждого запроса определить количество строк из диапазона [li, ri], которые начинаются и заканчиваются на гласные буквы ('a', 'e', 'i', 'o', 'u').
Вернуть массив ответов, где каждый элемент соответствует результату очередного запроса.
💡 Идея
Чтобы эффективно отвечать на диапазонные запросы, мы можем заранее подсчитать кумулятивные суммы валидных строк (начинающихся и заканчивающихся на гласные) в массиве префиксных сумм. Это позволяет сократить обработку каждого запроса до константного времени.
🔍 Подробности подхода
Создание префиксных сумм:
Сначала создаём итератор prefix_sum_iter, вычисляющий кумулятивное количество "валидных" строк
(неплохой повод воспользоваться для этого методом std::iter::scan).
Добавляем 0 в начало итогового массива (см. std::iter::once и std::iter::chain), чтобы упростить расчёты для запросов (исключая лишнюю проверку условий для обработки начала диапазона).
Дана бинарная строка, состоящая из символов 0 и 1.
Требуется найти максимальный результат разбиения строки на две непустые подстроки.
Результат определяется как:
Результат = (Количество нулей в левой подстроке) + (Количество единиц в правой подстроке).
💡 Идея
Для эффективного решения задачи:
Рассчитаем динамический баланс для каждого допустимого разбиения строки. Баланс показывает, насколько выгодно разделить строку в конкретной точке.
Пройдем по строке, обновляя текущий баланс и максимальный результат. Пропустим последнюю итерацию, чтобы обе подстроки оставались непустыми.
🔍 Подробности подхода
Формула результата: Для разбиения в точке i:
Result = zero_count + (total_ones - ones_count)
, где:
Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.
📜 Условие задачи
У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:
Однодневный билет за costs[0] долларов.
Семидневный билет (покрывает любые последовательно идущие 7 дней) за costs[1] долларов.
Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за costs[2] долларов.
Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.
💡 Идея
Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.
🛠️ Детали подхода
Создаем массив dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.
Нам нужно подсчитать количество "хороших строк", длина которых находится в диапазоне [low, high].
Хорошая строка создаётся из пустой строки путём выполнения следующих операций:
Добавление символа '0' ровно zero раз.
Добавление символа '1' ровно one раз.
Результат может быть очень большим, поэтому необходимо вернуть его по модулю 10⁹+7.
💡 Идея
Для решения задачи мы используем динамическое программирование.
Каждое состояние dp[length] хранит количество способов построить строку длины length.
Постепенно вычисляя значения для всех длин от 1 до high, мы получаем итоговый результат.
🔍 Подробности подхода
Инициализация:
Создаём массив dp длиной high+1, где dp[length] будет содержать количество способов построить строку длины length.
Базовый случай:dp[0] = 1, так как существует ровно один способ создать пустую строку.
Дано: список строк words одинаковой длины и строка target. Цель: определить, сколькими способами можно собрать строку target, следуя правилам:
В очередной шаг можно использовать символ, совпадающий с необходимым очередным символом target, из любой допустимой позиции таблицы words.
После выбора символа из определённой позиции все символы всех слов левее или равные этой позиции становятся недоступными.
Вернуть количество способов по модулю 1_000_000_007
💡 Идея
Мы можем использовать подход динамического программирования. Для быстрого обновления состояний ДП предварительно подсчитаем частоты символов для каждой позиции в words.
Формула ДП:
Пусть dp[i][j] — количество способов собрать первые i символов строки target, используя первые j-й позиции в строках words. Тогда:
Дано: массив чисел nums и целое число k. Задача: найти три непересекающихся подмассива длины k с максимальной суммой и вернуть индексы их начала.
Если существует несколько решений, вернуть лексикографически минимальное.
Идея 💡
Для нахождения оптимального решения нам нужно:
Вычислить суммы всех подмассивов длины k с помощью техники скользящего окна.
Найти лучшие индексы подмассивов для правой, средней и левой частей массива, используя динамическое программирование.
Это позволяет эффективно комбинировать результаты и найти оптимальное выделение трёх подмассива.
Детали подхода 🛠️
Скользящее окно для вычисления сумм:
Вычисляем суммы всех подмассивов длины k, чтобы избежать повторных расчетов.
Поиск лучших правых подмассивов:
Сканируем массив справа налево, чтобы сохранить индексы подмассивов с максимальной суммой для каждого положения.
leetcoder
finder