Задача: 491. Non-decreasing Subsequences
Сложность: medium

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

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

2⃣Функция обратного отслеживания
Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента.

3⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.

😎 Решение:

class Solution {
    function findSubsequences($nums) {
        $result = [];
        $sequence = [];
        $this->backtrack($nums, 0, $sequence, $result);
        return array_values($result);
    }

    private function backtrack($nums, $index, &$sequence, &$result) {
        if ($index == count($nums)) {
            if (count($sequence) >= 2) {
                $key = implode(',', $sequence);
                $result[$key] = $sequence;
            }
            return;
        }
        if (empty($sequence) || end($sequence) <= $nums[$index]) {
            $sequence[] = $nums[$index];
            $this->backtrack($nums, $index + 1, $sequence, $result);
            array_pop($sequence);
        }
        $this->backtrack($nums, $index + 1, $sequence, $result);
    }
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

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

function findHeight($root) {
    if ($root === null) return -1;
    return 1 + max(findHeight($root->left), findHeight($root->right));
}

function fill(&$res, $root, $r, $c, $height) {
    if ($root === null) return;
    $res[$r][$c] = strval($root->val);
    if ($root->left !== null) {
        fill($res, $root->left, $r + 1, $c - (1 << ($height - $r - 1)), $height);
    }
    if ($root->right !== null) {
        fill($res, $root->right, $r + 1, $c + (1 << ($height - $r - 1)), $height);
    }
}

function printTree($root) {
    $height = findHeight($root);
    $m = $height + 1;
    $n = (1 << ($height + 1)) - 1;
    $res = array_fill(0, $m, array_fill(0, $n, ""));
    fill($res, $root, 0, intval(($n - 1) / 2), $height);
    return $res;
}

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.
Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

class TrieNode {
    private $links;
    private $isEnd;

    public function __construct() {
        $this->links = array_fill(0, 26, null);
        $this->isEnd = false;
    }

    public function containsKey($ch) {
        return $this->links[ord($ch) - ord('a')] !== null;
    }

    public function get($ch) {
        return $this->links[ord($ch) - ord('a')];
    }

    public function put($ch, $node) {
        $this->links[ord($ch) - ord('a')] = $node;
    }

    public function setEnd() {
        $this->isEnd = true;
    }

    public function isEndNode() {
        return $this->isEnd;
    }
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!$node->containsKey($ch)) {
                $node->put($ch, new TrieNode());
            }
            $node = $node->get($ch);
        }
        $node->setEnd();
    }

    private function searchPrefix($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if ($node->containsKey($ch)) {
                $node = $node->get($ch);
            } else {
                return null;
            }
        }
        return $node;
    }

    public function search($word) {
        $node = $this->searchPrefix($word);
        return $node !== null && $node->isEndNode();
    }

    public function startsWith($prefix) {
        return $this->searchPrefix($prefix) !== null;
    }
}

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

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

😎 Решение:

