Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

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

Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

1⃣ Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:

class Solution {
    /**
     * @param Integer[][] $graph
     * @return Integer
     */
    function shortestPathLength($graph) {
        $n = count($graph);
        if ($n == 1) return 0;
        
        $endingMask = (1 << $n) - 1;
        $seen = array_fill(0, $n, array_fill(0, $endingMask, false));
        $queue = [];
        
        for ($i = 0; $i < $n; $i++) {
            $queue[] = [$i, 1 << $i];
            $seen[$i][1 << $i] = true;
        }
        
        $steps = 0;
        while (!empty($queue)) {
            $nextQueue = [];
            foreach ($queue as [$node, $mask]) {
                foreach ($graph[$node] as $neighbor) {
                    $nextMask = $mask | (1 << $neighbor);
                    if ($nextMask == $endingMask) return 1 + $steps;
                    if (!$seen[$neighbor][$nextMask]) {
                        $seen[$neighbor][$nextMask] = true;
                        $nextQueue[] = [$neighbor, $nextMask];
                    }
                }
            }
            $steps++;
            $queue = $nextQueue;
        }
        
        return -1;
    }
}

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

Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium

Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

1⃣Обратный обход in-order:
Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений.

2⃣Накопление суммы:
Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой.

3⃣Преобразование узлов:
Преобразуйте значение каждого узла в накопленную сумму.

😎 Решение:

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $sum = 0;
    
    function bstToGst($root) {
        $this->reverseInorder($root);
        return $root;
    }
    
    function reverseInorder($node) {
        if ($node === null) return;
        $this->reverseInorder($node->right);
        $this->sum += $node->val;
        $node->val = $this->sum;
        $this->reverseInorder($node->left);
    }
}

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

Задача: 868. Binary Gap
Сложность: easy

Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.

Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.

Пример:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

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

1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1.

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

3⃣Верните найденное максимальное расстояние.

😎 Решение:

class Solution {
    function binaryGap($N) {
        $A = [];
        for ($i = 0; $i < 32; $i++)
            if (($N >> $i) & 1) $A[] = $i;

        $ans = 0;
        for ($i = 0; $i < count($A) - 1; $i++)
            $ans = max($ans, $A[$i + 1] - $A[$i]);
        return $ans;
    }
}

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

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

Дан бинарный массив nums. Верните максимальную длину непрерывного подмассива с равным количеством 0 и 1.

Пример:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

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

1⃣Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подмассива. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.

2⃣Итеративно пройдите по массиву nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подмассива между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подмассив длиннее.

3⃣Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации верните max_length.

😎 Решение:

class Solution {
    function findMaxLength($nums) {
        $countMap = [0 => -1];
        $maxLength = 0;
        $count = 0;
        
        for ($i = 0; $i < count($nums); $i++) {
            $count += ($nums[$i] == 1 ? 1 : -1);
            
            if (array_key_exists($count, $countMap)) {
                $maxLength = max($maxLength, $i - $countMap[$count]);
            } else {
                $countMap[$count] = $i;
            }
        }
        
        return $maxLength;
    }
}

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

Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium


Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.

Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.

Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.

Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

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

1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.

2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.

3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:
Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.

😎 Решение:

class Solution {
    private function dfs($node, $adj, &$visit) {
        $visit[$node] = true;
        if (!isset($adj[$node])) {
            return;
        }
        foreach ($adj[$node] as $neighbor) {
            if (!$visit[$neighbor]) {
                $visit[$neighbor] = true;
                $this->dfs($neighbor, $adj, $visit);
            }
        }
    }

    function makeConnected($n, $connections) {
        if (count($connections) < $n - 1) {
            return -1;
        }

        $adj = [];
        foreach ($connections as $connection) {
            $adj[$connection[0]][] = $connection[1];
            $adj[$connection[1]][] = $connection[0];
        }

        $numberOfConnectedComponents = 0;
        $visit = array_fill(0, $n, false);
        for ($i = 0; $i < $n; $i++) {
            if (!$visit[$i]) {
                $numberOfConnectedComponents++;
                $this->dfs($i, $adj, $visit);
            }
        }

        return $numberOfConnectedComponents - 1;
    }
}

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

Задача: 360. Sort Transformed Array
Сложность: medium

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

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

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

