PHP | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
شبکه:1 324
مشترکین
-224 ساعت
-47 روز
-2030 روز
آرشیو پست ها
1 322
Задача: 148. Sort List
Сложность: Medium
Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.
Пример:
Input: head = [4,2,1,3] Output: [1,2,3,4]👨💻 Алгоритм: 1⃣Разделение списка (Фаза разделения): Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка. 2⃣Сортировка подсписков и их объединение (Фаза слияния): Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков. 3⃣Иллюстрация процесса сортировки: Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список. 😎 Решение:
class ListNode {
public $val;
public $next;
public function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
public function sortList($head) {
if ($head === null || $head->next === null) {
return $head;
}
$mid = $this->getMid($head);
$left = $this->sortList($head);
$right = $this->sortList($mid);
return $this->merge($left, $right);
}
private function merge($list1, $list2) {
$dummyHead = new ListNode();
$tail = $dummyHead;
while ($list1 !== null && $list2 !== null) {
if ($list1->val < $list2->val) {
$tail->next = $list1;
$list1 = $list1->next;
} else {
$tail->next = $list2;
$list2 = $list2->next;
}
$tail = $tail->next;
}
$tail->next = $list1 ?? $list2;
return $dummyHead->next;
}
private function getMid($head) {
$midPrev = null;
$slow = $head;
$fast = $head;
while ($fast !== null && $fast->next !== null) {
$midPrev = ($midPrev === null) ? $slow : $midPrev->next;
$slow = $slow->next;
$fast = $fast->next->next;
}
$mid = $midPrev->next;
$midPrev->next = null;
return $mid;
}
}1 322
Задача: 366. Find Leaves of Binary Tree
Сложность: medium
Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.
Пример:
Input: root = [1,2,3,4,5] Output: [[4,5,3],[2],[1]] Explanation: [[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.👨💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:
class Solution {
private $pairs = [];
private function getHeight($node) {
if ($node === null) return -1;
$leftHeight = $this->getHeight($node->left);
$rightHeight = $this->getHeight($node->right);
$currHeight = max($leftHeight, $rightHeight) + 1;
$this->pairs[] = [$currHeight, $node->val];
return $currHeight;
}
public function findLeaves($root) {
$this->getHeight($root);
usort($this->pairs, function($a, $b) {
return $a[0] <=> $b[0];
});
$solution = [];
$currentHeight = -1;
foreach ($this->pairs as $pair) {
if ($pair[0] !== $currentHeight) {
$solution[] = [];
$currentHeight = $pair[0];
}
$solution[count($solution) - 1][] = $pair[1];
}
return $solution;
}
}1 322
Задача: 908. Smallest Range I
Сложность: easy
Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.
Пример:
Input: nums = [1], k = 0 Output: 0👨💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:
function smallestRangeI($nums, $k) {
$minVal = min($nums);
$maxVal = max($nums);
return max(0, ($maxVal - $k) - ($minVal + $k));
}1 322
Задача: 358. Rearrange String k Distance Apart
Сложность: hard
Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".
Пример:
Input: s = "aabbcc", k = 3 Output: "abcabc" Explanation: The same letters are at least a distance of 3 from each other.👨💻 Алгоритм: 1⃣Создайте словарь частот для символов строки и определите максимальную частоту. 2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов. 3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку. 😎 Решение:
class Solution {
function rearrangeString($s, $k) {
$freqs = [];
$maxFreq = 0;
for ($i = 0; $i < strlen($s); $i++) {
$char = $s[$i];
if (!isset($freqs[$char])) {
$freqs[$char] = 0;
}
$freqs[$char]++;
$maxFreq = max($maxFreq, $freqs[$char]);
}
$mostChars = [];
$secondChars = [];
foreach ($freqs as $char => $freq) {
if ($freq == $maxFreq) {
$mostChars[] = $char;
} else if ($freq == $maxFreq - 1) {
$secondChars[] = $char;
}
}
$segments = array_fill(0, $maxFreq, "");
for ($i = 0; $i < $maxFreq; $i++) {
foreach ($mostChars as $char) {
$segments[$i] .= $char;
}
if ($i < $maxFreq - 1) {
foreach ($secondChars as $char) {
$segments[$i] .= $char;
}
}
}
$segmentId = 0;
foreach ($freqs as $char => $freq) {
if (in_array($char, $mostChars) || in_array($char, $secondChars)) {
continue;
}
for ($j = 0; $j < $freq; $j++) {
$segments[$segmentId] .= $char;
$segmentId = ($segmentId + 1) % ($maxFreq - 1);
}
}
for ($i = 0; $i < $maxFreq - 1; $i++) {
if (strlen($segments[$i]) < $k) {
return "";
}
}
return implode("", $segments);
}
}1 322
Задача: 1044. Longest Duplicate Substring
Сложность: hard
Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".
Пример:
Input: s = "banana" Output: "ana"👨💻 Алгоритм: 1⃣Использование двоичного поиска для определения длины дублированной подстроки: Двоичный поиск используется для поиска максимальной длины дублированной подстроки. 2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины: Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок. 3⃣Хеширование с помощью функции rolling hash: Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов. 😎 Решение:
function longestDupSubstring($s) {
function search($s, $length) {
$seen = [];
for ($i = 0; $i <= strlen($s) - $length; $i++) {
$sub = substr($s, $i, $length);
if (isset($seen[$sub])) {
return $sub;
}
$seen[$sub] = true;
}
return "";
}
$left = 1;
$right = strlen($s);
$result = "";
while ($left < $right) {
$mid = intdiv($left + $right, 2);
$dup = search($s, $mid);
if ($dup !== "") {
$result = $dup;
$left = $mid + 1;
} else {
$right = $mid;
}
}
return $result;
}1 322
Задача: 189. Rotate Array
Сложность: medium
Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.
Пример:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]👨💻 Алгоритм: 1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива. 2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов. 3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива. 😎 Решение:
class Solution {
function rotate(&$nums, $k) {
$n = count($nums);
$a = array_fill(0, $n, 0);
for ($i = 0; $i < $n; $i++) {
$a[($i + $k) % $n] = $nums[$i];
}
for ($i = 0; $i < $n; $i++) {
$nums[$i] = $a[$i];
}
}
}1 322
Задача: 538. Convert BST to Greater Tree
Сложность: medium
Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST.
Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:
Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла.
Правое поддерево узла содержит только узлы с ключами, большими ключа узла.
И левое, и правое поддеревья также должны быть бинарными деревьями поиска.
Пример:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]👨💻 Алгоритм: 1⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево. 2⃣Посещаем текущий узел, обновляем его значение и общую сумму. 3⃣Рекурсивно обрабатываем левое поддерево. 😎 Решение:
class Solution {
private $sum = 0;
public function convertBST($root) {
if ($root !== null) {
$this->convertBST($root->right);
$this->sum += $root->val;
$root->val = $this->sum;
$this->convertBST($root->left);
}
return $root;
}
}1 322
Задача: 1273. Delete Tree Nodes
Сложность: 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];
}1 322
Задача: 374. Guess Number Higher or Lower
Сложность: easy
Мы играем в игру "Угадай число" от 1 до n.
Есть предопределённая функция guess(int num), которая возвращает:
-1 — если num больше загаданного числа
1 — если num меньше загаданного числа
0 — если num совпадает с загаданным числом
Пример:
Input: n = 10, pick = 6 Output: 6👨💻 Алгоритм: 1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess. 2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного. 3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного. 😎 Решение:
class Solution extends GuessGame {
function guessNumber($n) {
$low = 1;
$high = $n;
while ($low <= $high) {
$mid = $low + intdiv($high - $low, 2);
$res = guess($mid);
if ($res == 0)
return $mid;
else if ($res < 0)
$high = $mid - 1;
else
$low = $mid + 1;
}
return -1;
}
}1 322
Задача: 567. Permutation in String
Сложность: medium
Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.
Пример:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
👨💻 Алгоритм:
1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.
😎 Решение:
function checkInclusion($s1, $s2) {
$s1Len = strlen($s1);
$s2Len = strlen($s2);
if ($s1Len > $s2Len) return false;
$s1Count = array_fill(0, 26, 0);
$s2Count = array_fill(0, 26, 0);
for ($i = 0; $i < $s1Len; $i++) {
$s1Count[ord($s1[$i]) - ord('a')]++;
$s2Count[ord($s2[$i]) - ord('a')]++;
}
for ($i = 0; $i < $s2Len - $s1Len; $i++) {
if ($s1Count == $s2Count) return true;
$s2Count[ord($s2[$i]) - ord('a')]--;
$s2Count[ord($s2[$i + $s1Len]) - ord('a')]++;
}
return $s1Count == $s2Count;
}1 322
Задача: 645. Set Mismatch
Сложность: easy
У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.
Пример:
Input: nums = [1,2,2,4] Output: [2,3]👨💻 Алгоритм: 1⃣Пройдите по массиву, используя набор для отслеживания чисел, чтобы определить дублированное число. 2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива. 3⃣Верните дублированное и отсутствующее числа в виде массива. 😎 Решение:
function findErrorNums($nums) {
$n = count($nums);
$numSet = [];
$duplicate = -1;
foreach ($nums as $num) {
if (in_array($num, $numSet)) {
$duplicate = $num;
}
$numSet[] = $num;
}
$missing = ($n * ($n + 1)) / 2 - array_sum(array_unique($numSet));
return [$duplicate, $missing];
}1 322
Задача: 282. Expression Add Operators
Сложность: hard
Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.
Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.
Пример:
Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.👨💻 Алгоритм: 1⃣Инициализация и рекурсивный вызов: Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения. Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений. 2⃣Рекурсивная генерация выражений: В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения. Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение. 3⃣Проверка и запись валидных выражений: Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов. Если выражение валидное, записывайте его в список результатов. 😎 Решение:
class Solution {
private $answer;
private $digits;
private $target;
private function recurse($index, $previousOperand, $currentOperand, $value, &$ops) {
if ($index == strlen($this->digits)) {
if ($value == $this->target && $currentOperand == 0) {
$this->answer[] = implode("", $ops);
}
return;
}
$currentOperand = $currentOperand * 10 + intval($this->digits[$index]);
$currentValRep = strval($currentOperand);
if ($currentOperand > 0) {
$this->recurse($index + 1, $previousOperand, $currentOperand, $value, $ops);
}
$ops[] = "+";
$ops[] = $currentValRep;
$this->recurse($index + 1, $currentOperand, 0, $value + $currentOperand, $ops);
array_pop($ops);
array_pop($ops);
if (count($ops) > 0) {
$ops[] = "-";
$ops[] = $currentValRep;
$this->recurse($index + 1, -$currentOperand, 0, $value - $currentOperand, $ops);
array_pop($ops);
array_pop($ops);
$ops[] = "*";
$ops[] = $currentValRep;
$this->recurse($index + 1, $currentOperand * $previousOperand, 0, $value - $previousOperand + ($currentOperand * $previousOperand), $ops);
array_pop($ops);
array_pop($ops);
}
}
public function addOperators($num, $target) {
if (strlen($num) == 0) {
return [];
}
$this->target = $target;
$this->digits = $num;
$this->answer = [];
$ops = [];
$this->recurse(0, 0, 0, 0, $ops);
return $this->answer;
}
}1 322
Задача: 137. Single Number II
Сложность: medium
Дан массив целых чисел nums, в котором каждый элемент встречается три раза, кроме одного, который встречается ровно один раз. Найдите этот единственный элемент и верните его.
Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.
Пример:
Input: nums = [2,2,3,2] Output: 3👨💻 Алгоритм: 1⃣Сортировка массива: Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом. 2⃣Итерация с проверкой: Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива. Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла. 3⃣Возврат уникального элемента: Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе. Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше. 😎 Решение:
function singleNumber($nums) {
sort($nums);
$len = count($nums);
for ($i = 0; $i < $len - 1; $i += 3) {
if ($nums[$i] !== $nums[$i + 1]) {
return $nums[$i];
}
}
return $nums[$len - 1];
}1 322
Задача: 233. Number of Digit One
Сложность: hard
Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.
Пример:
Input: n = 13 Output: 6👨💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение:
function countDigitOne($n) {
$countr = 0;
for ($i = 1; $i <= $n; $i *= 10) {
$divider = $i * 10;
$countr += intval($n / $divider) * $i + min(max($n % $divider - $i + 1, 0), $i);
}
return $countr;
}1 322
Задача: 1469. Find All The Lonely Nodes
Сложность: easy
В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.
Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.
Пример:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.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 {
function DFS($root, $isLonely, &$ans) {
if ($root === null) {
return;
}
if ($isLonely) {
$ans[] = $root->val;
}
$this->DFS($root->left, $root->right === null, $ans);
$this->DFS($root->right, $root->left === null, $ans);
}
function getLonelyNodes($root) {
$ans = [];
$this->DFS($root, false, $ans);
return $ans;
}
}1 322
Задача: 863. All Nodes Distance K in Binary Tree
Сложность: medium
Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла.
Ответ можно вернуть в любом порядке.
Пример:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.class Solution {
function distanceK($root, $target, $k) {
$this->addParent($root, null);
$answer = [];
$visited = new SplObjectStorage();
$this->dfs($target, $k, $visited, $answer);
return $answer;
}
private function addParent($cur, $parent) {
if ($cur) {
$cur->parent = $parent;
$this->addParent($cur->left, $cur);
$this->addParent($cur->right, $cur);
}
}
private function dfs($cur, $distance, $visited, &$answer) {
if (!$cur || $visited->contains($cur)) return;
$visited->attach($cur);
if ($distance == 0) {
$answer[] = $cur->val;
return;
}
$this->dfs($cur->parent, $distance - 1, $visited, $answer);
$this->dfs($cur->left, $distance - 1, $visited, $answer);
$this->dfs($cur->right, $distance - 1, $visited, $answer);
}
}1 322
Задача: 1539. Kth Missing Positive Number
Сложность: easy
Дан массив
arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.
Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.
Пример:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.class Solution {
function findKthPositive($arr, $k) {
if ($k <= $arr[0] - 1) {
return $k;
}
$k -= $arr[0] - 1;
$n = count($arr);
for ($i = 0; $i < $n - 1; ++$i) {
$currMissing = $arr[$i + 1] - $arr[$i] - 1;
if ($k <= $currMissing) {
return $arr[$i] + $k;
}
$k -= $currMissing;
}
return $arr[$n - 1] + $k;
}
}1 322
![Задача: 280. Wiggle Sort Сложность: medium Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] &g](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDACgcHiMeGSgjISMtKygwPGRBPDc3PHtYXUlkkYCZlo+AjIqgtObDoKrarYqMyP/L2u71////m8H////6/+b9//j/2wBDASstLTw1PHZBQXb4pYyl+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj/wAARCAAUACgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwDYLY7H8qb5nsfyp2Bn/wCvSFQ3UUAAbPajdUL70y2E2juSaRLlP42UemM0rj5WWAeaKQEMoI6GimIX8aMe5oooACOOpprLnHJH0NFFAAq853N+dFFFAH//2Q==)
Задача: 280. Wiggle Sort
Сложность: medium
Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....
Вы можете считать, что входной массив всегда имеет допустимый ответ.
Пример:
Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4] Explanation: [1,6,2,5,3,4] is also accepted.👨💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:
class Solution {
private function swap(&$nums, $i, $j) {
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
}
public function wiggleSort(&$nums) {
for ($i = 0; $i < count($nums) - 1; $i++) {
if (($i % 2 == 0 && $nums[$i] > $nums[$i + 1]) || ($i % 2 == 1 && $nums[$i] < $nums[$i + 1])) {
$this->swap($nums, $i, $i + 1);
}
}
}
}1 322
Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard
Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия:
Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).
Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].
Пример:
Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]class Solution {
private function bitmask($word) {
$mask = 0;
for ($i = 0; $i < strlen($word); $i++) {
$mask |= 1 << (ord($word[$i]) - ord('a'));
}
return $mask;
}
function findNumOfValidWords($words, $puzzles) {
$wordCount = [];
foreach ($words as $word) {
$mask = $this->bitmask($word);
if (!isset($wordCount[$mask])) {
$wordCount[$mask] = 0;
}
$wordCount[$mask]++;
}
$result = [];
foreach ($puzzles as $puzzle) {
$first = 1 << (ord($puzzle[0]) - ord('a'));
$count = isset($wordCount[$first]) ? $wordCount[$first] : 0;
$mask = $this->bitmask(substr($puzzle, 1));
for ($submask = $mask; $submask > 0; $submask = ($submask - 1) & $mask) {
$count += isset($wordCount[$submask | $first]) ? $wordCount[$submask | $first] : 0;
}
$result[] = $count;
}
return $result;
}
}1 322
Задача: 415. Add Strings
Сложность: easy
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: num1 = "11", num2 = "123" Output: "134"👨💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел. 2⃣Пройдите по массиву nums, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число. 😎 Решение:
function thirdMax($nums) {
$first = null;
$second = null;
$third = null;
foreach ($nums as $num) {
if ($num === $first || $num === $second || $num === $third) {
continue;
}
if ($first === null || $num > $first) {
$third = $second;
$second = $first;
$first = $num;
} elseif ($second === null || $num > $second) {
$third = $second;
$second = $num;
} elseif ($third === null || $num > $third) {
$third = $num;
}
}
return $third !== null ? $third : $first;
}