PHP | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Mostrar más
Red:1 356
Suscriptores
-124 horas
-67 días
-930 días
Archivo de publicaciones
1 356
Задача: 932. Beautiful Array
Сложность: medium
Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.
Пример:
Input: n = 4 Output: [2,1,4,3]👨💻 Алгоритм: 1⃣Использовать рекурсивный метод для создания красивого массива. 2⃣Если длина массива равна 1, вернуть массив [1]. Разделить n на четные и нечетные индексы и создать массивы для них. 3⃣Объединить массивы, созданные для четных и нечетных индексов, в результирующий массив. 😎 Решение:
function beautifulArray($n) {
return construct($n);
}
function construct($n) {
if ($n == 1) return [1];
$odd = array_map(fn($x) => 2 * $x - 1, construct(($n + 1) / 2));
$even = array_map(fn($x) => 2 * $x, construct($n / 2));
return array_merge($odd, $even);
}1 356
Задача: 1094. Car Pooling
Сложность: medium
Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).
Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.
Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.
Пример:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false👨💻 Алгоритм: 1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity. 2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени. 3⃣Мы можем сохранить изменения количества пассажиров в каждый момент времени, отсортировать их по меткам времени и, наконец, пройтись по ним, чтобы проверить фактическую вместимость. 😎 Решение:
class Solution {
function carPooling($trips, $capacity) {
$timestamp = [];
foreach ($trips as $trip) {
$timestamp[$trip[1]] = ($timestamp[$trip[1]] ?? 0) + $trip[0];
$timestamp[$trip[2]] = ($timestamp[$trip[2]] ?? 0) - $trip[0];
}
ksort($timestamp);
$usedCapacity = 0;
foreach ($timestamp as $change) {
$usedCapacity += $change;
if ($usedCapacity > $capacity) {
return false;
}
}
return true;
}
}1 356
Задача: 752. Open the Lock
Сложность: medium
Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.
Пример:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6👨💻 Алгоритм: 1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния. 2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное. 3⃣Если очередь пуста и целевое состояние не найдено, верните -1. 😎 Решение:
function openLock($deadends, $target) {
function neighbors($node) {
$res = [];
for ($i = 0; $i < 4; $i++) {
$x = intval($node[$i]);
for ($d = -1; $d <= 1; $d += 2) {
$y = ($x + $d + 10) % 10;
$res[] = substr($node, 0, $i) . $y . substr($node, $i + 1);
}
}
return $res;
}
$dead = array_flip($deadends);
$queue = [['0000', 0]];
$visited = ['0000' => true];
while (!empty($queue)) {
list($node, $steps) = array_shift($queue);
if ($node === $target) return $steps;
if (isset($dead[$node])) continue;
foreach (neighbors($node) as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = [$neighbor, $steps + 1];
}
}
}
return -1;
}1 356
Задача: 965. Univalued Binary Tree
Сложность: easy
Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.
Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.
Пример:
Input: root = [1,1,1,1,1,null,1] Output: true👨💻 Алгоритм: 1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список. 2⃣Проверьте, что все значения в списке одинаковы. 3⃣Если все значения одинаковы, верните true, иначе верните false. 😎 Решение:
class Solution {
private $vals;
function isUnivalTree($root) {
$this->vals = [];
$this->dfs($root);
foreach ($this->vals as $v) {
if ($v != $this->vals[0]) {
return false;
}
}
return true;
}
function dfs($node) {
if ($node != null) {
$this->vals[] = $node->val;
$this->dfs($node->left);
$this->dfs($node->right);
}
}
}1 356
Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard
Дано n заказов, каждый из которых состоит из услуги забора и доставки.
Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).
Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1 Output: 1 Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.👨💻 Алгоритм: 1⃣Инициализация: Используйте динамическое программирование для хранения количества допустимых последовательностей для каждого количества заказов от 1 до n. 2⃣Рекурсивное вычисление: Для каждого количества заказов k используйте рекурсивную формулу для вычисления количества допустимых последовательностей, учитывая, что каждая новая пара (забор и доставка) может быть вставлена в любую из существующих позиций. 3⃣Возвращение результата: Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения. 😎 Решение:
class Solution {
function countOrders($n) {
$MOD = 1_000_000_007;
$dp = array_fill(0, $n + 1, 0);
$dp[0] = 1;
for ($i = 1; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] * (2 * $i - 1) * $i % $MOD;
}
return $dp[$n];
}
}1 356
Задача: 815. Bus Routes
Сложность: hard
Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.
Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.
Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.
Пример:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.class Solution {
function numBusesToDestination($routes, $source, $target) {
if ($source == $target) return 0;
$adjList = [];
foreach ($routes as $route => $stops) {
foreach ($stops as $stop) {
if (!isset($adjList[$stop])) {
$adjList[$stop] = [];
}
$adjList[$stop][] = $route;
}
}
$q = [];
$vis = [];
foreach ($adjList[$source] ?? [] as $route) {
$q[] = $route;
$vis[$route] = true;
}
$busCount = 1;
while (count($q) > 0) {
$size = count($q);
for ($i = 0; $i < $size; $i++) {
$route = array_shift($q);
foreach ($routes[$route] as $stop) {
if ($stop == $target) return $busCount;
foreach ($adjList[$stop] ?? [] as $nextRoute) {
if (!isset($vis[$nextRoute])) {
$vis[$nextRoute] = true;
$q[] = $nextRoute;
}
}
}
}
$busCount++;
}
return -1;
}
}1 356
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution {
function removeDuplicateLetters($s) {
$stack = [];
$seen = [];
$lastOccurrence = [];
for ($i = 0; $i < strlen($s); $i++) {
$lastOccurrence[$s[$i]] = $i;
}
for ($i = 0; $i < strlen($s); $i++) {
$c = $s[$i];
if (!isset($seen[$c])) {
while (!empty($stack) && $c < end($stack) && $i < $lastOccurrence[end($stack)]) {
unset($seen[array_pop($stack)]);
}
$seen[$c] = true;
$stack[] = $c;
}
}
return implode('', $stack);
}
}1 356
Задача: 1531. String Compression II
Сложность: hard
Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.
Найдите минимальную длину сжатой версии строки s после удаления не более k символов.
Пример:
Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.class Solution {
private $memo = [];
private $add = [1 => true, 9 => true, 99 => true];
function getLengthOfOptimalCompression($s, $k) {
return $this->dp($s, 0, chr(ord('a') + 26), 0, $k);
}
private function dp($s, $idx, $lastChar, $lastCharCount, $k) {
if ($k < 0) {
return PHP_INT_MAX / 2;
}
if ($idx == strlen($s)) {
return 0;
}
$key = $idx * 101 * 27 * 101 + (ord($lastChar) - ord('a')) * 101 * 101 + $lastCharCount * 101 + $k;
if (isset($this->memo[$key])) {
return $this->memo[$key];
}
$deleteChar = $this->dp($s, $idx + 1, $lastChar, $lastCharCount, $k - 1);
if ($s[$idx] == $lastChar) {
$keepChar = $this->dp($s, $idx + 1, $lastChar, $lastCharCount + 1, $k) + (isset($this->add[$lastCharCount]) ? 1 : 0);
} else {
$keepChar = $this->dp($s, $idx + 1, $s[$idx], 1, $k) + 1;
}
$res = min($keepChar, $deleteChar);
$this->memo[$key] = $res;
return $res;
}
}1 356
Задача: 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 356
Задача: 322. Coin Change
Сложность: medium
Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1.
Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.
Пример:
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1👨💻 Алгоритм: 1⃣Инициализация и вызов функции backtracking Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами. 2⃣Функция backtracking Внутри функции backtracking для каждой монеты из массива coins: Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет. 3⃣Возврат результата Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1. 😎 Решение:
class Solution {
public function coinChange($coins, $amount) {
return $this->coinChangeHelper(0, $coins, $amount);
}
private function coinChangeHelper($idxCoin, $coins, $amount) {
if ($amount == 0) return 0;
if ($idxCoin < count($coins) && $amount > 0) {
$maxVal = intdiv($amount, $coins[$idxCoin]);
$minCost = PHP_INT_MAX;
for ($x = 0; $x <= $maxVal; $x++) {
if ($amount >= $x * $coins[$idxCoin]) {
$res = $this->coinChangeHelper($idxCoin + 1, $coins, $amount - $x * $coins[$idxCoin]);
if ($res != -1) {
$minCost = min($minCost, $res + $x);
}
}
}
return $minCost == PHP_INT_MAX ? -1 : $minCost;
}
return -1;
}
}1 356
Задача: 31. Next Permutation
Сложность: medium
Дан массив целых чисел
nums, представляющий перестановку его элементов. Нужно изменить nums, чтобы получить его следующую перестановку в лексикографическом порядке. Если это невозможно, преобразовать массив в наименьшую возможную перестановку (отсортировать по возрастанию).
Замена должна происходить на месте, используя только постоянную дополнительную память.
Пример:
Input: nums = [1,2,3] Output: [1,3,2]👨💻 Алгоритм: 1⃣Найти первую пару чисел, идущих по убыванию справа налево. 2⃣Найти наименьшее число справа, которое больше найденного, и поменять их местами. 3⃣Отсортировать оставшуюся часть массива после измененного элемента. 😎 Решение:
class Solution {
function nextPermutation(&$nums) {
if (count($nums) <= 1) return;
$i = count($nums) - 2;
while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) $i--;
if ($i >= 0) {
$j = count($nums) - 1;
while ($nums[$j] <= $nums[$i]) $j--;
$this->swap($nums, $i, $j);
}
$this->reverse($nums, $i + 1, count($nums) - 1);
}
function swap(&$nums, $i, $j) {
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
}
function reverse(&$nums, $start, $end) {
while ($start < $end) {
$this->swap($nums, $start, $end);
$start++;
$end--;
}
}
}1 356
Задача: 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 356
Задача: 988. Smallest String Starting From Leaf
Сложность: medium
Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.
Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.
Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.
Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.
Пример:
Input: root = [0,1,2,3,4,3,4] Output: "dba"👨💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:
class Solution {
private $ans = "~";
function smallestFromLeaf($root) {
$this->dfs($root, "");
return $this->ans;
}
private function dfs($node, $path) {
if ($node === null) return;
$path = chr($node->val + ord('a')) . $path;
if ($node->left === null && $node->right === null) {
if (strcmp($path, $this->ans) < 0) {
$this->ans = $path;
}
}
$this->dfs($node->left, $path);
$this->dfs($node->right, $path);
}
}1 356
Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium
Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.
Пример:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.👨💻 Алгоритм: 1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0. 2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0): Сдвигайте max_xor влево, чтобы освободить следующий бит. Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы. 3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums: Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i. Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите. 😎 Решение:
class Solution {
function findMaximumXOR($nums) {
$maxNum = $nums[0];
foreach ($nums as $num) {
if ($num > $maxNum) {
$maxNum = $num;
}
}
$L = strlen(decbin($maxNum));
$maxXor = 0;
for ($i = $L - 1; $i >= 0; $i--) {
$maxXor <<= 1;
$currXor = $maxXor | 1;
$prefixes = [];
foreach ($nums as $num) {
$prefixes[$num >> $i] = true;
}
foreach ($prefixes as $p => $true) {
if (isset($prefixes[$currXor ^ $p])) {
$maxXor = $currXor;
break;
}
}
}
return $maxXor;
}
}
?>1 356
Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard
Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.
Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.
Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.
Пример:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.class Solution {
function numSubmatrixSumTarget($matrix, $target) {
$r = count($matrix);
$c = count($matrix[0]);
$ps = array_fill(0, $r + 1, array_fill(0, $c + 1, 0));
for ($i = 1; $i <= $r; ++$i) {
for ($j = 1; $j <= $c; ++$j) {
$ps[$i][$j] = $ps[$i - 1][$j] + $ps[$i][$j - 1] - $ps[$i - 1][$j - 1] + $matrix[$i - 1][$j - 1];
}
}
$count = 0;
for ($r1 = 1; $r1 <= $r; ++$r1) {
for ($r2 = $r1; $r2 <= $r; ++$r2) {
$h = array();
$h[0] = 1;
for ($col = 1; $col <= $c; ++$col) {
$currSum = $ps[$r2][$col] - $ps[$r1 - 1][$col];
if (isset($h[$currSum - $target])) {
$count += $h[$currSum - $target];
}
if (isset($h[$currSum])) {
$h[$currSum]++;
} else {
$h[$currSum] = 1;
}
}
}
}
return $count;
}
}1 356
Задача: 664. Strange Printer
Сложность: hard
Существует странный принтер с двумя особыми свойствами:
Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.
Пример:
Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".👨💻 Алгоритм: 1⃣Инициализация и подсчет: Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1]. 2⃣Динамическое программирование: Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим. В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов. 3⃣Возврат результата: Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки. 😎 Решение:
class Solution {
function strangePrinter($s) {
$n = strlen($s);
$dp = array_fill(0, $n, array_fill(0, $n, 0));
for ($length = 1; $length <= $n; $length++) {
for ($i = 0; $i <= $n - $length; $i++) {
$j = $i + $length - 1;
$dp[$i][$j] = ($i === $j) ? 1 : $dp[$i][$j - 1] + 1;
for ($k = $i; $k < $j; $k++) {
if ($s[$k] === $s[$j]) {
$dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + ($k + 1 <= $j - 1 ? $dp[$k + 1][$j - 1] : 0));
}
}
}
}
return $dp[0][$n - 1];
}
}1 356
Задача: 1029. Two City Scheduling
Сложность: medium
Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.
Пример:
Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7]👨💻 Алгоритм: 1⃣Вычислить разницу стоимости: Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B. 2⃣Сортировать по разнице: Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна. 3⃣Назначить города: Первые n человек из отсортированного списка отправьте в город A. Оставшихся n человек отправьте в город B. 😎 Решение:
class Solution {
function twoCitySchedCost($costs) {
usort($costs, function($a, $b) {
return ($a[0] - $a[1]) - ($b[0] - $b[1]);
});
$totalCost = 0;
$n = count($costs) / 2;
for ($i = 0; $i < $n; $i++) {
$totalCost += $costs[$i][0];
$totalCost += $costs[$i + $n][1];
}
return $totalCost;
}
}1 356
Задача: 268. Missing Number
Сложность: easy
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1⃣Сначала отсортируйте массив nums. 2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution {
function missingNumber($nums) {
sort($nums);
if ($nums[count($nums) - 1] != count($nums)) {
return count($nums);
} else if ($nums[0] != 0) {
return 0;
}
for ($i = 1; $i < count($nums); $i++) {
$expectedNum = $nums[$i - 1] + 1;
if ($nums[$i] != $expectedNum) {
return $expectedNum;
}
}
return -1;
}
}1 356
Задача: 834. Sum of Distances in Tree
Сложность: hard
Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.
Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.
Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.
Пример:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] Output: [8,12,6,10,10,10] Explanation: The tree is shown above. We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.👨💻 Алгоритм: 1⃣Постройте дерево и выполните обход в глубину (DFS) для расчета количества узлов в поддереве и суммы расстояний до всех узлов поддерева. 2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева. 3⃣Выполните второй обход в глубину (DFS) для корректировки суммы расстояний для каждого узла на основе суммы расстояний его родительского узла. 😎 Решение:
class Solution {
private $ans;
private $count;
private $graph;
private $N;
function sumOfDistancesInTree($N, $edges) {
$this->N = $N;
$this->graph = array_fill(0, $N, []);
$this->ans = array_fill(0, $N, 0);
$this->count = array_fill(0, $N, 1);
foreach ($edges as $edge) {
$this->graph[$edge[0]][] = $edge[1];
$this->graph[$edge[1]][] = $edge[0];
}
$this->dfs(0, -1);
$this->dfs2(0, -1);
return $this->ans;
}
function dfs($node, $parent) {
foreach ($this->graph[$node] as $child) {
if ($child != $parent) {
$this->dfs($child, $node);
$this->count[$node] += $this->count[$child];
$this->ans[$node] += $this->ans[$child] + $this->count[$child];
}
}
}
function dfs2($node, $parent) {
foreach ($this->graph[$node] as $child) {
if ($child != $parent) {
$this->ans[$child] = $this->ans[$node] - $this->count[$child] + $this->N - $this->count[$child];
$this->dfs2($child, $node);
}
}
}
}1 356
Задача: 940. Distinct Subsequences II4
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.
Пример:
Input: s = "abc" Output: 7👨💻 Алгоритм: 1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j. 2⃣Инициализировать матрицу DP нулями. Пройти по каждому символу строки: Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ. Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений. 3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7. 😎 Решение:
function countSubsequences($s) {
$MOD = 1000000007;
$dp = array_fill(0, 26, 0);
foreach (str_split($s) as $c) {
$index = ord($c) - ord('a');
$dp[$index] = (array_sum($dp) + 1) % $MOD;
}
return array_sum($dp) % $MOD;
}