class Solution {
    function sortTransformedArray($nums, $a, $b, $c) {
        $transformed = array_map(function($x) use ($a, $b, $c) {
            return $a * $x * $x + $b * $x + $c;
        }, $nums);

        $this->radixSort($transformed);
        return $transformed;
    }

    private function radixSort(&$array) {
        $maxElement = max(array_map('abs', $array));
        $placeValue = 1;

        while ($maxElement / $placeValue > 0) {
            $this->countingSortByDigit($array, $placeValue);
            $placeValue *= 10;
        }

        $negatives = array_filter($array, function($x) { return $x < 0; });
        $positives = array_filter($array, function($x) { return $x >= 0; });
        sort($negatives);
        sort($positives);
        $array = array_merge($negatives, $positives);
    }

    private function countingSortByDigit(&$array, $placeValue) {
        $n = count($array);
        $output = array_fill(0, $n, 0);
        $count = array_fill(0, 10, 0);

        foreach ($array as $num) {
            $digit = (int)(abs($num) / $placeValue) % 10;
            $count[$digit]++;
        }

        for ($i = 1; $i < 10; $i++) {
            $count[$i] += $count[$i - 1];
        }

        for ($i = $n - 1; $i >= 0; $i--) {
            $num = $array[$i];
            $digit = (int)(abs($num) / $placeValue) % 10;
            $output[$count[$digit] - 1] = $num;
            $count[$digit]--;
        }

        for ($i = 0; $i < $n; $i++) {
            $array[$i] = $output[$i];
        }
    }
}

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

Задача: 121. Best Time to Buy and Sell Stock
Сложность: easy

Вам дан массив цен, где prices[i] является ценой данной акции в i-й день.

Ваша задача — максимизировать вашу прибыль, выбрав один день для покупки акции и другой день в будущем для ее продажи.

Верните максимальную прибыль, которую вы можете получить от этой операции. Если прибыль получить невозможно, верните 0.

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

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

1⃣Инициализируем minPrice значением PHP_INT_MAX, maxProfit — 0.

2⃣Проходим по всем ценам:
Если текущая цена меньше minPrice, обновляем minPrice.
Если текущая прибыль (price - minPrice) больше maxProfit, обновляем maxProfit.

3⃣Возвращаем maxProfit.

😎 Решение:

class Solution {
    public function maxProfit($prices) {
        $minPrice = PHP_INT_MAX;
        $maxProfit = 0;
        foreach ($prices as $price) {
            if ($price < $minPrice) {
                $minPrice = $price;
            } elseif ($price - $minPrice > $maxProfit) {
                $maxProfit = $price - $minPrice;
            }
        }
        return $maxProfit;
    }
}

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

Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium

Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.

Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:

Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.

Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].

Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

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

1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].

2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.

3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.

😎 Решение:

class Solution {
    public $flipped;
    public $index;
    public $voyage;

    function flipMatchVoyage($root, $voyage) {
        $this->flipped = [];
        $this->index = 0;
        $this->voyage = $voyage;

        $this->dfs($root);
        if (!empty($this->flipped) && $this->flipped[0] == -1) {
            return [-1];
        }

        return $this->flipped;
    }

    function dfs($node) {
        if ($node !== null) {
            if ($node->val != $this->voyage[$this->index++]) {
                $this->flipped = [-1];
                return;
            }

            if ($this->index < count($this->voyage) && $node->left !== null && $node->left->val != $this->voyage[$this->index]) {
                $this->flipped[] = $node->val;
                $this->dfs($node->right);
                $this->dfs($node->left);
            } else {
                $this->dfs($node->left);
                $this->dfs($node->right);
            }
        }
    }
}

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

Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy

Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.

Верните массив после сортировки.

Пример:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

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

1⃣Создание функции для подсчета единиц:
Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении.

2⃣Сортировка массива:
Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.

3⃣Возврат отсортированного массива:
Верните отсортированный массив.

😎 Решение:

class Solution {
    function sortByBits($arr) {
        usort($arr, function($a, $b) {
            $countA = substr_count(decbin($a), '1');
            $countB = substr_count(decbin($b), '1');
            return $countA === $countB ? $a - $b : $countA - $countB;
        });
        return $arr;
    }
}

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

