Задача: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 730. Count Different Palindromic Subsequences
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.
Пример:
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.
2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.
3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.
Пример:
Input: s = "bccb"
Output: 6
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.
2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.
3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.
😎 Решение:
function countPalindromicSubsequences($s) {
$MOD = 1000000007;
$n = strlen($s);
$dp = array_fill(0, $n, array_fill(0, $n, 0));
for ($i = 0; $i < $n; $i++) {
$dp[$i][$i] = 1;
}
for ($length = 2; $length <= $n; $length++) {
for ($i = 0; $i <= $n - $length; $i++) {
$j = $i + $length - 1;
if ($s[$i] == $s[$j]) {
$l = $i + 1;
$r = $j - 1;
while ($l <= $r && $s[$l] != $s[$i]) $l++;
while ($l <= $r && $s[$r] != $s[$j]) $r--;
if ($l > $r) {
$dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 + 2;
} else if ($l == $r) {
$dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 + 1;
} else {
$dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 - $dp[$l + 1][$r - 1];
}
} else {
$dp[$i][$j] = $dp[$i + 1][$j] + $dp[$i][$j - 1] - $dp[$i + 1][$j - 1];
}
$dp[$i][$j] = ($dp[$i][$j] + $MOD) % $MOD;
}
}
return $dp[0][$n - 1];
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 284. Peeking Iterator
Сложность: medium
Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).
Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.
Пример:
👨💻 Алгоритм:
1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.
2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.
3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).
Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.
Пример:
Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]
Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next(); // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek(); // return 2, the pointer does not move [1,2,3].
peekingIterator.next(); // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next(); // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False
👨💻 Алгоритм:
1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.
2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.
3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.
😎 Решение:
class PeekingIterator {
private $iterator;
private $nextElement;
public function __construct(Iterator $iterator) {
$this->iterator = $iterator;
$this->nextElement = $iterator->valid() ? $iterator->current() : null;
}
public function next() {
$currentElement = $this->nextElement;
$this->iterator->next();
$this->nextElement = $this->iterator->valid() ? $this->iterator->current() : null;
return $currentElement;
}
public function hasNext() {
return $this->nextElement !== null;
}
public function peek() {
return $this->nextElement;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача №26. Remove Duplicates from Sorted Array
Сложность: easy
Учитывая целочисленный массив
Пример:
👨💻 Алгоритм:
1⃣Использовать два указателя:
2⃣Если текущий элемент отличается от предыдущего, записать его на
3⃣Вернуть
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Учитывая целочисленный массив
nums, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов. Пример:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
👨💻 Алгоритм:
1⃣Использовать два указателя:
index для записи уникальных элементов и i для перебора массива. 2⃣Если текущий элемент отличается от предыдущего, записать его на
index-позицию. 3⃣Вернуть
index как количество уникальных элементов. 😎 Решение:
class Solution {
function removeDuplicates(&$nums) {
$index = 1;
for ($i = 1; $i < count($nums); $i++) {
if ($nums[$i] !== $nums[$i - 1]) {
$nums[$index++] = $nums[$i];
}
}
return $index;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 835. Image Overlap
Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
👨💻 Алгоритм:
1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.
2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).
3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.
👨💻 Алгоритм:
1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.
2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).
3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.
😎 Решение:
class Solution {
function shiftAndCount($xShift, $yShift, $M, $R) {
$leftShiftCount = 0;
$rightShiftCount = 0;
$rRow = 0;
for ($mRow = $yShift; $mRow < count($M); ++$mRow) {
$rCol = 0;
for ($mCol = $xShift; $mCol < count($M); ++$mCol) {
if ($M[$mRow][$mCol] == 1 && $M[$mRow][$mCol] == $R[$rRow][$rCol]) {
$leftShiftCount++;
}
if ($M[$mRow][$rCol] == 1 && $M[$mRow][$rCol] == $R[$rRow][$mCol]) {
$rightShiftCount++;
}
$rCol++;
}
$rRow++;
}
return max($leftShiftCount, $rightShiftCount);
}
function largestOverlap($A, $B) {
$maxOverlaps = 0;
for ($yShift = 0; $yShift < count($A); ++$yShift) {
for ($xShift = 0; $xShift < count($A); ++$xShift) {
$maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $A, $B));
$maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $B, $A));
}
}
return $maxOverlaps;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 661. Image Smoother
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
👨💻 Алгоритм:
1⃣Инициализация:
Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания.
2⃣Обработка каждой ячейки:
Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).
Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы.
3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0
👨💻 Алгоритм:
1⃣Инициализация:
Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания.
2⃣Обработка каждой ячейки:
Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).
Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы.
3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.
😎 Решение:
class Solution {
function imageSmoother($img) {
$m = count($img);
$n = count($img[0]);
$result = array_fill(0, $m, array_fill(0, $n, 0));
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
$count = 0;
$total = 0;
for ($ni = max(0, $i - 1); $ni <= min($m - 1, $i + 1); $ni++) {
for ($nj = max(0, $j - 1); $nj <= min($n - 1, $j + 1); $nj++) {
$total += $img[$ni][$nj];
$count++;
}
}
$result[$i][$j] = floor($total / $count);
}
}
return $result;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1143. Longest Common Subsequence
Сложность: medium
Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.
Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.
Пример:
👨💻 Алгоритм:
1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны.
2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.
3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.
Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.
Пример:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
👨💻 Алгоритм:
1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны.
2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.
3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.
😎 Решение:
class Solution {
private $memo = [];
private $text1;
private $text2;
function longestCommonSubsequence($text1, $text2) {
$this->text1 = $text1;
$this->text2 = $text2;
$len1 = strlen($text1);
$len2 = strlen($text2);
$this->memo = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, -1));
return $this->memoSolve(0, 0);
}
private function memoSolve($p1, $p2) {
if ($p1 == strlen($this->text1) || $p2 == strlen($this->text2)) return 0;
if ($this->memo[$p1][$p2] != -1) return $this->memo[$p1][$p2];
if ($this->text1[$p1] == $this->text2[$p2]) {
$this->memo[$p1][$p2] = 1 + $this->memoSolve($p1 + 1, $p2 + 1);
} else {
$this->memo[$p1][$p2] = max($this->memoSolve($p1, $p2 + 1), $this->memoSolve($p1 + 1, $p2));
}
return $this->memo[$p1][$p2];
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy
У нас есть n фишек, где позиция i-й фишки равна position[i].
Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.
Пример:
👨💻 Алгоритм:
1⃣Посчитать количество фишек на четных и нечетных позициях.
2⃣Сравнить количество фишек на четных и нечетных позициях.
3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
У нас есть n фишек, где позиция i-й фишки равна position[i].
Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.
Пример:
Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost = 2.
👨💻 Алгоритм:
1⃣Посчитать количество фишек на четных и нечетных позициях.
2⃣Сравнить количество фишек на четных и нечетных позициях.
3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.
😎 Решение:
class Solution {
function minCostToMoveChips($position) {
$evenCount = 0;
$oddCount = 0;
foreach ($position as $pos) {
if ($pos % 2 == 0) {
$evenCount++;
} else {
$oddCount++;
}
}
return min($evenCount, $oddCount);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 65. Valid Number
Сложность: hard
Учитывая строку s, определите, является ли s валидным числом.
Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".
Формально, валидное число определяется с использованием одного из следующих определений:
Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.
Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:
Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.
Цифры определяются как одна или более цифр.
Пример:
👨💻 Алгоритм:
1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.
2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.
3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Учитывая строку s, определите, является ли s валидным числом.
Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".
Формально, валидное число определяется с использованием одного из следующих определений:
Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.
Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:
Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.
Цифры определяются как одна или более цифр.
Пример:
Input: s = "0"
Output: true
👨💻 Алгоритм:
1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.
2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.
3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.
😎 Решение:
function isNumber($s) {
$seenDigit = false;
$seenExponent = false;
$seenDot = false;
for ($i = 0; $i < strlen($s); $i++) {
$curr = $s[$i];
if (is_numeric($curr)) {
$seenDigit = true;
} elseif ($curr === "+" || $curr === "-") {
if ($i > 0 && $s[$i - 1] !== "e" && $s[$i - 1] !== "E") {
return false;
}
} elseif ($curr === "e" || $curr === "E") {
if ($seenExponent || !$seenDigit) {
return false;
}
$seenExponent = true;
$seenDigit = false; // Reset seenDigit after an exponent
} elseif ($curr === ".") {
if ($seenDot || $seenExponent) {
return false;
}
$seenDot = true;
} else {
return false;
}
}
return $seenDigit;
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 599. Minimum Index Sum of Two Lists
Сложность: Easy
Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.
Общая строка - это строка, которая появляется и в list1, и в list2.
Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.
Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.
Пример:
👨💻 Алгоритм:
1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.
2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.
3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: Easy
Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.
Общая строка - это строка, которая появляется и в list1, и в list2.
Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.
Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.
Пример:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
👨💻 Алгоритм:
1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.
2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.
3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.
😎 Решение:
class Solution {
function findRestaurant($list1, $list2) {
$map = [];
for ($i = 0; $i < count($list1); $i++) {
for ($j = 0; $j < count($list2); $j++) {
if ($list1[$i] == $list2[$j]) {
if (!isset($map[$i + $j])) {
$map[$i + $j] = [];
}
$map[$i + $j][] = $list1[$i];
}
}
}
$minIndexSum = min(array_keys($map));
return $map[$minIndexSum];
}
}Ставь 👍 и забирай 📚 Базу знаний
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
Задача: 169. Majority Element
Сложность: easy
Дан массив nums размера n, верните элемент большинства.
Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.
Пример:
👨💻 Алгоритм:
1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.
2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.
3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан массив nums размера n, верните элемент большинства.
Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.
Пример:
Input: nums = [3,2,3]
Output: 3
👨💻 Алгоритм:
1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.
2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.
3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋
😎 Решение:
function majorityElement($nums) {
$counts = [];
foreach ($nums as $num) {
if (!isset($counts[$num])) {
$counts[$num] = 1;
} else {
$counts[$num]++;
}
}
foreach ($counts as $num => $count) {
if ($count > count($nums) / 2) {
return $num;
}
}
return 0;
}Ставь 👍 и забирай 📚 Базу знаний