Задача: 278. First Bad Version
Сложность: easy
Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими.
Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.
Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.
Пример:
👨💻 Алгоритм:
1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.
2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.
3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими.
Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.
Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.
Пример:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
👨💻 Алгоритм:
1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.
2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.
3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.
😎 Решение:
class Solution {
public function firstBadVersion($n) {
$left = 1;
$right = $n;
while ($left < $right) {
$mid = $left + (int)(($right - $left) / 2);
if ($this->isBadVersion($mid)) {
$right = $mid;
} else {
$left = $mid + 1;
}
}
return $left;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1231. Divide Chocolate
Сложность: hard
У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.
Пример:
👨💻 Алгоритм:
1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить.
2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.
3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.
Пример:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
👨💻 Алгоритм:
1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить.
2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.
3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.
😎 Решение:
function maximizeSweetness($sweetness, $k) {
$canDivide = function($minSweetness) use ($sweetness, $k) {
$currentSum = 0;
$cuts = 0;
foreach ($sweetness as $sweet) {
$currentSum += $sweet;
if ($currentSum >= $minSweetness) {
$cuts++;
$currentSum = 0;
}
}
return $cuts >= $k + 1;
};
$left = min($sweetness);
$right = intdiv(array_sum($sweetness), $k + 1);
while ($left < $right) {
$mid = intdiv($left + $right + 1, 2);
if ($canDivide($mid)) {
$left = $mid;
} else {
$right = $mid - 1;
}
}
return $left;
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 446. Arithmetic Slices II - Subsequence
Сложность: hard
Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.
Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.
Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.
Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.
Пример:
👨💻 Алгоритм:
1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.
2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.
3⃣Возвращаем количество всех арифметических подпоследовательностей.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.
Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.
Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.
Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.
Пример:
Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
👨💻 Алгоритм:
1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.
2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.
3⃣Возвращаем количество всех арифметических подпоследовательностей.
😎 Решение:
class Solution {
private $n;
private $ans;
private function dfs($dep, $A, $cur) {
if ($dep == $this->n) {
if (count($cur) < 3) return;
for ($i = 1; $i < count($cur); $i++) {
if ($cur[$i] - $cur[$i - 1] != $cur[1] - $cur[0]) return;
}
$this->ans++;
return;
}
$this->dfs($dep + 1, $A, $cur);
array_push($cur, $A[$dep]);
$this->dfs($dep + 1, $A, $cur);
}
public function numberOfArithmeticSlices($A) {
$this->n = count($A);
$this->ans = 0;
$this->dfs(0, $A, []);
return $this->ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 28. Find the Index of the First Occurrence in a String
Сложность: easy
Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.
Пример:
👨💻 Алгоритм:
1⃣Определяем длины строки
2⃣Используем
3⃣Если совпадение найдено, возвращаем индекс, иначе продолжаем поиск, пока не достигнем конца
😎Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.
Пример:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
👨💻 Алгоритм:
1⃣Определяем длины строки
needle и haystack, начинаем поиск с нулевого индекса. 2⃣Используем
substr для извлечения подстроки из haystack и проверяем на совпадение с needle. 3⃣Если совпадение найдено, возвращаем индекс, иначе продолжаем поиск, пока не достигнем конца
haystack. 😎Решение:
class Solution {
/**
* @param String $haystack
* @param String $needle
* @return Integer
*/
function strStr($haystack, $needle) {
$needleLen = strlen($needle);
$haylen = strlen($haystack);
$start = 0;
while (true) {
$substring = substr($haystack, $start, $needleLen);
if ($substring == $needle) {
return $start;
}
if ($start == $haylen-1) {
return -1;
}
$start++;
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача №19. Remove Nth Node From End of List
Сложность: medium
Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.
Пример:
👨💻 Алгоритм:
1⃣Определить длину списка, пройдясь по нему один раз.
2⃣Найти узел, предшествующий удаляемому, используя второй проход.
3⃣Изменить ссылки, чтобы удалить целевой узел.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.
Пример:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
👨💻 Алгоритм:
1⃣Определить длину списка, пройдясь по нему один раз.
2⃣Найти узел, предшествующий удаляемому, используя второй проход.
3⃣Изменить ссылки, чтобы удалить целевой узел.
😎 Решение:
class Solution {
function removeNthFromEnd($head, $n) {
$tamaño = 0;
$aux = $head;
while ($aux !== null) {
$aux = $aux->next;
$tamaño++;
}
if ($tamaño == 1) {
return null;
}
if ($tamaño == $n) {
return $head->next;
}
$aux = $head;
for ($i = 0; $i < $tamaño - $n - 1; $i++) {
$aux = $aux->next;
}
$aux->next = $aux->next->next;
return $head;
}
}Ставь 👍 и забирай 📚 Базу знаний
🤔1
Задача: 1146. Snapshot Array
Сложность: medium
Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.
Пример:
👨💻 Алгоритм:
1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].
2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].
3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.
Пример:
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5); // Set array[0] = 5
snapshotArr.snap(); // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
👨💻 Алгоритм:
1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].
2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].
3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].
😎 Решение:
class SnapshotArray {
private $snapId;
private $historyRecords;
function __construct($length) {
$this->snapId = 0;
$this->historyRecords = array_fill(0, $length, [0 => 0]);
}
function set($index, $val) {
$this->historyRecords[$index][$this->snapId] = $val;
}
function snap() {
$this->snapId++;
return $this->snapId - 1;
}
function get($index, $snapId) {
while ($snapId >= 0) {
if (isset($this->historyRecords[$index][$snapId])) {
return $this->historyRecords[$index][$snapId];
}
$snapId--;
}
return 0;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1265. Print Immutable Linked List in Reverse
Сложность: medium
Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.
Пример:
👨💻 Алгоритм:
1⃣Используйте рекурсию для достижения конца связного списка.
2⃣На обратном пути рекурсии распечатайте значение каждого узла.
3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.
Пример:
Input: head = [1,2,3,4]
Output: [4,3,2,1]
👨💻 Алгоритм:
1⃣Используйте рекурсию для достижения конца связного списка.
2⃣На обратном пути рекурсии распечатайте значение каждого узла.
3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов).
😎 Решение:
interface ImmutableListNode {
public function printValue();
public function getNext();
}
class Solution {
function printLinkedListInReverse($head) {
if ($head->getNext() !== null) {
$this->printLinkedListInReverse($head->getNext());
}
$head->printValue();
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard
Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.
Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.
2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.
3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.
Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.
Пример:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]
👨💻 Алгоритм:
1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.
2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.
3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.
😎 Решение:
class Solution {
function sortItems($n, $m, $group, $beforeItems) {
$groupId = $m;
for ($i = 0; $i < $n; $i++) if ($group[$i] == -1) $group[$i] = $groupId++;
$itemGraph = array_fill(0, $n, []);
$groupGraph = array_fill(0, $groupId, []);
$itemIndegree = array_fill(0, $n, 0);
$groupIndegree = array_fill(0, $groupId, 0);
for ($curr = 0; $curr < $n; $curr++) {
foreach ($beforeItems[$curr] as $prev) {
$itemGraph[$prev][] = $curr;
$itemIndegree[$curr]++;
if ($group[$curr] != $group[$prev]) {
$groupGraph[$group[$prev]][] = $group[$curr];
$groupIndegree[$group[$curr]]++;
}
}
}
$itemOrder = $this->topologicalSort($itemGraph, $itemIndegree);
$groupOrder = $this->topologicalSort($groupGraph, $groupIndegree);
if (empty($itemOrder) || empty($groupOrder)) return [];
$orderedGroups = [];
foreach ($itemOrder as $item) {
$orderedGroups[$group[$item]][] = $item;
}
$answerList = [];
foreach ($groupOrder as $groupIndex) {
if (isset($orderedGroups[$groupIndex])) $answerList = array_merge($answerList, $orderedGroups[$groupIndex]);
}
return $answerList;
}
function topologicalSort($graph, $indegree) {
$visited = [];
$stack = [];
foreach ($graph as $key => $value) if ($indegree[$key] == 0) $stack[] = $key;
while (!empty($stack)) {
$curr = array_pop($stack);
$visited[] = $curr;
foreach ($graph[$curr] as $next) {
$indegree[$next]--;
if ($indegree[$next] == 0) $stack[] = $next;
}
}
return count($visited) == count($graph) ? $visited : [];
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 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;
}Ставь 👍 и забирай 📚 Базу знаний