Задача: 273. Integer to English Words
Сложность: hard

Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

class Solution {
    private $belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"];
    private $tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
    private $thousands = ["", "Thousand", "Million", "Billion"];
    
    function numberToWords($num) {
        if ($num == 0) return "Zero";
        $result = "";
        $i = 0;
        
        while ($num > 0) {
            if ($num % 1000 != 0) {
                $result = $this->helper($num % 1000) . $this->thousands[$i] . " " . $result;
            }
            $num = intval($num / 1000);
            $i++;
        }
        return trim($result);
    }

    private function helper($num) {
        if ($num == 0) return "";
        else if ($num < 20) return $this->belowTwenty[$num] . " ";
        else if ($num < 100) return $this->tens[intval($num / 10)] . " " . $this->helper($num % 10);
        else return $this->belowTwenty[intval($num / 100)] . " Hundred " . $this->helper($num % 100);
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

3⃣После каждого хода проверяйте, есть ли победитель. Если все ходы сделаны и нет победителя, проверьте, завершена ли игра вничью или еще есть ходы.

😎 Решение:

function tictactoe($moves) {
    $grid = array_fill(0, 3, array_fill(0, 3, ''));
    for ($i = 0; $i < count($moves); $i++) {
        $r = $moves[$i][0];
        $c = $moves[$i][1];
        $grid[$r][$c] = $i % 2 == 0 ? 'X' : 'O';
    }

    for ($i = 0; $i < 3; $i++) {
        if ($grid[$i][0] == $grid[$i][1] && $grid[$i][1] == $grid[$i][2] && $grid[$i][0] != '')
            return $grid[$i][0] == 'X' ? 'A' : 'B';
        if ($grid[0][$i] == $grid[1][$i] && $grid[1][$i] == $grid[2][$i] && $grid[0][$i] != '')
            return $grid[0][$i] == 'X' ? 'A' : 'B';
    }

    if ($grid[0][0] == $grid[1][1] && $grid[1][1] == $grid[2][2] && $grid[0][0] != '')
        return $grid[0][0] == 'X' ? 'A' : 'B';
    if ($grid[0][2] == $grid[1][1] && $grid[1][1] == $grid[2][0] && $grid[0][2] != '')
        return $grid[0][2] == 'X' ? 'A' : 'B';

    return count($moves) == 9 ? 'Draw' : 'Pending';
}

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

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

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

Задача: 269. Alien Dictionary
Сложность: hard

Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.
Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.
Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".
В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

1⃣Извлечение отношений порядка и создание списков смежности:
Извлечь отношения порядка между буквами из слов.
Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого.

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

function alienOrder($words) {
    $adjList = [];
    $inDegree = [];

    foreach ($words as $word) {
        foreach (str_split($word) as $char) {
            $inDegree[$char] = 0;
        }
    }

    for ($i = 0; $i < count($words) - 1; $i++) {
        $firstWord = $words[$i];
        $secondWord = $words[$i + 1];
        for ($j = 0; $j < min(strlen($firstWord), strlen($secondWord)); $j++) {
            $c = $firstWord[$j];
            $d = $secondWord[$j];
            if ($c !== $d) {
                if (!isset($adjList[$c])) {
                    $adjList[$c] = [];
                }
                if (!in_array($d, $adjList[$c])) {
                    $adjList[$c][] = $d;
                    $inDegree[$d]++;
                }
                break;
            }
        }
        if (strlen($secondWord) < strlen($firstWord) && strpos($firstWord, $secondWord) === 0) {
            return "";
        }
    }

    $output = [];
    $queue = [];

    foreach ($inDegree as $char => $degree) {
        if ($degree == 0) {
            $queue[] = $char;
        }
    }

    while (!empty($queue)) {
        $c = array_shift($queue);
        $output[] = $c;
        if (isset($adjList[$c])) {
            foreach ($adjList[$c] as $d) {
                $inDegree[$d]--;
                if ($inDegree[$d] == 0) {
                    $queue[] = $d;
                }
            }
        }
    }

    if (count($output) < count($inDegree)) {
        return "";
    }

    return implode("", $output);
}

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

Задача: 587. Erect the Fence
Сложность: hard

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.
Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.
Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке.

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

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

1⃣Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

2⃣Построение верхней оболочки:
Пройдитесь по точкам в обратном порядке, чтобы построить верхнюю оболочку.
Добавляйте точки к оболочке и удаляйте последние точки, если они не образуют против часовой стрелки поворот.

3⃣Удаление дублирующих элементов и возврат результата:
Используйте HashSet, чтобы удалить дублирующиеся точки из стека.
Преобразуйте результат в массив и верните его.

😎 Решение:

class Solution {
    private function orientation($p, $q, $r) {
        return ($q[1] - $p[1]) * ($r[0] - $q[0]) - ($q[0] - $p[0]) * ($r[1] - $q[1]);
    }

    function outerTrees($points) {
        usort($points, function($a, $b) {
            return $a[0] === $b[0] ? $a[1] - $b[1] : $a[0] - $b[0];
        });

        $hull = [];

        foreach ($points as $point) {
            while (count($hull) >= 2 && $this->orientation($hull[count($hull) - 2], $hull[count($hull) - 1], $point) > 0) {
                array_pop($hull);
            }
            $hull[] = $point;
        }

        array_pop($hull);

        for ($i = count($points) - 1; $i >= 0; $i--) {
            while (count($hull) >= 2 && $this->orientation($hull[count($hull) - 2], $hull[count($hull) - 1], $points[$i]) > 0) {
                array_pop($hull);
            }
            $hull[] = $points[$i];
        }

        $uniqueHull = [];
        foreach ($hull as $h) {
            $uniqueHull[implode(',', $h)] = $h;
        }

        return array_values($uniqueHull);
    }
}

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

Задача: 600. Non-negative Integers without Consecutive Ones
Сложность: Hard

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

class Solution {
    function findIntegers($num) {
        $count = 0;
        for ($i = 0; $i <= $num; $i++) {
            if ($this->check($i)) {
                $count++;
            }
        }
        return $count;
    }

    function check($n) {
        $i = 31;
        while ($i > 0) {
            if (($n & (1 << $i)) != 0 && ($n & (1 << ($i - 1))) != 0) {
                return false;
            }
            $i--;
        }
        return true;
    }
}

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

Задача: 401. Binary Watch
Сложность: easy

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

1⃣Генерация всех возможных комбинаций:
Переберите все возможные значения для часов и минут.
Используйте битовые операции для подсчета количества единиц в бинарном представлении числа.

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

3⃣Форматирование результата:
Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎 Решение:

class Solution {
    function readBinaryWatch($turnedOn) {
        $results = [];
        for ($h = 0; $h < 12; $h++) {
            for ($m = 0; $m < 60; $m++) {
                if (substr_count(decbin($h), '1') + substr_count(decbin($m), '1') == $turnedOn) {
                    $results[] = sprintf("%d:%02d", $h, $m);
                }
            }
        }
        return $results;
    }
}

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

3⃣Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.

😎 Решение:

class Solution {
    const WHITE = 1;
    const GRAY = 2;
    const BLACK = 3;

    public function findOrder($numCourses, $prerequisites) {
        $isPossible = true;
        $color = array_fill(0, $numCourses, self::WHITE);
        $adjList = [];
        $topologicalOrder = [];

        foreach ($prerequisites as $relation) {
            list($dest, $src) = $relation;
            if (!isset($adjList[$src])) {
                $adjList[$src] = [];
            }
            $adjList[$src][] = $dest;
        }

        for ($i = 0; $i < $numCourses && $isPossible; $i++) {
            if ($color[$i] == self::WHITE) {
                $this->dfs($i, $color, $adjList, $isPossible, $topologicalOrder);
            }
        }

        if ($isPossible) {
            $order = array_reverse($topologicalOrder);
            return $order;
        } else {
            return [];
        }
    }

    private function dfs($node, &$color, &$adjList, &$isPossible, &$topologicalOrder) {
        if (!$isPossible) return;
        $color[$node] = self::GRAY;

        if (isset($adjList[$node])) {
            foreach ($adjList[$node] as $neighbor) {
                if ($color[$neighbor] == self::WHITE) {
                    $this->dfs($neighbor, $color, $adjList, $isPossible, $topologicalOrder);
                } else if ($color[$neighbor] == self::GRAY) {
                    $isPossible = false;
                }
            }
        }

        $color[$node] = self::BLACK;
        $topologicalOrder[] = $node;
    }
}

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

1⃣Сортировка заданий:
Сначала мы сортируем задания по времени их окончания. Это позволит нам легко проверять, какие задания могут быть выбраны без пересечения с предыдущими выбранными заданиями.

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

function jobScheduling($startTime, $endTime, $profit) {
    $jobs = [];
    for ($i = 0; $i < count($startTime); $i++) {
        $jobs[] = [$endTime[$i], $startTime[$i], $profit[$i]];
    }
    usort($jobs, function($a, $b) {
        return $a[0] - $b[0];
    });

    $dp = [[0, 0]];

    foreach ($jobs as [$e, $s, $p]) {
        $i = 0;
        while ($i < count($dp) && $dp[$i][0] <= $s) $i++;
        $newProfit = $dp[$i - 1][1] + $p;
        if ($newProfit > $dp[count($dp) - 1][1]) {
            $dp[] = [$e, $newProfit];
        }
    }

    return $dp[count($dp) - 1][1];
}

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

Задача: 301. Remove Invalid Parentheses
Сложность: hard

Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой.
Верните список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке.

Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

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

1⃣Инициализация:
Инициализируйте массив, который будет хранить все допустимые выражения.
Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо.
Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно.

2⃣Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.

3⃣Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений.

😎 Решение:

class Solution {
    private $validExpressions;
    private $minimumRemoved;

    function __construct() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function reset() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function recurse($s, $index, $leftCount, $rightCount, $expression, $removedCount) {
        if ($index === strlen($s)) {
            if ($leftCount === $rightCount) {
                if ($removedCount <= $this->minimumRemoved) {
                    $possibleAnswer = implode('', $expression);
                    if ($removedCount < $this->minimumRemoved) {
                        $this->validExpressions = [];
                        $this->minimumRemoved = $removedCount;
                    }
                    $this->validExpressions[$possibleAnswer] = true;
                }
            }
            return;
        }

        $currentCharacter = $s[$index];
        $length = count($expression);

        if ($currentCharacter !== '(' && $currentCharacter !== ')') {
            array_push($expression, $currentCharacter);
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount);
            array_pop($expression);
        } else {
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount + 1);
            array_push($expression, $currentCharacter);

            if ($currentCharacter === '(') {
                $this->recurse($s, $index + 1, $leftCount + 1, $rightCount, $expression, $removedCount);
            } else if ($rightCount < $leftCount) {
                $this->recurse($s, $index + 1, $leftCount, $rightCount + 1, $expression, $removedCount);
            }

            array_pop($expression);
        }
    }

