Задача: 821. Shortest Distance to a Character
Сложность: easy
Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.
Пример:
👨💻 Алгоритм:
1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.
2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.
3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.
Пример:
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.
👨💻 Алгоритм:
1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.
2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.
3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.
😎 Решение:
class Solution {
function shortestToChar($S, $C) {
$N = strlen($S);
$ans = array_fill(0, $N, PHP_INT_MAX);
$prev = -$N;
for ($i = 0; $i < $N; ++$i) {
if ($S[$i] == $C) {
$prev = $i;
}
$ans[$i] = $i - $prev;
}
$prev = 2 * $N;
for ($i = $N - 1; $i >= 0; --$i) {
if ($S[$i] == $C) {
$prev = $i;
}
$ans[$i] = min($ans[$i], $prev - $i);
}
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 924. Minimize Malware Spread
Сложность: hard
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.
Пример:
👨💻 Алгоритм:
1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.
2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.
3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.
Пример:
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
👨💻 Алгоритм:
1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.
2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.
3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.
😎 Решение:
function minMalwareSpread($graph, $initial) {
function dfs($graph, $node, &$infected) {
for ($neighbor = 0; $neighbor < count($graph); $neighbor++) {
if ($graph[$node][$neighbor] == 1 && !in_array($neighbor, $infected)) {
$infected[] = $neighbor;
dfs($graph, $neighbor, $infected);
}
}
}
$n = count($graph);
$initialSet = $initial;
sort($initial);
$minInfected = PHP_INT_MAX;
$bestNode = $initial[0];
foreach ($initial as $node) {
$infected = $initialSet;
$infected = array_diff($infected, [$node]);
foreach ($initialSet as $i) {
if ($i != $node) {
dfs($graph, $i, $infected);
}
}
if (count($infected) < $minInfected) {
$minInfected = count($infected);
$bestNode = $node;
}
}
return $bestNode;
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1024. Video Stitching
Сложность: medium
Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.
2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.
3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.
Пример:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
👨💻 Алгоритм:
1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.
2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.
3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.
😎 Решение:
class Solution {
function videoStitching($clips, $T) {
usort($clips, function($a, $b) {
return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
});
$end = -1;
$end2 = 0;
$res = 0;
foreach ($clips as $clip) {
if ($end2 >= $T || $clip[0] > $end2) break;
if ($end < $clip[0] && $clip[0] <= $end2) {
$res++;
$end = $end2;
}
$end2 = max($end2, $clip[1]);
}
return $end2 >= $T ? $res : -1;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 166. Fraction to Recurring Decimal
Сложность: medium
Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.
Пример:
👨💻 Алгоритм:
1⃣Использование хеш-таблицы для отслеживания остатков:
Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части.
Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее.
2⃣Обработка нулевого остатка:
Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать.
3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.
Пример:
Input: numerator = 1, denominator = 2
Output: "0.5"
👨💻 Алгоритм:
1⃣Использование хеш-таблицы для отслеживания остатков:
Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части.
Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее.
2⃣Обработка нулевого остатка:
Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать.
3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.
😎 Решение:
class Solution {
function fractionToDecimal($numerator, $denominator) {
if ($numerator == 0) {
return "0";
}
$fraction = "";
if (($numerator < 0) xor ($denominator < 0)) {
$fraction .= "-";
}
$dividend = abs($numerator);
$divisor = abs($denominator);
$fraction .= intval($dividend / $divisor);
$remainder = $dividend % $divisor;
if ($remainder == 0) {
return $fraction;
}
$fraction .= ".";
$lookup = [];
while ($remainder != 0) {
if (isset($lookup[$remainder])) {
$pos = $lookup[$remainder];
$fraction = substr($fraction, 0, $pos) . "(" . substr($fraction, $pos) . ")";
break;
}
$lookup[$remainder] = strlen($fraction);
$remainder *= 10;
$fraction .= intval($remainder / $divisor);
$remainder %= $divisor;
}
return $fraction;
}
}Ставь 👍 и забирай 📚 Базу знаний
🔥 Скрытые вакансии с удаленной работой для PHP разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 PHP Jobs | Вакансии
🔸 Все каналы с вакансиями
🔹 PHP Jobs | Вакансии
🔸 Все каналы с вакансиями
Задача: 71. Simplify Path
Сложность: medium
Дан абсолютный путь для файловой системы в стиле Unix, который начинается с символа '/'. Преобразуйте этот путь в его упрощенный канонический путь.
В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов.
Упрощенный канонический путь должен соответствовать следующим правилам:
Он должен начинаться с одного слэша '/'.
Каталоги в пути должны быть разделены только одним слэшем '/'.
Он не должен заканчиваться слэшем '/', если только это не корневой каталог.
Он должен исключать любые одинарные или двойные точки, используемые для обозначения текущих или родительских каталогов.
Верните новый путь.
Пример:
👨💻 Алгоритм:
1⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их.
2⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст.
3⃣Наконец, если обрабатываемый нами в данный момент компонент не является одним из специальных символов, мы просто добавляем его в наш стек, так как это законное имя каталога. Как только все компоненты обработаны, нам просто нужно соединить все имена каталогов в нашем стеке, используя '/' в качестве разделителя, и мы получим самый короткий путь, который приведет нас в тот же каталог, что и предоставленный на входе.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан абсолютный путь для файловой системы в стиле Unix, который начинается с символа '/'. Преобразуйте этот путь в его упрощенный канонический путь.
В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов.
Упрощенный канонический путь должен соответствовать следующим правилам:
Он должен начинаться с одного слэша '/'.
Каталоги в пути должны быть разделены только одним слэшем '/'.
Он не должен заканчиваться слэшем '/', если только это не корневой каталог.
Он должен исключать любые одинарные или двойные точки, используемые для обозначения текущих или родительских каталогов.
Верните новый путь.
Пример:
Input: path = "/home/"
Output: "/home"
Explanation:
The trailing slash should be removed.
👨💻 Алгоритм:
1⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их.
2⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст.
3⃣Наконец, если обрабатываемый нами в данный момент компонент не является одним из специальных символов, мы просто добавляем его в наш стек, так как это законное имя каталога. Как только все компоненты обработаны, нам просто нужно соединить все имена каталогов в нашем стеке, используя '/' в качестве разделителя, и мы получим самый короткий путь, который приведет нас в тот же каталог, что и предоставленный на входе.
😎 Решение:
function simplifyPath($path) {
$stack = [];
$portions = explode("/", $path);
foreach ($portions as $portion) {
if ($portion === "..") {
if (!empty($stack)) {
array_pop($stack);
}
} elseif ($portion !== "." && $portion !== "") {
array_push($stack, $portion);
}
}
return "/" . implode("/", $stack);
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 913. Cat and Mouse4
Сложность: hard
В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.
Пример:
👨💻 Алгоритм:
1⃣Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока.
2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).
3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.
Пример:
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
👨💻 Алгоритм:
1⃣Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока.
2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).
3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.
😎 Решение:
function catMouseGame($graph) {
$n = count($graph);
$DRAW = 0; $MOUSE = 1; $CAT = 2;
$dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2, $DRAW)));
$queue = [];
for ($i = 1; $i < $n; $i++) {
$dp[0][$i][0] = $MOUSE;
$dp[0][$i][1] = $MOUSE;
$dp[$i][$i][0] = $CAT;
$dp[$i][$i][1] = $CAT;
$queue[] = [0, $i, 0, $MOUSE];
$queue[] = [0, $i, 1, $MOUSE];
$queue[] = [$i, $i, 0, $CAT];
$queue[] = [$i, $i, 1, $CAT];
}
function parents($graph, $mouse, $cat, $turn) {
$res = [];
if ($turn == 1) {
foreach ($graph[$mouse] as $m) {
$res[] = [$m, $cat, 0];
}
} else {
foreach ($graph[$cat] as $c) {
if ($c > 0) $res[] = [$mouse, $c, 1];
}
}
return $res;
}
while (!empty($queue)) {
list($mouse, $cat, $turn, $winner) = array_shift($queue);
foreach (parents($graph, $mouse, $cat, $turn) as list($m, $c, $t)) {
if ($dp[$m][$c][$t] == $DRAW) {
if (($t == 0 && $winner == $MOUSE) || ($t == 1 && $winner == $CAT)) {
$dp[$m][$c][$t] = $winner;
$queue[] = [$m, $c, $t, $winner];
} else {
$degrees = 0;
foreach (parents($graph, $m, $c, $t) as $_) $degrees++;
if ($degrees == 0) {
$dp[$m][$c][$t] = $winner;
$queue[] = [$m, $c, $t, $winner];
}
}
}
}
}
return $dp[1][2][0];
}Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 899. Orderly Queue
Сложность: hard
Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов.
Пример:
👨💻 Алгоритм:
1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.
2⃣Если k больше 1, отсортировать строку, так как любое количество перемещений позволит упорядочить все символы в строке.
3⃣Вернуть результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов.
Пример:
Input: s = "cba", k = 1
Output: "acb"
👨💻 Алгоритм:
1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.
2⃣Если k больше 1, отсортировать строку, так как любое количество перемещений позволит упорядочить все символы в строке.
3⃣Вернуть результат.
😎 Решение:
function orderlyQueue($s, $k) {
if ($k == 1) {
$minString = $s;
for ($i = 1; $i < strlen($s); $i++) {
$rotated = substr($s, $i) . substr($s, 0, $i);
if ($rotated < $minString) {
$minString = $rotated;
}
}
return $minString;
} else {
$sArray = str_split($s);
sort($sArray);
return implode('', $sArray);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy
Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.
Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].
Пример:
👨💻 Алгоритм:
1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.
2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.
3⃣Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.
Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].
Пример:
Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.
👨💻 Алгоритм:
1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.
2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.
3⃣Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности.
😎 Решение:
class Solution {
function findLengthOfLCIS($nums) {
$ans = 0;
$anchor = 0;
for ($i = 0; $i < count($nums); ++$i) {
if ($i > 0 && $nums[$i - 1] >= $nums[$i]) {
$anchor = $i;
}
$ans = max($ans, $i - $anchor + 1);
}
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 724. Find Pivot Index
Сложность: easy
Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.
Пример:
👨💻 Алгоритм:
1⃣Вычислите сумму всех элементов массива.
2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа.
3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.
Пример:
Input: nums = [1,7,3,6,5,6]
Output: 3
👨💻 Алгоритм:
1⃣Вычислите сумму всех элементов массива.
2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа.
3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.
😎 Решение:
function pivotIndex($nums) {
$totalSum = array_sum($nums);
$leftSum = 0;
foreach ($nums as $i => $num) {
if ($leftSum == $totalSum - $leftSum - $num) {
return $i;
}
$leftSum += $num;
}
return -1;
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1273. Delete Tree Nodes
Сложность: medium
Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.
Пример:
👨💻 Алгоритм:
1⃣Постройте дерево из заданных узлов, значений и родителей.
2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю.
3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.
Пример:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2
👨💻 Алгоритм:
1⃣Постройте дерево из заданных узлов, значений и родителей.
2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю.
3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.
😎 Решение:
function deleteTreeNodes($nodes, $parent, $value) {
$tree = [];
for ($i = 0; $i < $nodes; $i++) {
if (!isset($tree[$parent[$i]])) $tree[$parent[$i]] = [];
$tree[$parent[$i]][] = $i;
}
function dfs($node, &$tree, &$value) {
$totalSum = $value[$node];
$totalCount = 1;
if (isset($tree[$node])) {
foreach ($tree[$node] as $child) {
list($childSum, $childCount) = dfs($child, $tree, $value);
$totalSum += $childSum;
$totalCount += $childCount;
}
}
return $totalSum == 0 ? [0, 0] : [$totalSum, $totalCount];
}
return dfs(0, $tree, $value)[1];
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 474. Ones and Zeroes
Сложность: medium
Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.
Пример:
👨💻 Алгоритм:
1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
2⃣Считаем количество нулей и единиц в каждом подмножестве.
3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.
Пример:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
👨💻 Алгоритм:
1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
2⃣Считаем количество нулей и единиц в каждом подмножестве.
3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
class Solution {
function findMaxForm($strs, $m, $n) {
$maxlen = 0;
for ($i = 0; $i < (1 << count($strs)); $i++) {
$zeroes = 0;
$ones = 0;
$len = 0;
for ($j = 0; $j < 32; $j++) {
if (($i & (1 << $j)) != 0) {
$count = $this->countZeroesOnes($strs[$j]);
$zeroes += $count[0];
$ones += $count[1];
if ($zeroes > $m || $ones > $n)
break;
$len++;
}
}
if ($zeroes <= $m && $ones <= $n)
$maxlen = max($maxlen, $len);
}
return $maxlen;
}
function countZeroesOnes($s) {
$c = array(0, 0);
for ($i = 0; $i < strlen($s); $i++) {
$c[$s[$i] - '0']++;
}
return $c;
}
}Ставь 👍 и забирай 📚 Базу знаний