function minMalwareSpread($graph, $initial) {
    $n = count($graph);
    $components = [];
    $visited = [];
    
    function dfs($graph, $node, &$component, &$visited) {
        $stack = [$node];
        while (!empty($stack)) {
            $u = array_pop($stack);
            if (!isset($visited[$u])) {
                $visited[$u] = true;
                $component[] = $u;
                foreach ($graph[$u] as $v => $connected) {
                    if ($connected == 1 && !isset($visited[$v])) {
                        $stack[] = $v;
                    }
                }
            }
        }
    }
    
    for ($i = 0; $i < $n; $i++) {
        if (!isset($visited[$i])) {
            $component = [];
            dfs($graph, $i, $component, $visited);
            $components[] = $component;
        }
    }
    
    $infectedInComponent = array_fill(0, count($components), 0);
    $nodeToComponent = array_fill(0, $n, -1);
    
    foreach ($components as $idx => $component) {
        foreach ($component as $node) {
            $nodeToComponent[$node] = $idx;
            if (in_array($node, $initial)) {
                $infectedInComponent[$idx]++;
            }
        }
    }
    
    $minInfected = PHP_INT_MAX;
    $resultNode = min($initial);
    
    foreach ($initial as $node) {
        $componentIdx = $nodeToComponent[$node];
        if ($infectedInComponent[$componentIdx] == 1) {
            $componentSize = count($components[$componentIdx]);
            if ($componentSize < $minInfected || ($componentSize == $minInfected && $node < $resultNode)) {
                $minInfected = $componentSize;
                $resultNode = $node;
            }
        }
    }
    
    return $resultNode;
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

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

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

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

3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎 Решение:

function longestWord($words) {
    sort($words);
    $validWords = ["" => true];
    $longest = "";
    foreach ($words as $word) {
        if (isset($validWords[substr($word, 0, -1)])) {
            $validWords[$word] = true;
            if (strlen($word) > strlen($longest)) {
                $longest = $word;
            }
        }
    }
    return $longest;
}

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

Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

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

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

function networkDelayTime($times, $n, $k) {
    $graph = [];
    for ($i = 1; $i <= $n; $i++) {
        $graph[$i] = [];
    }
    foreach ($times as $time) {
        $graph[$time[0]][] = [$time[1], $time[2]];
    }

    $minHeap = new SplPriorityQueue();
    $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $minHeap->insert([$k, 0], 0);
    $minTime = array_fill(1, $n, INF);
    $minTime[$k] = 0;

    while (!$minHeap->isEmpty()) {
        $data = $minHeap->extract();
        $time = $data['priority'];
        $node = $data['data'][0];
        foreach ($graph[$node] as $neighbor) {
            $newTime = $time + $neighbor[1];
            if ($newTime < $minTime[$neighbor[0]]) {
                $minTime[$neighbor[0]] = $newTime;
                $minHeap->insert([$neighbor[0], $newTime], -$newTime);
            }
        }
    }

    $maxTime = max($minTime);
    return $maxTime == INF ? -1 : $maxTime;
}

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

Input: nums = [1,2,3,3,4,5]
Output: true

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

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

2⃣Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

class Solution {
    function isPossible($nums) {
        $freq = array_count_values($nums);
        $need = [];
        
        foreach ($nums as $num) {
            if ($freq[$num] == 0) continue;

            if (isset($need[$num]) && $need[$num] > 0) {
                $need[$num]--;
                $need[$num + 1] = isset($need[$num + 1]) ? $need[$num + 1] + 1 : 1;
            } elseif (isset($freq[$num + 1]) && $freq[$num + 1] > 0 && isset($freq[$num + 2]) && $freq[$num + 2] > 0) {
                $freq[$num + 1]--;
                $freq[$num + 2]--;
                $need[$num + 3] = isset($need[$num + 3]) ? $need[$num + 3] + 1 : 1;
            } else {
                return false;
            }
            $freq[$num]--;
        }
        
        return true;
    }
}

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.
Вы ограничены следующими правилами:
Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution {
    function generatePossibleResults($a, $b) {
        $res = [$a + $b, $a - $b, $b - $a, $a * $b];
        if ($a != 0) $res[] = $b / $a;
        if ($b != 0) $res[] = $a / $b;
        return $res;
    }

    function checkIfResultReached($list) {
        if (count($list) == 1) return abs($list[0] - 24) <= 0.1;

        for ($i = 0; $i < count($list); $i++) {
            for ($j = $i + 1; $j < count($list); $j++) {
                $newList = [];
                for ($k = 0; $k < count($list); $k++) {
                    if ($k != $i && $k != $j) $newList[] = $list[$k];
                }
                foreach ($this->generatePossibleResults($list[$i], $list[$j]) as $res) {
                    $newList[] = $res;
                    if ($this->checkIfResultReached($newList)) return true;
                    array_pop($newList);
                }
            }
        }
        return false;
    }

    function judgePoint24($cards) {
        return $this->checkIfResultReached(array_map('floatval', $cards));
    }
}

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

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

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