    function removeInvalidParentheses($s) {
        $this->reset();
        $this->recurse($s, 0, 0, 0, [], 0);
        return array_keys($this->validExpressions);
    }
}

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

Задача: 725. Split Linked List in Parts
Сложность: medium

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

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

1⃣Определите общую длину связного списка.

2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее.

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function splitListToParts($root, $k) {
    $length = 0;
    $node = $root;
    while ($node != null) {
        $length++;
        $node = $node->next;
    }

    $partLength = intdiv($length, $k);
    $extraParts = $length % $k;

    $parts = array_fill(0, $k, null);
    $node = $root;
    for ($i = 0; $i < $k; $i++) {
        $partHead = $node;
        $partSize = $partLength + ($i < $extraParts ? 1 : 0);
        for ($j = 0; $j < $partSize - 1; $j++) {
            if ($node != null) {
                $node = $node->next;
            }
        }
        if ($node != null) {
            $nextPart = $node->next;
            $node->next = null;
            $node = $nextPart;
        }
        $parts[$i] = $partHead;
    }

    return $parts;
}

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.
Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.
Реализуйте класс MedianFinder:
MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

class MedianFinder {
    private $numbers;

    public function __construct() {
        $this->numbers = [];
    }

    public function addNum($num) {
        $this->numbers[] = $num;
    }

    public function findMedian() {
        sort($this->numbers);
        $n = count($this->numbers);
        if ($n % 2 == 0) {
            return ($this->numbers[$n / 2 - 1] + $this->numbers[$n / 2]) / 2.0;
        } else {
            return $this->numbers[$n / 2];
        }
    }
}
?>

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