PHP | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Ko'proq ko'rsatish
Tarmoq:1 356
Obunachilar
Ma'lumot yo'q24 soatlar
-47 kunlar
-930 kunlar
Postlar arxiv
1 356
Задача: 226. Invert Binary Tree
Сложность: easy
Дан корень бинарного дерева, инвертируйте дерево и верните его корень.
Пример:
Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]👨💻 Алгоритм: 1⃣Рекурсивная инверсия поддеревьев: Если текущий узел (root) пустой, возвращаем null. Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right. Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left. 2⃣Обмен поддеревьев: Устанавливаем левое поддерево текущего узла равным правому поддереву. Устанавливаем правое поддерево текущего узла равным левому поддереву. 3⃣Возврат корня: Возвращаем текущий узел (root) как новый корень инвертированного дерева. 😎 Решение:
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
public function invertTree($root) {
if ($root === null) {
return null;
}
$right = $this->invertTree($root->right);
$left = $this->invertTree($root->left);
$root->left = $right;
$root->right = $left;
return $root;
}
}1 356
Задача №17. Letter Combinations of a Phone Number
Сложность: medium
Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.
Пример:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]👨💻 Алгоритм: 1⃣Создать ассоциативный массив, сопоставляющий цифры с соответствующими буквами. 2⃣Использовать рекурсию для перебора всех возможных комбинаций. 3⃣Добавлять полученные комбинации в результирующий массив. 😎 Решение:
class Solution {
public $result = [];
function letterCombinations($digits) {
if(strlen($digits) == 0) {
return [];
}
$layouts = [
2 => range('a', 'c'),
3 => range('d', 'f'),
4 => range('g', 'i'),
5 => range('j', 'l'),
6 => range('m', 'o'),
7 => range('p', 's'),
8 => range('t', 'v'),
9 => range('w', 'z'),
];
return $this->recursive(0, $digits, $layouts);
}
function recursive ($index, $chars, $layouts, $combine = '') {
foreach($layouts[$chars[$index]] as $currentLayout) {
if($layouts[$chars[$index + 1]]) {
$this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout);
} else {
$this->result[] = $combine . $currentLayout;
}
}
return $this->result;
}
}1 356
#hard
Задача: 827. Making A Large Island
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.👨💻 Алгоритм: 1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер. 2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1. 3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1. 😎 Решение:
class Solution {
private $dr = [-1, 0, 1, 0];
private $dc = [0, -1, 0, 1];
private $grid;
private $N;
function largestIsland($grid) {
$this->grid = $grid;
$this->N = count($grid);
$index = 2;
$area = array_fill(0, $this->N * $this->N + 2, 0);
for ($r = 0; $r < $this->N; ++$r) {
for ($c = 0; $c < $this->N; ++$c) {
if ($grid[$r][$c] == 1) {
$area[$index] = $this->dfs($r, $c, $index);
++$index;
}
}
}
$ans = max($area);
for ($r = 0; $r < $this->N; ++$r) {
for ($c = 0; $c < $this->N; ++$c) {
if ($grid[$r][$c] == 0) {
$seen = [];
foreach ($this->neighbors($r, $c) as $move) {
if ($grid[$move[0]][$move[1]] > 1) {
$seen[$grid[$move[0]][$move[1]]] = true;
}
}
$bns = 1;
foreach (array_keys($seen) as $i) {
$bns += $area[$i];
}
$ans = max($ans, $bns);
}
}
}
return $ans;
}
function dfs($r, $c, $index) {
$ans = 1;
$this->grid[$r][$c] = $index;
foreach ($this->neighbors($r, $c) as $move) {
if ($this->grid[$move[0]][$move[1]] == 1) {
$this->grid[$move[0]][$move[1]] = $index;
$ans += $this->dfs($move[0], $move[1], $index);
}
}
return $ans;
}
function neighbors($r, $c) {
$ans = [];
for ($k = 0; $k < 4; ++$k) {
$nr = $r + $this->dr[$k];
$nc = $c + $this->dc[$k];
if ($nr >= 0 && $nr < $this->N && $nc >= 0 && $nc < $this->N) {
$ans[] = [$nr, $nc];
}
}
return $ans;
}1 356
Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.
Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.
Пример:
Input: nums = [2,4,5,5,5,5,5,6,6], target = 5 Output: true Explanation: The value 5 appears 5 times and the length of the array is 9. Thus, 5 is a majority element because 5 > 9/2 is true.👨💻 Алгоритм: 1⃣Инициализация переменной count: Инициализируйте переменную count значением 0.. 2⃣Итерация по списку nums: Пройдите по каждому элементу списка nums. Если элемент num равен target, увеличьте значение переменной count. 3⃣Проверка условия мажоритарного элемента: Если count больше чем половина длины списка nums, верните true. В противном случае верните false. 😎 Решение:
class Solution {
function isMajorityElement($nums, $target) {
$count = 0;
foreach ($nums as $num) {
if ($num == $target) {
$count++;
}
}
return $count > count($nums) / 2;
}
}1 356
Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard
Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.
Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).
Пример:
Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.👨💻 Алгоритм: 1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции). 2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием: dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой). dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей). 3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов. 😎 Решение:
class Solution {
function maxProfit($k, $prices) {
$n = count($prices);
if ($n == 0 || $k == 0) return 0;
if ($k * 2 >= $n) {
$res = 0;
for ($i = 1; $i < $n; $i++) {
$res += max(0, $prices[$i] - $prices[$i - 1]);
}
return $res;
}
$dp = array_fill(0, $n, array_fill(0, $k + 1, [PHP_INT_MIN / 2, PHP_INT_MIN / 2]));
$dp[0][0][0] = 0;
$dp[0][1][1] = -$prices[0];
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j <= $k; $j++) {
$dp[$i][$j][0] = max($dp[$i - 1][$j][0], $dp[$i - 1][$j][1] + $prices[$i]);
if ($j > 0) {
$dp[$i][$j][1] = max($dp[$i - 1][$j][1], $dp[$i - 1][$j - 1][0] - $prices[$i]);
}
}
}
$res =1 356
Задача: 722. Remove Comments
Сложность: medium
Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.
Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.
Пример:
Input: source = ["/*Test program */", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/* This is a test", " multiline ", " comment for ", " testing */", "a = b + c;", "}"]
Output: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"]
👨💻 Алгоритм:
1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.
2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.
3⃣После обработки всех строк добавьте непустые строки из buffer в результат.
😎 Решение:
function removeComments($source) {
$inBlock = false;
$buffer = "";
$result = [];
foreach ($source as $line) {
$i = 0;
if (!$inBlock) $buffer = "";
while ($i < strlen($line)) {
if (!$inBlock && $i + 1 < strlen($line) && $line[$i] == '/' && $line[$i + 1] == '*') {
$inBlock = true;
$i++;
} elseif ($inBlock && $i + 1 < strlen($line) && $line[$i] == '*' && $line[$i + 1] == '/') {
$inBlock = false;
$i++;
} elseif (!$inBlock && $i + 1 < strlen($line) && $line[$i] == '/' && $line[$i + 1] == '/') {
break;
} elseif (!$inBlock) {
$buffer .= $line[$i];
}
$i++;
}
if (!$inBlock && strlen($buffer) > 0) {
$result[] = $buffer;
}
}
return $result;
}1 356
Задача: 667. Beautiful Arrangement II
Сложность: medium
Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:
Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.
Пример:
Input: n = 3, k = 1 Output: [1,2,3] Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1👨💻 Алгоритм: 1⃣Инициализация списка: Начните с создания списка от 1 до n: [1, 2, 3, ..., n]. 2⃣Конструирование шаблона с k различиями: Для обеспечения k различных значений разностей используйте следующий подход: Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей. Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей. 3⃣Заполнение списка: Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n. 😎 Решение:
class Solution {
function constructArray($n, $k) {
$answer = [];
$left = 1;
$right = $n;
for ($i = 0; $i <= $k; $i++) {
if ($i % 2 == 0) {
$answer[] = $left++;
} else {
$answer[] = $right--;
}
}
if ($k % 2 == 0) {
for ($i = $right; $i >= $left; $i--) {
$answer[] = $i;
}
} else {
for ($i = $left; $i <= $right; $i++) {
$answer[] = $i;
}
}
return $answer;
}
}1 356
Задача: 904. Fruit Into Baskets
Сложность: medium
Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.
Пример:
Input: fruits = [1,2,1] Output: 3👨💻 Алгоритм: 1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов. 2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне. Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов. 3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге. 😎 Решение:
function totalFruit($fruits) {
$basket = [];
$left = 0;
$maxFruits = 0;
for ($right = 0; $right < count($fruits); $right++) {
if (!isset($basket[$fruits[$right]])) {
$basket[$fruits[$right]] = 0;
}
$basket[$fruits[$right]]++;
while (count($basket) > 2) {
$basket[$fruits[$left]]--;
if ($basket[$fruits[$left]] == 0) {
unset($basket[$fruits[$left]]);
}
$left++;
}
$maxFruits = max($maxFruits, $right - $left + 1);
}
return $maxFruits;
}1 356
Задача: 43. Multiply Strings
Сложность: hard
Даны две строки
num1 и num2, представляющие неотрицательные целые числа. Необходимо вернуть их произведение в виде строки.
Запрещено использовать встроенные библиотеки для работы с большими числами (BigInteger) и напрямую преобразовывать строки в числа.
Пример:
Input: num1 = "2", num2 = "3" Output: "6"👨💻 Алгоритм: 1⃣Перевернуть строки
num1 и num2.
2⃣Умножить каждую цифру num2[j] на каждую цифру num1[i], добавляя результаты в массив ans.
3⃣ Обработать переносы (carry), чтобы числа не превышали 9.
😎 Решение:
function multiply($num1, $num2) {
if ($num1 === "0" || $num2 === "0") {
return "0";
}
$n = strlen($num1);
$m = strlen($num2);
$ans = array_fill(0, $n + $m, 0);
for ($i = $n - 1; $i >= 0; $i--) {
for ($j = $m - 1; $j >= 0; $j--) {
$mul = ($num1[$i] - '0') * ($num2[$j] - '0');
$sum = $mul + $ans[$i + $j + 1];
$ans[$i + $j + 1] = $sum % 10;
$ans[$i + $j] += intdiv($sum, 10);
}
}
while (count($ans) > 1 && $ans[0] === 0) {
array_shift($ans);
}
return implode("", $ans);
}1 356
Задача: 1463. Cherry Pickup II
Сложность: hard
Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).
У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).
Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.
Пример:
Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.class Solution {
function cherryPickup($grid) {
$m = count($grid);
$n = count($grid[0]);
$dp = array_fill(0, $m, array_fill(0, $n, array_fill(0, $n, 0)));
for ($row = $m - 1; $row >= 0; $row--) {
for ($col1 = 0; $col1 < $n; $col1++) {
for ($col2 = 0; $col2 < $n; $col2++) {
$result = $grid[$row][$col1];
if ($col1 != $col2) {
$result += $grid[$row][$col2];
}
if ($row != $m - 1) {
$maxCherries = 0;
for ($newCol1 = $col1 - 1; $newCol1 <= $col1 + 1; $newCol1++) {
for ($newCol2 = $col2 - 1; $newCol2 <= $col2 + 1; $newCol2++) {
if ($newCol1 >= 0 && $newCol1 < $n && $newCol2 >= 0 && $newCol2 < $n) {
$maxCherries = max($maxCherries, $dp[$row + 1][$newCol1][$newCol2]);
}
}
}
$result += $maxCherries;
}
$dp[$row][$col1][$col2] = $result;
}
}
}
return $dp[0][0][$n - 1];
}
}1 356
Задача: 672. Bulb Switcher II
Сложность: medium
Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2class Solution {
function flipLights($n, $m) {
$seen = [];
$n = min($n, 6);
$shift = max(0, 6 - $n);
for ($cand = 0; $cand < 16; ++$cand) {
$bcount = substr_count(decbin($cand), '1');
if ($bcount % 2 == $m % 2 && $bcount <= $m) {
$lights = 0;
if ((($cand >> 0) & 1) > 0) $lights ^= 0b111111 >> $shift;
if ((($cand >> 1) & 1) > 0) $lights ^= 0b010101 >> $shift;
if ((($cand >> 2) & 1) >1 356
Задача: 790. Domino and Tromino Tiling
Сложность: medium
У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.
Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.
Пример:
Input: n = 3 Output: 5 Explanation: The five different ways are show above.👨💻 Алгоритм: 1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n). 2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас. 3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся. 😎 Решение:
class Solution {
private $MOD = 1_000_000_007;
private $fCache = [];
private $pCache = [];
private function p($n) {
if (isset($this->pCache[$n])) {
return $this->pCache[$n];
}
if ($n == 2) {
return 1;
}
$result = ($this->p($n - 1) + $this->f($n - 2)) % $this->MOD;
$this->pCache[$n] = $result;
return $result;
}
private function f($n) {
if (isset($this->fCache[$n])) {
return $this->fCache[$n];
}
if ($n <= 2) {
return $n;
}
$result = ($this->f($n - 1) + $this->f($n - 2) + 2 * $this->p($n - 1)) % $this->MOD;
$this->fCache[$n] = $result;
return $result;
}
public function numTilings($n) {
return $this->f($n);
}
}1 356
Задача: 836. Rectangle Overlap
Сложность: easy
Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y.
Два прямоугольника перекрываются, если площадь их пересечения положительна. Для ясности, два прямоугольника, которые касаются только в углу или по краям, не перекрываются.
Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false.
Пример:
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3] Output: true👨💻 Алгоритм: 1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]). 2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]). 3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются. 😎 Решение:
class Solution {
/**
* @param Integer[] $rec1
* @param Integer[] $rec2
* @return Boolean
*/
function isRectangleOverlap($rec1, $rec2) {
return min($rec1[2], $rec2[2]) > max($rec1[0], $rec2[0]) &&
min($rec1[3], $rec2[3]) > max($rec1[1], $rec2[1]);
}
}1 356
Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium
Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.
Пример:
Input: stones = [7,4,9] Output: [1,2]👨💻 Алгоритм: 1⃣Сортировка: Сначала отсортируем массив камней. 2⃣Максимальное количество ходов: Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня. 3⃣Минимальное количество ходов: Минимальное количество ходов можно определить следующим образом: Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни. Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0. В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место). 😎 Решение:
function numMovesStonesII($stones) {
sort($stones);
$n = count($stones);
$maxMoves = $stones[$n-1] - $stones[0] + 1 - $n;
$maxMoves -= min($stones[1] - $stones[0] - 1, $stones[$n-1] - $stones[$n-2] - 1);
$minMoves = PHP_INT_MAX;
$j = 0;
for ($i = 0; $i < $n; $i++) {
while ($j < $n && $stones[$j] - $stones[$i] + 1 <= $n) {
$j++;
}
$alreadyInWindow = $j - $i;
if ($alreadyInWindow == $n - 1 && $stones[$j-1] - $stones[$i] + 1 == $n - 1) {
$minMoves = min($minMoves, 2);
} else {
$minMoves = min($minMoves, $n - $alreadyInWindow);
}
}
return [$minMoves, $maxMoves];
}1 356
Задача: 348. Design Tic-Tac-Toe
Сложность: medium
Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:
Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:
TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.
Пример:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1]👨💻 Алгоритм: 1⃣Инициализация: Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно. Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно. Инициализируйте размер доски n. 2⃣Выполнение хода: Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода. Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal. 3⃣Проверка победы: Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя. Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода. 😎 Решение:
class TicTacToe {
private $n;
private $rows;
private $cols;
private $diagonal;
private $antiDiagonal;
function __construct($n) {
$this->n = $n;
$this->rows = array_fill(0, $n, 0);
$this->cols = array_fill(0, $n, 0);
$this->diagonal = 0;
$this->antiDiagonal = 0;
}
function move($row, $col, $player) {
$add = $player === 1 ? 1 : -1;
$this->rows[$row] += $add;
$this->cols[$col] += $add;
if ($row === $col) {
$this->diagonal += $add;
}
if ($row + $col === $this->n - 1) {
$this->antiDiagonal += $add;
}
if (abs($this->rows[$row]) === $this->n ||
abs($this->cols[$col]) === $this->n ||
abs($this->diagonal) === $this->n ||
abs($this->antiDiagonal) === $this->n) {
return $player;
}
return 0;
}
}1 356
Задача: 1087. Brace Expansion
Сложность: medium
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]class Solution {
private function storeFirstOptions($s, $startPos, &$firstOptions) {
if ($s[$startPos] != '{') {
$firstOptions[] = $s[$startPos];
} else {
$startPos++;
while ($s[$startPos] != '}') {
if ($s[$startPos] >= 'a' && $s[$startPos] <= 'z') {
$firstOptions[] = $s[$startPos];
}
$startPos++;
}
sort($firstOptions);
}
return $startPos + 1;
}
private function findAllWords($s, $startPos) {
if ($startPos == strlen($s)) {
return [""];
}
$firstOptions = [];
$remStringStartPos = $this->storeFirstOptions($s, $startPos, $firstOptions);
$wordsWithRemString = $this->findAllWords($s, $remStringStartPos);
$expandedWords = [];
foreach ($firstOptions as $c) {
foreach ($wordsWithRemString as $word) {
$expandedWords[] = $c . $word;
}
}
return $expandedWords;
}
public function expand($s) {
return $this->findAllWords($s, 0);
}
}1 356
Задача: 155. Min Stack
Сложность: medium
Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.
Пример:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2class MinStack {
private $stack = [];
public function __construct() {
$this->stack = [];
}
private function last() {
return end($this->stack);
}
public function push($x) {
if (empty($this->stack)) {
array_push($this->stack, [$x, $x]);
return;
}
$currentMin = $this->last()[1];
array_push($this->stack, [$x, min($currentMin, $x)]);
}
public function pop() {
array_pop($this->stack);
}
public function top() {
$last = $this->last();
return $last[0];
}
public function getMin() {
$last = $this->last();
return $last[1];
}
}1 356
Задача: 205. Isomorphic Strings
Сложность: easy
Даны две строки s и t, определите, являются ли они изоморфными.
Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.
Все вхождения одного символа должны быть заменены другим символом, сохраняя порядок символов. Два символа не могут отображаться в один и тот же символ, но один символ может отображаться сам на себя.
Пример:
Input: s = "egg", t = "add" Output: true👨💻 Алгоритм: 1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s. 2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению. 3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам. 😎 Решение:
class Solution {
function isIsomorphic($s, $t) {
$mappingStoT = [];
$mappingTtoS = [];
for ($i = 0; $i < strlen($s); ++$i) {
$c1 = $s[$i];
$c2 = $t[$i];
if (!isset($mappingStoT[$c1]) && !isset($mappingTtoS[$c2])) {
$mappingStoT[$c1] = $c2;
$mappingTtoS[$c2] = $c1;
} else if (($mappingStoT[$c1] ?? null) !== $c2 || ($mappingTtoS[$c2] ?? null) !== $c1) {
return false;
}
}
return true;
}
}1 356
Главный навык на ближайшие годы — ВАЙБ-КОДИНГ
ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня
И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную.
Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg
1 356
Задача: 1248. Count Number of Nice Subarrays
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
Input: arr = [1,2] Output: 2👨💻 Алгоритм: 1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1. 2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц. 3⃣Подсчитайте количество таких подмассивов и верните этот результат. 😎 Решение:
class Solution {
function numberOfSubarrays($nums, $k) {
return $this->atMost($nums, $k) - $this->atMost($nums, $k - 1);
}
private function atMost($nums, $k) {
$res = 0;
$left = 0;
$count = 0;
for ($right = 0; $right < count($nums); $right++) {
if ($nums[$right] % 2 === 1) $count++;
while ($count > $k) {
if ($nums[$left++] % 2 === 1) $count--;
}
$res += $right - $left + 1;
}
return $res;
}
}