PHP | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:1 355
Підписники
-124 години
-67 днів
-1030 день
Архів дописів
1 355
Задача: 78. Subsets
Сложность: medium
Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).
Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.
Пример:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]👨💻 Алгоритм: 1⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов. 2⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод. 3⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr. 😎 Решение:
function subsets($nums) {
$output = [];
$n = count($nums);
function backtrack($first, $curr, $k, &$output, $nums, $n) {
if (count($curr) == $k) {
$output[] = $curr;
return;
}
for ($i = $first; $i < $n; $i++) {
$curr[] = $nums[$i];
backtrack($i + 1, $curr, $k, $output, $nums, $n);
array_pop($curr);
}
}
for ($k = 0; $k <= $n; $k++) {
backtrack(0, [], $k, $output, $nums, $n);
}
return $output;
}1 355
Задача: 1247. Minimum Swaps to Make Strings Equal
Сложность: hard
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
Input: arr = [1,2] Output: 2👨💻 Алгоритм: 1⃣Подсчет несоответствующих пар: Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'. 2⃣Проверка четности: Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1. 3⃣Вычисление минимального количества замен: Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2. Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2. 😎 Решение:
function minimumSwap($s1, $s2) {
$xy = 0;
$yx = 0;
for ($i = 0; $i < strlen($s1); $i++) {
if ($s1[$i] === 'x' && $s2[$i] === 'y') {
$xy++;
} else if ($s1[$i] === 'y' && $s2[$i] === 'x') {
$yx++;
}
}
if (($xy + $yx) % 2 != 0) {
return -1;
}
return intdiv($xy, 2) + intdiv($yx, 2) + ($xy % 2) * 2;
}1 355
Задача: 382. Linked List Random Node
Сложность: medium
Дан односвязный список, вернуть значение случайного узла из списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.
Реализуйте класс Solution:
Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.
Пример:
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.class ListNode {
public $val;
public $next;
public function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
private $range = array();
public function __construct($head) {
while ($head !== null) {
$this->range[] = $head->val;
$head = $head->next;
}
}
public function getRandom() {
$pick = rand(0, count($this->range) - 1);
return $this->range[$pick];
}
}
?>1 355
Задача: 130. Surrounded Regions
Сложность: Medium
Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:
Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.
Пример:
Input: board = [["X"]] Output: [["X"]]👨💻 Алгоритм: 1⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:
function solve(&$board) {
if ($board == null || count($board) == 0) {
return;
}
$ROWS = count($board);
$COLS = count($board[0]);
$borders = [];
for ($r = 0; $r < $ROWS; ++$r) {
array_push($borders, [$r, 0], [$r, $COLS - 1]);
}
for ($c = 0; $c < $COLS; ++$c) {
array_push($borders, [0, $c], [$ROWS - 1, $c]);
}
foreach ($borders as $pair) {
dfs($board, $pair[0], $pair[1]);
}
for ($r = 0; $r < $ROWS; ++$r) {
for ($c = 0; $c < $COLS; ++$c) {
if ($board[$r][$c] == "O") $board[$r][$c] = "X";
if ($board[$r][$c] == "E") $board[$r][$c] = "O";
}
}
}
function dfs(&$board, $row, $col) {
if ($board[$row][$col] != "O") return;
$board[$row][$col] = "E";
$ROWS = count($board);
$COLS = count($board[0]);
if ($col < $COLS - 1) dfs($board, $row, $col + 1);
if ($row < $ROWS - 1) dfs($board, $row + 1, $col);
if ($col > 0) dfs($board, $row, $col - 1);
if ($row > 0) dfs($board, $row - 1, $col);
}1 355
Задача: 675. Cut Off Trees for Golf Event
Сложность: hard
Есть лес в виде матрицы. В каждой ячейке:
0 — непроходимо
1 — проходимо
>1 — дерево (высота = значение)
Нужно срубить все деревья в порядке возрастания высоты, начиная с (0, 0), минимизируя количество шагов. Если добраться до какого-то дерева невозможно — вернуть -1.
Пример:
Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.function cutOffTree($forest) {
$trees = [];
$rows = count($forest);
$cols = count($forest[0]);
for ($r = 0; $r < $rows; $r++) {
for ($c = 0; $c < $cols; $c++) {
if ($forest[$r][$c] > 1) {
$trees[] = [$forest[$r][$c], $r, $c];
}
}
}
usort($trees, function($a, $b) {
return $a[0] - $b[0];
});
$sr = 0;
$sc = 0;
$ans = 0;
foreach ($trees as $tree) {
[$value, $tr, $tc] = $tree;
$d = dist($forest, $sr, $sc, $tr, $tc);
if ($d < 0) {
return -1;
}
$ans += $d;
$sr = $tr;
$sc = $tc;
}
return $ans;
}
function dist($forest, $sr, $sc, $tr, $tc) {
return 0;
}1 355
Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy
Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).
Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.
Пример:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"class Solution {
function valid($str1, $str2, $k) {
$len1 = strlen($str1);
$len2 = strlen($str2);
if ($len1 % $k > 0 || $len2 % $k > 0) {
return false;
} else {
$base = substr($str1, 0, $k);
$n1 = intval($len1 / $k);
$n2 = intval($len2 / $k);
return $str1 == $this->joinWords($base, $n1) && $str2 == $this->joinWords($base, $n2);
}
}
function joinWords($str, $k) {
$ans = "";
for ($i = 0; $i < $k; ++$i) {
$ans .= $str;
}
return $ans;
}
function gcdOfStrings($str1, $str2) {
$len1 = strlen($str1);
$len2 = strlen($str2);
for ($i = min($len1, $len2); $i >= 1; --$i) {
if ($this->valid($str1, $str2, $i)) {
return substr($str1, 0, $i);
}
}
return "";
}
}1 355
Задача: 291. Word Pattern II
Сложность: medium
Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.
Пример:
Input: pattern = "abab", s = "redblueredblue" Output: true Explanation: One possible mapping is as follows: 'a' -> "red" 'b' -> "blue"👨💻 Алгоритм: 1⃣Инициализация структур данных и определение рекурсивной функции: Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s. Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ. Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону. 2⃣Рекурсивная проверка соответствия: Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false. Получите символ из шаблона по индексу pIndex. Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне. 3⃣Отображение новых подстрок: Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки. Для каждой новой подстроки проверьте, существует ли она уже в ` 😎 Решение:
class Solution {
function wordPatternMatch($pattern, $s) {
$symbolMap = [];
$wordSet = [];
return $this->isMatch($s, 0, $pattern, 0, $symbolMap, $wordSet);
}
private function isMatch($s, $sIndex, $pattern, $pIndex, &$symbolMap, &$wordSet) {
if ($pIndex == strlen($pattern)) {
return $sIndex == strlen($s);
}
$symbol = $pattern[$pIndex];
if (isset($symbolMap[$symbol])) {
$word = $symbolMap[$symbol];
if (substr($s, $sIndex, strlen($word)) !== $word) {
return false;
}
return $this->isMatch($s, $sIndex + strlen($word), $pattern, $pIndex + 1, $symbolMap, $wordSet);
}
for ($k = $sIndex + 1; $k <= strlen($s); $k++) {
$newWord = substr($s, $sIndex, $k - $sIndex);
if (in_array($newWord, $wordSet)) {
continue;
}
$symbolMap[$symbol] = $newWord;
$wordSet[] = $newWord;
if ($this->isMatch($s, $k, $pattern, $pIndex + 1, $symbolMap, $wordSet)) {
return true;
}
unset($symbolMap[$symbol]);
array_pop($wordSet);
}
return false;
}
}
?>1 355
Задача: 647. Palindromic Substrings
Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "abc" Output: 3👨💻 Алгоритм: 1⃣Инициализируйте счетчик для подсчета палиндромных подстрок. 2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины. 3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется. 😎 Решение:
function countSubstrings($s) {
$totalCount = 0;
function expandAroundCenter($s, $left, $right) {
$count = 0;
while ($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
$count++;
$left--;
$right++;
}
return $count;
}
for ($i = 0; $i < strlen($s); $i++) {
$totalCount += expandAroundCenter($s, $i, $i);
$totalCount += expandAroundCenter($s, $i, $i + 1);
}
return $totalCount;
}1 355
Задача: 128. Longest Consecutive Sequence
Сложность: Medium
Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.
Необходимо написать алгоритм, который работает за время O(n).
Пример:
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.👨💻 Алгоритм: 1⃣Проверка базового случая: Перед началом работы проверяем базовый случай с пустым массивом. Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение. 2⃣Обработка чисел в массиве: Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим). Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу. Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем. 3⃣Завершение обработки и возврат результата: В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность). Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной. 😎 Решение:
function arrayContains($arr, $num) {
foreach ($arr as $item) {
if ($item === $num) {
return true;
}
}
return false;
}
function longestConsecutive($nums) {
$longestStreak = 0;
foreach ($nums as $num) {
$currentNum = $num;
$currentStreak = 1;
while (arrayContains($nums, $currentNum + 1)) {
$currentNum += 1;
$currentStreak += 1;
}
if ($currentStreak > $longestStreak) {
$longestStreak = $currentStreak;
}
}
return $longestStreak;
}1 355
Задача: 260. Single Number III
Сложность: medium
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство..
Пример:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.👨💻 Алгоритм: 1⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел. 2⃣Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы. 3⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа. 😎 Решение:
class Solution {
public function singleNumber($nums) {
$xor = 0;
foreach ($nums as $num) {
$xor ^= $num;
}
$diff = $xor & -$xor;
$res = [0, 0];
foreach ($nums as $num) {
if (($num & $diff) == 0) {
$res[0] ^= $num;
} else {
$res[1] ^= $num;
}
}
return $res;
}
}1 355
🖼️ Стажировки и вакансии для PHP разработчиков.
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
👉 @jobs_php
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
1 355
Задача: 1230. Toss Strange Coins
Сложность: medium
У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].
Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.
Пример:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125👨💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:
class Solution {
function probabilityOfHeads($prob, $target) {
$n = count($prob);
$dp = array_fill(0, $n + 1, array_fill(0, $target + 1, 0));
$dp[0][0] = 1.0;
for ($i = 1; $i <= $n; $i++) {
$dp[$i][0] = $dp[$i - 1][0] * (1 - $prob[$i - 1]);
for ($j = 1; $j <= $target; $j++) {
if ($j <= $i) {
$dp[$i][$j] = $dp[$i - 1][$j - 1] * $prob[$i - 1] + $dp[$i - 1][$j] * (1 - $prob[$i - 1]);
}
}
}
return $dp[$n][$target];
}
}1 355
Задача: 1207. Unique Number of Occurrences
Сложность: easy
Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.
Пример:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.class Solution {
/**
* @param Integer[] $arr
* @return Boolean
*/
function uniqueOccurrences($arr) {
$freq = array_count_values($arr);
$freqSet = array_unique(array_values($freq));
return count($freq) == count($freqSet);
}
}1 355
Задача: 126.Word Ladder II
Сложность: Hard
Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:
Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].
Пример:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] Explanation: There are 2 shortest transformation sequences: "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"👨💻 Алгоритм: 1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS). 2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList. 3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths. 😎 Решение:
class Solution {
function findLadders($beginWord, $endWord, $wordList) {
$adjList = [];
$wordSet = array_flip($wordList);
$this->bfs($beginWord, $endWord, $wordSet, $adjList);
$this->currPath = [$endWord];
$this->shortestPaths = [];
$this->backtrack($endWord, $beginWord, $adjList);
return $this->shortestPaths;
}
function findNeighbors($word, &$wordSet) {
$neighbors = [];
$charList = str_split($word);
for ($i = 0; $i < strlen($word); $i++) {
$oldChar = $charList[$i];
foreach (range('a', 'z') as $c) {
if ($c != $oldChar) {
$charList[$i] = $c;
$newWord = implode('', $charList);
if (isset($wordSet[$newWord])) {
$neighbors[] = $newWord;
}
}
}
$charList[$i] = $oldChar;
}
return $neighbors;
}
function backtrack($source, $destination, &$adjList) {
if ($source == $destination) {
$this->shortestPaths[] = array_reverse($this->currPath);
} else if (isset($adjList[$source])) {
foreach ($adjList[$source] as $neighbor) {
array_push($this->currPath, $neighbor);
$this->backtrack($neighbor, $destination, $adjList);
array_pop($this->currPath);
}
}
}
function bfs($beginWord, $endWord, &$wordSet, &$adjList) {
$queue = [$beginWord];
unset($wordSet[$beginWord]);
while ($queue) {
$currentWord = array_shift($queue);
$neighbors = $this->findNeighbors($currentWord, $wordSet);
foreach ($neighbors as $neighbor) {
$adjList[$neighbor][] = $currentWord;
if (isset($wordSet[$neighbor])) {
unset($wordSet[$neighbor]);
$queue[] = $neighbor;
}
}
}
}
}1 355
Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium
Вам дан корень бинарного дерева.
Зигзагообразный путь для бинарного дерева определяется следующим образом:
Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).
Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Рекурсивная функция DFS: Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо). 2⃣Обновление максимальной длины пути: При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума. 3⃣Рекурсивный вызов для левого и правого дочерних узлов: Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления. 😎 Решение:
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 $maxLength = 0;
function longestZigZag($root) {
$this->dfs($root, true, 0);
$this->dfs($root, false, 0);
return $this->maxLength;
}
private function dfs($node, $isLeft, $length) {
if ($node === null) return;
$this->maxLength = max($this->maxLength, $length1 355
Задача: 1057. Campus Bikes
Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: [1,0]👨💻 Алгоритм: 1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список. 2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда. Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы. 3⃣Заполни и верни массив назначений. 😎 Решение:
function assignBikes($workers, $bikes) {
$pairs = [];
for ($i = 0; $i < count($workers); $i++) {
for ($j = 0; $j < count($bikes); $j++) {
$distance = abs($workers[$i][0] - $bikes[$j][0]) + abs($workers[$i][1] - $bikes[$j][1]);
$pairs[] = [$distance, $i, $j];
}
}
usort($pairs, function($a, $b) {
if ($a[0] !== $b[0]) return $a[0] - $b[0];
if ($a[1] !== $b[1]) return $a[1] - $b[1];
return $a[2] - $b[2];
});
$result = array_fill(0, count($workers), -1);
$bikeTaken = array_fill(0, count($bikes), false);
$workerAssigned = array_fill(0, count($workers), false);
foreach ($pairs as [$distance, $workerIdx, $bikeIdx]) {
if (!$workerAssigned[$workerIdx] && !$bikeTaken[$bikeIdx]) {
$result[$workerIdx] = $bikeIdx;
$bikeTaken[$bikeIdx] = true;
$workerAssigned[$workerIdx] = true;
}
}
return $result;
}1 355
📺 База 1000+ реальных собеседований
На программиста, тестировщика, аналитика, проджекта и другие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 355
Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium
Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length). 2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k. 3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки. 😎 Решение:
class Solution {
function lengthOfLongestSubstringKDistinct($s, $k) {
$left = 0;
$right = 0;
$charCount = [];
$maxLength = 0;
while ($right < strlen($s)) {
$charCount[$s[$right]] = ($charCount[$s[$right]] ?? 0) + 1;
while (count($charCount) > $k) {
$charCount[$s[$left]]--;
if ($charCount[$s[$left]] == 0) {
unset($charCount[$s[$left]]);
}
$left++;
}
$maxLength = max($maxLength, $right - $left + 1);
$right++;
}
return $maxLength;
}
}1 355
Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard
Дан бинарный массив nums и целое число k.
Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.
Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1.
Подмассив - это непрерывная часть массива.
Пример:
Input: nums = [0,1,0], k = 1 Output: 2 Explanation: Flip nums[0], then flip nums[2].👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив flip, чтобы отслеживать, сколько раз был перевернут каждый элемент. Инициализируйте flips для отслеживания количества текущих переворотов. 2⃣Перебор элементов массива: Для каждого элемента определите, необходимо ли его переворачивать, учитывая текущее количество переворотов и значение в массиве. Если нужно перевернуть, увеличьте счетчик переворотов и обновите массив flip. 3⃣Проверка возможности выполнения задачи: Если количество переворотов больше длины массива, верните -1. 😎 Решение:
class Solution {
function minKBitFlips($nums, $k) {
$n = count($nums);
$flip = 0;
$flips = 0;
$flipQueue = array_fill(0, $n, 0);
for ($i = 0; $i < $n; $i++) {
if ($i >= $k) {
$flip ^= $flipQueue[$i - $k];
}
if ($nums[$i] == $flip) {
if ($i + $k > $n) return -1;
$flips++;
$flip ^= 1;
$flipQueue[$i] = 1;
}
}
return $flips;
}
}1 355
Задача: 598. Range Addition II
Сложность: Easy
Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.
Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.
Пример:
Input: m = 3, n = 3, ops = [[2,2],[3,3]] Output: 4 Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.👨💻 Алгоритм: 1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j). 2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])). 3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y. 😎 Решение:
class Solution {
function maxCount($m, $n, $ops) {
$minA = $m;
$minB = $n;
foreach ($ops as $op) {
$minA = min($minA, $op[0]);
$minB = min($minB, $op[1]);
}
return $minA * $minB;
}
}