Задача: 684. Redundant Connection
Сложность: medium
В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.
Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.
Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
👨💻 Алгоритм:
1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.
2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.
3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.
Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.
Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
👨💻 Алгоритм:
1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.
2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.
3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.
😎 Решение:
class Solution {
private $seen;
private $MAX_EDGE_VAL = 1000;
function findRedundantConnection($edges) {
$graph = array_fill(0, $this->MAX_EDGE_VAL + 1, []);
foreach ($edges as $edge) {
$this->seen = [];
if (!empty($graph[$edge[0]]) && !empty($graph[$edge[1]]) &&
$this->dfs($graph, $edge[0], $edge[1])) {
return $edge;
}
$graph[$edge[0]][] = $edge[1];
$graph[$edge[1]][] = $edge[0];
}
throw new Exception("No redundant connection found");
}
function dfs($graph, $source, $target) {
if (!in_array($source, $this->seen)) {
$this->seen[] = $source;
if ($source == $target) return true;
foreach ($graph[$source] as $nei) {
if ($this->dfs($graph, $nei, $target)) return true;
}
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний
Пожизненная PRO подписка на easyoffer по цене одного года.
Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.
Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию
Покупай на https://easyoffer.ru/
Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.
Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию
Покупай на https://easyoffer.ru/
Задача: 303. Range Sum Query - Immutable
Сложность: easy
Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).
Пример:
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.
2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.
3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).
Пример:
Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.
2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.
3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.
😎 Решение:
class NumArray {
private $sum;
function __construct($nums) {
$this->sum = array_fill(0, count($nums) + 1, 0);
for ($i = 0; $i < count($nums); $i++) {
$this->sum[$i + 1] = $this->sum[$i] + $nums[$i];
}
}
function sumRange($i, $j) {
return $this->sum[$j + 1] - $this->sum[$i];
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 729. My Calendar I
Сложность: medium
Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.
Пример:
👨💻 Алгоритм:
1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий.
2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.
3⃣Если новое событие не пересекается с существующими событиями, добавьте его в список событий и верните true. В противном случае верните false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.
Пример:
Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
👨💻 Алгоритм:
1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий.
2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.
3⃣Если новое событие не пересекается с существующими событиями, добавьте его в список событий и верните true. В противном случае верните false.
😎 Решение:
class MyCalendar {
private $events;
function __construct() {
$this->events = [];
}
function book($start, $end) {
foreach ($this->events as $event) {
if ($start < $event[1] && $end > $event[0]) {
return false;
}
}
$this->events[] = [$start, $end];
return true;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 826. Most Profit Assigning Work
Сложность: medium
У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.
Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям.
Пример:
👨💻 Алгоритм:
1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.
2⃣Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.
3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.
Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям.
Пример:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
👨💻 Алгоритм:
1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.
2⃣Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.
3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.
😎 Решение:
class Solution {
function maxProfitAssignment($difficulty, $profit, $worker) {
$jobProfile = [[0, 0]];
for ($i = 0; $i < count($difficulty); $i++) {
$jobProfile[] = [$difficulty[$i], $profit[$i]];
}
usort($jobProfile, function($a, $b) {
return $a[0] <=> $b[0];
});
for ($i = 1; $i < count($jobProfile); $i++) {
$jobProfile[$i][1] = max($jobProfile[$i][1], $jobProfile[$i - 1][1]);
}
$netProfit = 0;
foreach ($worker as $ability) {
$l = 0;
$r = count($jobProfile) - 1;
$jobProfit = 0;
while ($l <= $r) {
$mid = intdiv($l + $r, 2);
if ($jobProfile[$mid][0] <= $ability) {
$jobProfit = max($jobProfit, $jobProfile[$mid][1]);
$l = $mid + 1;
} else {
$r = $mid - 1;
}
}
$netProfit += $jobProfit;
}
return $netProfit;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Сложность: medium
Дан массив prices, где prices[i] — цена данной акции в i-й день.
Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями:
После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).
Пример:
👨💻 Алгоритм:
1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.
2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.
3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив prices, где prices[i] — цена данной акции в i-й день.
Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями:
После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).
Пример:
Input: prices = [1]
Output: 0
👨💻 Алгоритм:
1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.
2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.
3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.
😎 Решение:
class Solution {
function maxProfit($prices) {
if (empty($prices)) return 0;
$hold = -$prices[0];
$sold = 0;
$cooldown = 0;
for ($i = 1; $i < count($prices); $i++) {
$newHold = max($hold, $cooldown - $prices[$i]);
$newSold = $hold + $prices[$i];
$newCooldown = max($cooldown, $sold);
$hold = $newHold;
$sold = $newSold;
$cooldown = $newCooldown;
}
return max($sold, $cooldown);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 867. Transpose Matrix
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.
2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].
3⃣Верните матрицу ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.
Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.
Пример:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
👨💻 Алгоритм:
1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.
2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].
3⃣Верните матрицу ans.
😎 Решение:
class Solution {
function transpose($A) {
$R = count($A);
$C = count($A[0]);
$ans = array_fill(0, $C, array_fill(0, $R, 0));
for ($r = 0; $r < $R; ++$r)
for ($c = 0; $c < $C; ++$c)
$ans[$c][$r] = $A[$r][$c];
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 251. Flatten 2D Vector
Сложность: medium
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
👨💻 Алгоритм:
1⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.
2⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.
3⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]
Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next(); // return 1
vector2D.next(); // return 2
vector2D.next(); // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next(); // return 4
vector2D.hasNext(); // return False
👨💻 Алгоритм:
1⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.
2⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.
3⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().
😎 Решение:
class Vector2D {
private $nums;
private $position;
public function __construct($v) {
$this->nums = [];
foreach ($v as $innerList) {
$this->nums = array_merge($this->nums, $innerList);
}
$this->position = -1;
}
public function next() {
$this->position++;
return $this->nums[$this->position];
}
public function hasNext() {
return $this->position + 1 < count($this->nums);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 63. Unique Paths II
Сложность: medium
Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.
Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.
Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла.
Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.
Пример:
👨💻 Алгоритм:
1⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.
2⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.
3⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.
Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.
Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла.
Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.
Пример:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
👨💻 Алгоритм:
1⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.
2⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.
3⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.
😎 Решение:
function uniquePathsWithObstacles($obstacleGrid) {
$R = count($obstacleGrid);
$C = count($obstacleGrid[0]);
if ($obstacleGrid[0][0] == 1) {
return 0;
}
$obstacleGrid[0][0] = 1;
for ($i = 1; $i < $R; $i++) {
$obstacleGrid[$i][0] = ($obstacleGrid[$i][0] == 0 && $obstacleGrid[$i - 1][0] == 1) ? 1 : 0;
}
for ($i = 1; $i < $C; $i++) {
$obstacleGrid[0][$i] = ($obstacleGrid[0][$i] == 0 && $obstacleGrid[0][$i - 1] == 1) ? 1 : 0;
}
for ($i = 1; $i < $R; $i++) {
for ($j = 1; $j < $C; $j++) {
if ($obstacleGrid[$i][$j] == 0) {
$obstacleGrid[$i][$j] = $obstacleGrid[$i - 1][$j] + $obstacleGrid[$i][$j - 1];
} else {
$obstacleGrid[$i][$j] = 0;
}
}
}
return $obstacleGrid[$R - 1][$C - 1];
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium
Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.
Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:
Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.
Пример:
👨💻 Алгоритм:
1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.
2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.
3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.
Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:
Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.
Пример:
Input: grid = [[0,1],[1,0]]
Output: 2
👨💻 Алгоритм:
1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.
2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.
3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.
😎 Решение:
class Solution {
private static $directions = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1]
];
function shortestPathBinaryMatrix($grid) {
if ($grid[0][0] != 0 || $grid[count($grid) - 1][count($grid[0]) - 1] != 0) {
return -1;
}
$queue = [[0, 0]];
$grid[0][0] = 1;
while (!empty($queue)) {
[$row, $col] = array_shift($queue);
$distance = $grid[$row][$col];
if ($row == count($grid) - 1 && $col == count($grid[0]) - 1) {
return $distance;
}
foreach (self::$directions as $direction) {
$newRow = $row + $direction[0];
$newCol = $col + $direction[1];
if ($newRow >= 0 && $newCol >= 0 && $newRow < count($grid) && $newCol < count($grid[0]) && $grid[$newRow][$newCol] == 0) {
$queue[] = [$newRow, $newCol];
$grid[$newRow][$newCol] = $distance + 1;
}
}
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1344. Angle Between Hands of a Clock
Сложность: medium
Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.
Ответы с точностью до 10^-5 от фактического значения будут считаться правильными.
Пример:
👨💻 Алгоритм:
1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.
2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).
3⃣Вернуть меньший угол: min(diff, 360 - diff).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.
Ответы с точностью до 10^-5 от фактического значения будут считаться правильными.
Пример:
Input: hour = 12, minutes = 30
Output: 165
👨💻 Алгоритм:
1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.
2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).
3⃣Вернуть меньший угол: min(diff, 360 - diff).
😎 Решение:
class Solution {
public function angleClock($hour, $minutes) {
$oneMinAngle = 6;
$oneHourAngle = 30;
$minutesAngle = $oneMinAngle * $minutes;
$hourAngle = ($hour % 12 + $minutes / 60) * $oneHourAngle;
$diff = abs($hourAngle - $minutesAngle);
return min($diff, 360 - $diff);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 916. Word Subsets
Сложность: medium
Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.
Пример:
👨💻 Алгоритм:
1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.
2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.
3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.
Пример:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]
👨💻 Алгоритм:
1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.
2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.
3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.
😎 Решение:
function wordSubsets($words1, $words2) {
$maxCount = array_fill(0, 26, 0);
foreach ($words2 as $word) {
$count = getCount($word);
for ($i = 0; $i < 26; $i++) {
$maxCount[$i] = max($maxCount[$i], $count[$i]);
}
}
$result = [];
foreach ($words1 as $word) {
$count = getCount($word);
if (isUniversal($count, $maxCount)) {
$result[] = $word;
}
}
return $result;
}
function getCount($word) {
$count = array_fill(0, 26, 0);
foreach (str_split($word) as $char) {
$count[ord($char) - ord('a')]++;
}
return $count;
}
function isUniversal($count, $maxCount) {
for ($i = 0; $i < 26; $i++) {
if ($count[$i] < $maxCount[$i]) {
return false;
}
}
return true;
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 480. Sliding Window Median
Сложность: Hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
👨💻 Алгоритм:
1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.
2⃣Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна.
3⃣Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: Hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
👨💻 Алгоритм:
1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.
2⃣Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна.
3⃣Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.
😎 Решение:
function medianSlidingWindow($nums, $k) {
$medians = [];
for ($i = 0; $i + $k <= count($nums); $i++) {
$window = array_slice($nums, $i, $k);
sort($window);
if ($k % 2 == 1) {
$medians[] = $window[$k / 2];
} else {
$medians[] = ($window[$k / 2 - 1] + $window[$k / 2]) / 2.0;
}
}
return $medians;
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 170. Two Sum III - Data structure design
Сложность: easy
Разработайте структуру данных, которая принимает поток целых чисел и проверяет, есть ли в ней пара чисел, сумма которых равна определенному значению.
Реализуйте класс TwoSum:
- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.
Пример:
👨💻 Алгоритм:
1⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.
2⃣Итерация с использованием двух указателей:
Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся.
На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий:
Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения.
Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low.
Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.
3⃣Завершение цикла:
Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Разработайте структуру данных, которая принимает поток целых чисел и проверяет, есть ли в ней пара чисел, сумма которых равна определенному значению.
Реализуйте класс TwoSum:
- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.
Пример:
Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]
👨💻 Алгоритм:
1⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.
2⃣Итерация с использованием двух указателей:
Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся.
На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий:
Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения.
Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low.
Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.
3⃣Завершение цикла:
Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.
😎 Решение:
class TwoSum {
private $nums = [];
public function __construct() {}
public function add($number) {
if (!isset($this->nums[$number])) {
$this->nums[$number] = 0;
}
$this->nums[$number]++;
}
public function find($value) {
foreach ($this->nums as $num => $count) {
$complement = $value - $num;
if (($complement != $num && isset($this->nums[$complement])) ||
($complement == $num && $count > 1)) {
return true;
}
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy
Даны два массива строк
Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.
Пример:
👨💻 Алгоритм:
1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.
2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.
3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Даны два массива строк
word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.
Пример:
Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.
👨💻 Алгоритм:
1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.
2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.
3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.
😎 Решение:
class Solution {
function arrayStringsAreEqual($word1, $word2) {
$list2 = implode('', $word2);
$index = 0;
$n = strlen($list2);
foreach ($word1 as $word) {
for ($i = 0; $i < strlen($word); $i++) {
if ($index >= $n || $word[$i] != $list2[$index]) {
return false;
}
$index++;
}
}
return $index == $n;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 206. Reverse Linked List
Сложность: easy
Дан односвязный список, разверните этот список и верните развернутый список.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.
2⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.
3⃣После завершения цикла верните prev как новую голову развернутого списка.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан односвязный список, разверните этот список и верните развернутый список.
Пример:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
👨💻 Алгоритм:
1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.
2⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.
3⃣После завершения цикла верните prev как новую голову развернутого списка.
😎 Решение:
class ListNode {
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
function reverseList($head) {
$prev = null;
$curr = $head;
while ($curr !== null) {
$nextTemp = $curr->next;
$curr->next = $prev;
$prev = $curr;
$curr = $nextTemp;
}
return $prev;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1168. Optimize Water Distribution in a Village
Сложность: hard
В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы.
Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.
Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой.
Пример:
👨💻 Алгоритм:
1⃣Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков.
2⃣Набор для вершин: Используйте набор для поддержания всех вершин, добавленных в окончательное минимальное остовное дерево (MST) во время его построения. С помощью набора можно определить, была ли вершина уже добавлена или нет.
3⃣Очередь с приоритетом (куча): Используйте кучу для реализации жадной стратегии. На каждом шаге определяйте лучшее ребро для добавления на основе стоимости его добавления в дерево. Куча позволяет извлекать минимальный элемент за константное время и удалять минимальный элемент за логарифмическое время. Это идеально подходит для нашей задачи повторного нахождения ребра с наименьшей стоимостью.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы.
Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.
Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой.
Пример:
Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
👨💻 Алгоритм:
1⃣Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков.
2⃣Набор для вершин: Используйте набор для поддержания всех вершин, добавленных в окончательное минимальное остовное дерево (MST) во время его построения. С помощью набора можно определить, была ли вершина уже добавлена или нет.
3⃣Очередь с приоритетом (куча): Используйте кучу для реализации жадной стратегии. На каждом шаге определяйте лучшее ребро для добавления на основе стоимости его добавления в дерево. Куча позволяет извлекать минимальный элемент за константное время и удалять минимальный элемент за логарифмическое время. Это идеально подходит для нашей задачи повторного нахождения ребра с наименьшей стоимостью.
😎 Решение:
class Solution {
function minCostToSupplyWater($n, $wells, $pipes) {
$graph = array_fill(0, $n + 1, []);
$minHeap = new SplPriorityQueue();
$minHeap->setExtractFlags(SplPriorityQueue::EXTR_DATA);
foreach ($wells as $i => $cost) {
$graph[0][] = [$cost, $i + 1];
$minHeap->insert([$cost, $i + 1], -$cost);
}
foreach ($pipes as $pipe) {
[$house1, $house2, $cost] = $pipe;
$graph[$house1][] = [$cost, $house2];
$graph[$house2][] = [$cost, $house1];
}
$mstSet = [0 => true];
$totalCost = 0;
while (count($mstSet) < $n + 1) {
$edge = $minHeap->extract();
[$cost, $nextHouse] = $edge;
if (isset($mstSet[$nextHouse])) continue;
$mstSet[$nextHouse] = true;
$totalCost += $cost;
foreach ($graph[$nextHouse] as $neighborEdge) {
if (!isset($mstSet[$neighborEdge[1]])) {
$minHeap->insert($neighborEdge, -$neighborEdge[0]);
}
}
}
return $totalCost;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 850. Rectangle Area II
Сложность: hard
Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
👨💻 Алгоритм:
1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.
2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.
3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.
👨💻 Алгоритм:
1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.
2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.
3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.
😎 Решение:
class Solution {
function rectangleArea($rectangles) {
$N = count($rectangles);
$Xvals = [];
$Yvals = [];
foreach ($rectangles as $rec) {
$Xvals[$rec[0]] = true;
$Xvals[$rec[2]] = true;
$Yvals[$rec[1]] = true;
$Yvals[$rec[3]] = true;
}
$imapx = array_keys($Xvals);
sort($imapx);
$imapy = array_keys($Yvals);
sort($imapy);
$mapx = [];
$mapy = [];
foreach ($imapx as $i => $v) {
$mapx[$v] = $i;
}
foreach ($imapy as $i => $v) {
$mapy[$v] = $i;
}
$grid = array_fill(0, count($imapx), array_fill(0, count($imapy), false));
foreach ($rectangles as $rec) {
for ($x = $mapx[$rec[0]]; $x < $mapx[$rec[2]]; $x++) {
for ($y = $mapy[$rec[1]]; $y < $mapy[$rec[3]]; $y++) {
$grid[$x][$y] = true;
}
}
}
$ans = 0;
for ($x = 0; $x < count($grid); $x++) {
for ($y = 0; $y < count($grid[0]); $y++) {
if ($grid[$x][$y]) {
$ans += ($imapx[$x + 1] - $imapx[$x]) * ($imapy[$y + 1] - $imapy[$y]);
}
}
}
$ans %= 1_000_000_007;
return (int)$ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 690. Employee Importance
Сложность: medium
У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных.
Вам дан массив сотрудников employees, где:
employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.
Пример:
👨💻 Алгоритм:
1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.
2⃣Реализуйте функцию DFS для подсчета общей важности, которая включает важность сотрудника и всех его подчиненных.
3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных.
Вам дан массив сотрудников employees, где:
employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.
Пример:
Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.
👨💻 Алгоритм:
1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.
2⃣Реализуйте функцию DFS для подсчета общей важности, которая включает важность сотрудника и всех его подчиненных.
3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.
😎 Решение:
class Employee {
public $id;
public $importance;
public $subordinates;
function __construct($id, $importance, $subordinates) {
$this->id = $id;
$this->importance = $importance;
$this->subordinates = $subordinates;
}
}
class Solution {
private $emap;
function getImportance($employees, $queryid) {
$this->emap = [];
foreach ($employees as $e) {
$this->emap[$e->id] = $e;
}
return $this->dfs($queryid);
}
private function dfs($eid) {
$employee = $this->emap[$eid];
$ans = $employee->importance;
foreach ($employee->subordinates as $subid) {
$ans += $this->dfs($subid);
}
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium
Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.
Пример:
👨💻 Алгоритм:
1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.
2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.
3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.
Пример:
Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
👨💻 Алгоритм:
1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.
2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.
3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.
😎 Решение:
function leadsToDestination($n, $edges, $source, $destination) {
$graph = [];
foreach ($edges as $edge) {
$graph[$edge[0]][] = $edge[1];
}
$visited = array_fill(0, $n, 0);
function dfs($node, $graph, &$visited, $destination) {
if ($visited[$node] != 0) return $visited[$node] == 2;
if (!isset($graph[$node])) return $node == $destination;
$visited[$node] = 1;
foreach ($graph[$node] as $neighbor) {
if (!dfs($neighbor, $graph, $visited, $destination)) return false;
}
$visited[$node] = 2;
return true;
}
return dfs($source, $graph, $visited, $destination);
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium
Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.
2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.
3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.
Пример:
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
👨💻 Алгоритм:
1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.
2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.
3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.
😎 Решение:
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
private $index = 0;
function bstFromPreorder($preorder) {
return $this->constructBST($preorder, PHP_INT_MIN, PHP_INT_MAX);
}
private function constructBST($preorder, $lower, $upper) {
if ($this->index == count($preorder)) {
return null;
}
$val = $preorder[$this->index];
if ($val < $lower || $val > $upper) {
return null;
}
$this->index++;
$root = new TreeNode($val);
$root->left = $this->constructBST($preorder, $lower, $val);
$root->right = $this->constructBST($preorder, $val, $upper);
return $root;
}
}Ставь 👍 и забирай 📚 Базу знаний