PHP | LeetCode

Задача: 861. Score After Flipping Matrix
Сложность: medium

Вам дана бинарная матрица grid размером m x n.

Ход состоит из выбора любой строки или столбца и переключения каждого значения в этой строке или столбце (т.е. изменение всех 0 на 1, и всех 1 на 0).

Каждая строка матрицы интерпретируется как двоичное число, и счёт матрицы — это сумма этих чисел.

Верните наивысший возможный счёт после выполнения любого количества ходов (включая ноль ходов).

Пример:
Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные: m и n для количества строк и столбцов в grid, score для хранения максимального счёта матрицы. Пройдитесь по первому столбцу матрицы. Если элемент равен 0, переверните всю строку.

2⃣Пройдитесь по матрице от второго до последнего столбца. Для каждого столбца посчитайте количество нулей (countZero). Если количество нулей больше, переверните весь столбец.

3⃣Пройдитесь по модифицированной матрице. Для каждого элемента добавьте его к score, сдвинув влево на значение текущего столбца. Верните score, который хранит наивысший возможный счёт матрицы.

😎 Решение:
class Solution {
function matrixScore($grid) {
$m = count($grid);
$n = count($grid[0]);

for ($i = 0; $i < $m; $i++) {
if ($grid[$i][0] == 0) {
for ($j = 0; $j < $n; $j++) {
$grid[$i][$j] ^= 1;
}
}
}

for ($j = 1; $j < $n; $j++) {
$countZero = 0;
for ($i = 0; $i < $m; $i++) {
if ($grid[$i][$j] == 0) {
$countZero++;
}
}
if ($countZero > $m / 2) {
for ($i = 0; $i < $m; $i++) {
$grid[$i][$j] ^= 1;
}
}
}

$score = 0;
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($grid[$i][$j] == 1) {
$score += 1

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:
Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

👨‍💻 Алгоритм:

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

2⃣Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет.

3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.

😎 Решение:
class Solution {
function findRoot($tree) {
$seen = [];

foreach ($tree as $node) {
foreach ($node->children as $child) {
$seen[$child->val] = true;
}
}

foreach ($tree as $node) {
if (!isset($seen[$node->val])) {
return $node;
}
}

return null;
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium

Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.

Пример:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.
start для хранения начального индекса текущей подстроки.
currCost для хранения текущих затрат на преобразование подстроки s в t.

2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.

3⃣Возврат maxLen как результата.

😎 Решение:
class Solution {
/**
* @param String $s
* @param String $t
* @param Integer $maxCost
* @return Integer
*/
function equalSubstring($s, $t, $maxCost) {
$N = strlen($s);

$maxLen = 0;
$start = 0;
$currCost = 0;

for ($i = 0; $i < $N; $i++) {
$currCost += abs(ord($s[$i]) - ord($t[$i]));

while ($currCost > $maxCost) {
$currCost -= abs(ord($s[$start]) - ord($t[$start]));
$start++;
}

$maxLen = max($maxLen, $i - $start + 1);
}

return $maxLen;
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:
Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

👨‍💻 Алгоритм:

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:
class TopVotedCandidate {
private $times;
private $leaders;

function __construct($persons, $times) {
$this->times = $times;
$this->leaders = [];
$counts = [];
$leader = -1;

foreach ($persons as $person) {
if (!isset($counts[$person])) {
$counts[$person] = 0;
}
$counts[$person]++;
if (!isset($counts[$leader]) || $counts[$person] >= $counts[$leader]) {
$leader = $person;
}
$this->leaders[] = $leader;
}
}

function q($t) {
$left = 0;
$right = count($this->times) - 1;
while ($left < $right) {
$mid = intdiv($left + $right + 1, 2);
if ($this->times[$mid] leaders[$left];
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 532. K-diff Pairs in an Array
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.
Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:
class Solution {
function findPairs($nums, $k) {
$counter = [];
foreach ($nums as $num) {
if (!isset($counter[$num])) {
$counter[$num] = 0;
}
$counter[$num]++;
}

$result = 0;
foreach ($counter as $x => $val) {
if ($k > 0) {
if (isset($counter[$x + $k])) {
$result++;
}
} else if ($k == 0 && $val > 1) {
$result++;
}
}

return $result;
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

👨‍💻 Алгоритм:

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

2⃣Использование бинарного поиска:
Примените бинарный поиск в диапазоне от минимальной до максимальной грузоподъемности, чтобы найти наименьшую грузоподъемность, при которой все пакеты можно отправить за заданное количество дней.

3⃣Проверка возможности отправки всех пакетов за заданное количество дней:
Напишите вспомогательную функцию, которая проверяет, можно ли отправить все пакеты при заданной грузоподъемности за определенное количество дней. Эта функция проходит по списку весов и считает количество необходимых дней для отправки всех пакетов при текущей грузоподъемности.

😎 Решение:
class Solution {
function shipWithinDays($weights, $D) {
$left = max($weights);
$right = array_sum($weights);

while ($left < $right) {
$mid = (int)(($left + $right) / 2);
if ($this->canShipInDays($weights, $D, $mid)) {
$right = $mid;
} else {
$left = $mid + 1;
}
}

return $left;
}

private function canShipInDays($weights, $D, $capacity) {
$days = 1;
$total = 0;
foreach ($weights as $weight) {
if ($total + $weight > $capacity) {
$days++;
$total = 0;
}
$total += $weight;
}
return $days

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left sum = array_fill(0, count($nums) + 1, 0);
for ($i = 0; $i < count($nums); $i++) {
$this->sum[$i + 1] = $this->sum[$i] + $nums[$i];
}
}

function sumRange($i, $j) {
return $this->sum[$j + 1] - $this->sum[$i];
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива.

3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива.

😎 Решение:
function findLength($nums1, $nums2) {
$dp = array_fill(0, count($nums1) + 1, array_fill(0, count($nums2) + 1, 0));
$maxLength = 0;
for ($i = count($nums1) - 1; $i >= 0; $i--) {
for ($j = count($nums2) - 1; $j >= 0; $j--) {
if ($nums1[$i] == $nums2[$j]) {
$dp[$i][$j] = $dp[$i + 1][$j + 1] + 1;
$maxLength = max($maxLength, $dp[$i][$j]);
}
}
}
return $maxLength;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:
Input: arr = [0]
Output: 1

👨‍💻 Алгоритм:

1⃣Создать множество для хранения уникальных результатов побитового ИЛИ.

2⃣Для каждого элемента массива, вычислить побитовое ИЛИ всех подмассивов, начинающихся с этого элемента.
Добавить результат каждого вычисления в множество.

3⃣Вернуть размер множества.

😎 Решение:
function subarrayBitwiseORs($arr) {
$result = [];
$current = [];
foreach ($arr as $num) {
$next = [$num];
foreach ($current as $x) {
$next[] = $x | $num;
}
$current = array_unique($next);
foreach ($current as $x) {
$result[$x] = true;
}
}
return count($result);
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4

👨‍💻 Алгоритм:

1⃣Использовать словарь для хранения количества встреченных сумм префиксов.
Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.

2⃣Пройти по массиву и обновить текущую сумму.
Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов.
Обновить словарь префиксных сумм.

3⃣Вернуть счетчик подмассивов.

😎 Решение:
function numSubarraysWithSum($nums, $goal) {
$prefixSumCount = [0 => 1];
$currentSum = 0;
$count = 0;

foreach ($nums as $num) {
$currentSum += $num;
if (isset($prefixSumCount[$currentSum - $goal])) {
$count += $prefixSumCount[$currentSum - $goal];
}
if (isset($prefixSumCount[$currentSum])) {
$prefixSumCount[$currentSum]++;
} else {
$prefixSumCount[$currentSum] = 1;
}
}

return $count;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$heap->insert([0, 0], -$coins[0]);

while (!$heap->isEmpty()) {
$current = $heap->extract();
$current_cost = -$current['priority'];
$i = $current['data'][1];
if ($current_cost > $dp[$i]) continue;
for ($k = 1; $k insert([$new_cost, $i + $k], -$new_cost);
}
}
}
}

return $dp[$n - 1] == PHP_INT_MAX ? [] : $path[$n - 1];
}

Ставь 👍 и забирай 📚 Базу знаний

Задача №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 kSum($nums, $target, 4);
}

function kSum($nums, $target, $k) {
$res = [];

if (!count($nums)) {
return $res;
}

$averageValue = $target / $k;
if ($averageValue < $nums[0] || $nums[count($nums)-1] < $averageValue) {
return $res;
}

if ($k == 2) {
return $this->twoSum($nums, $target);
}

for ($i = 0; $i < count($nums); $i++) {
if ($i == 0 || $nums[$i - 1] != $nums[$i]) {
$kSum = $this->kSum(array_slice($nums, $i+1), $target - $nums[$i], $k - 1);
foreach ($kSum as $item) {
$res[] = array_merge([$nums[$i]], $item);
}
}
}
return $res;
}

function twoSum($nums, $target) {
$res = [];
$lo = 0;
$hi = count($nums) - 1;

while ($lo < $hi) {
$currSum = $nums[$lo] + $nums[$hi];
if ($currSum < $target || ($lo > 0 && $nums[$lo] == $nums[$lo - 1])) {
$lo++;
} elseif ($currSum > $target || ($hi < count($nums) - 1 && $nums[$hi] == $nums[$hi + 1])) {
$hi--;
} else {
$res[] = [$nums[$lo], $nums[$hi]];
$lo++;
$hi--;
}
}
return $res;
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:
Input: num = "257"
Output: "IOI"

👨‍💻 Алгоритм:

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:
function toHexString($num) {
$hexStr = strtoupper(dechex($num));
$hexStr = str_replace(['0', '1'], ['O', 'I'], $hexStr);
foreach (str_split($hexStr) as $char) {
if (!in_array($char, str_split('ABCDEFIO'))) {
return "ERROR";
}
}
return $hexStr;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 411. Minimum Unique Word Abbreviation
Сложность: hard

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):
"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.
Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:
Input: target = "apple", dictionary = ["blade"]
Output: "a4"

👨‍💻 Алгоритм:

1⃣Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.

2⃣Сгенерируйте все возможные аббревиатуры для строки target.

3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:
function generateAbbreviations($word) {
$result = [];
generateAbbreviationsHelper(str_split($word), "", 0, 0, $result);
return $result;
}

function generateAbbreviationsHelper($word, $current, $pos, $count, &$result) {
if ($pos == count($word)) {
$result[] = $current . ($count > 0 ? $count : "");
return;
}
generateAbbreviationsHelper($word, $current, $pos + 1, $count + 1, $result);
generateAbbreviationsHelper($word, $current . ($count > 0 ? $count : "") . $word[$pos], $pos + 1, 0, $result);
}

function minAbbreviation($target, $dictionary) {
$targetAbbrs = generateAbbreviations($target);
$dictAbbrs = [];
foreach ($dictionary as $word) {
$dictAbbrs = array_merge($dictAbbrs, generateAbbreviations($word));
}
$dictAbbrs = array_flip(array_flip($dictAbbrs));
$validAbbrs = array_diff($targetAbbrs, $dictAbbrs);
usort($validAbbrs, function($a, $b) { return strlen($a) - strlen($b); });
return $validAbbrs[0];
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 779. K-th Symbol in Grammar
Сложность: medium

Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10.

Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110.
Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк.

Пример:
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

👨‍💻 Алгоритм:

1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal.

2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal).

😎 Решение:
class Solution {
private function depthFirstSearch(int $n, int $k, int $rootVal): int {
if ($n === 1) return $rootVal;
$totalNodes = 1 $totalNodes / 2) {
$nextRootVal = $rootVal === 0 ? 1 : 0;
return $this->depthFirstSearch($n - 1, $k - $totalNodes / 2, $nextRootVal);
} else {
$nextRootVal = $rootVal === 0 ? 0 : 1;
return $this->depthFirstSearch($n - 1, $k, $nextRootVal);
}
}

public function kthGrammar(int $n, int $k): int {
return $this->depthFirstSearch($n, $k, 0);
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 477. Total Hamming Distance
Сложность: Medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:
Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

👨‍💻 Алгоритм:

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:
class Solution {
function totalHammingDistance($nums) {
$ans = 0;

if (empty($nums)) {
return $ans;
}

for ($i = 0; $i < count($nums) - 1; $i++) {
for ($j = $i + 1; $j < count($nums); $j++) {
$ans += $this->countBits($nums[$i] ^ $nums[$j]);
}
}

return $ans;
}

private function countBits($n) {
$count = 0;
while ($n > 0) {
$count += $n & 1;
$n >>= 1;
}
return $count;
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 859. Buddy Strings
Сложность: easy

Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:
Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

👨‍💻 Алгоритм:

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:
class Solution {
function buddyStrings($s, $goal) {
if (strlen($s) != strlen($goal)) return false;
if ($s == $goal) {
$freq = array_fill(0, 26, 0);
foreach (str_split($s) as $ch) {
if (++$freq[ord($ch) - ord('a')] > 1) return true;
}
return false;
}

$firstIndex = -1;
$secondIndex = -1;
for ($i = 0; $i < strlen($s); ++$i) {
if ($s[$i] != $goal[$i]) {
if ($firstIndex == -1) $firstIndex = $i;
else if ($secondIndex == -1) $secondIndex = $i;
else return false;
}
}

return $secondIndex != -1 &&
$s[$firstIndex] == $goal[$secondIndex] &&
$s[$secondIndex] == $goal[$firstIndex];
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 2 * $x - 1, construct(($n + 1) / 2));
$even = array_map(fn($x) => 2 * $x, construct($n / 2));
return array_merge($odd, $even);
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
}
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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 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;
}

Ставь 👍 и забирай 📚 Базу знаний