Задача: 330. Patching Array
Сложность: hard

Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива.
Верните минимальное количество дополнений, необходимых для этого.

Пример:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

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

1⃣Инициализация переменных:
Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums.

2⃣Основной цикл:
Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n.
Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches.

3⃣Возврат результата:
После завершения цикла верните значение patches, которое представляет минимальное количество необходимых дополнений.

😎 Решение:

class Solution {
    function minPatches($nums, $n) {
        $patches = 0;
        $i = 0;
        $miss = 1;
        while ($miss <= $n) {
            if ($i < count($nums) && $nums[$i] <= $miss) {
                $miss += $nums[$i++];
            } else {
                $miss += $miss;
                $patches++;
            }
        }
        return $patches;
    }
}

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

Задача №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

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

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

3⃣Добавлять полученные комбинации в результирующий массив.

😎 Решение:

class Solution { 
 
    public $result = []; 
 
    function letterCombinations($digits) { 
        if(strlen($digits) == 0) { 
            return []; 
        } 
 
        $layouts = [ 
            2 => range('a', 'c'), 
            3 => range('d', 'f'), 
            4 => range('g', 'i'), 
            5 => range('j', 'l'),  
            6 => range('m', 'o'),  
            7 => range('p', 's'), 
            8 => range('t', 'v'), 
            9 => range('w', 'z'), 
        ]; 
 
        return $this->recursive(0, $digits, $layouts); 
    } 
 
    function recursive ($index, $chars, $layouts, $combine = '') { 
        foreach($layouts[$chars[$index]] as $currentLayout) { 
            if($layouts[$chars[$index + 1]]) { 
                $this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout); 
            } else { 
                $this->result[] = $combine . $currentLayout; 
            } 
        } 
 
        return $this->result; 
    } 
}

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

Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

1⃣Инициализация
Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack.

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

3⃣Возврат результата
Верните список output как результат.

😎 Решение:

class Node {
    public $val;
    public $children;

    function __construct($val = 0, $children = []) {
        $this->val = $val;
        $this->children = $children;
    }
}

class Solution {
    function preorder($root) {
        if ($root === null) return [];
        $stack = [$root];
        $output = [];
        
        while (!empty($stack)) {
            $node = array_pop($stack);
            $output[] = $node->val;
            $children = array_reverse($node->children);
            foreach ($children as $child) {
                $stack[] = $child;
            }
        }
        
        return $output;
    }
}

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

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

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

function treeDiameter($edges) {
    if (count($edges) === 0) return 0;

    $graph = [];
    foreach ($edges as $edge) {
        if (!isset($graph[$edge[0]])) $graph[$edge[0]] = [];
        if (!isset($graph[$edge[1]])) $graph[$edge[1]] = [];
        $graph[$edge[0]][] = $edge[1];
        $graph[$edge[1]][] = $edge[0];
    }

    $farthestNode = 0;

    function dfs($node, $parent, &$graph, &$farthestNode) {
        $maxDepth = 0;
        foreach ($graph[$node] as $neighbor) {
            if ($neighbor !== $parent) {
                $depth = dfs($neighbor, $node, $graph, $farthestNode);
                if ($depth + 1 > $maxDepth) {
                    $maxDepth = $depth + 1;
                    $farthestNode = $neighbor;
                }
            }
        }
        return $maxDepth;
    }

    dfs(0, -1, $graph, $farthestNode);
    $startNode = $farthestNode;

    dfs($startNode, -1, $graph, $farthestNode);
    return dfs($farthestNode, -1, $graph, $farthestNode);
}

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter {
    private $prefixSuffixMap = [];
    
    function __construct($words) {
        foreach ($words as $index => $word) {
            $length = strlen($word);
            for ($prefixLength = 1; $prefixLength <= $length; $prefixLength++) {
                for ($suffixLength = 1; $suffixLength <= $length; $suffixLength++) {
                    $prefix = substr($word, 0, $prefixLength);
                    $suffix = substr($word, $length - $suffixLength);
                    $key = $prefix . '#' . $suffix;
                    $this->prefixSuffixMap[$key] = $index;
                }
            }
        }
    }
    
    function f($pref, $suff) {
        $key = $pref . '#' . $suff;
        return array_key_exists($key, $this->prefixSuffixMap) ? $this->prefixSuffixMap[$key] : -1;
    }
}

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

Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

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

3⃣Верни максимальную длину среди всех цепочек.

😎 Решение:

function longestStrChain($words) {
    usort($words, function($a, $b) {
        return strlen($a) - strlen($b);
    });
    
    $dp = [];
    $longestChain = 1;
    
    foreach ($words as $word) {
        $dp[$word] = 1;
        for ($i = 0; $i < strlen($word); $i++) {
            $predecessor = substr($word, 0, $i) . substr($word, $i + 1);
            if (isset($dp[$predecessor])) {
                $dp[$word] = max($dp[$word], $dp[$predecessor] + 1);
            }
        }
        $longestChain = max($longestChain, $dp[$word]);
    }
    
    return $longestChain;
}

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

Задача: 606. Construct String from Binary Tree
Сложность: medium

Дано бинарное дерево, необходимо вернуть его строковое представление, используя прямой обход (preorder traversal) и правила со скобками:
Скобки для детей обязательны, если есть правый ребёнок
Пропускать пустые скобки, кроме случая, когда отсутствует левый, но есть правый ребёнок

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

class Solution {
    function tree2str($t) {
        $res = "";
        $this->dfs($t, $res);
        return $res;
    }

    function dfs($t, &$res) {
        if ($t == null)
            return;
        $res .= $t->val;
        if ($t->left == null && $t->right == null)
            return;
        $res .= '(';
        $this->dfs($t->left, $res);
        $res .= ')';
        if ($t->right != null) {
            $res .= '(';
            $this->dfs($t->right, $res);
            $res .= ')';
        }
    }
}

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

Задача: 1065. Index Pairs of a String
Сложность: easy

Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words.

Верните пары [i, j] в отсортированном порядке (то есть отсортируйте их по первой координате, а в случае совпадения сортируйте их по второй координате).

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Поддерживайте хэш-набор слов.

2⃣Итерируйте i от 0 до text.length-1. Итерируйте j от i до text.length-1. Если подстрока text[i...j] принадлежит хэш-набору слов, добавьте пару [i, j] в ответ.

3⃣Верните ответ.

😎 Решение:

class Solution {
    function indexPairs($text, $words) {
        $wordsSet = array_flip($words);
        $ans = [];
        
        for ($i = 0; $i < strlen($text); $i++) {
            for ($j = $i; $j < strlen($text); $j++) {
                if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
                    $ans[] = [$i, $j];
                }
            }
        }
        return $ans;
    }
}

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

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

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

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

function isBoomerang($points) {
    list($x1, $y1) = $points[0];
    list($x2, $y2) = $points[1];
    list($x3, $y3) = $points[2];
    return ($x1 != $x2 || $y1 != $y2) && 
           ($x1 != $x3 || $y1 != $y3) && 
           ($x2 != $x3 || $y2 != $y3) && 
           ($x1 * ($y2 - $y3) + $x2 * ($y3 - $y1) + $x3 * ($y1 - $y2)) != 0;
}

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

Задача: 666. Path Sum IV
Сложность: medium

Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

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

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

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

class Solution {
    function pathSum($nums) {
        $tree = [];
        
        foreach ($nums as $num) {
            $depth = intdiv($num, 100);
            $pos = intdiv($num, 10) % 10;
            $val = $num % 10;
            $tree[$depth * 10 + $pos] = $val;
        }
        
        return $this->dfs($tree, 1, 1, 0);
    }
    
    private function dfs($tree, $depth, $pos, $currentSum) {
        $key = $depth * 10 + $pos;
        if (!isset($tree[$key])) {
            return 0;
        }
        $currentSum += $tree[$key];
        $leftChild = ($depth + 1) * 10 + 2 * $pos - 1;
        $rightChild = ($depth + 1) * 10 + 2 * $pos;
        if (!isset($tree[$leftChild]) && !isset($tree[$rightChild])) {
            return $currentSum;
        }
        return $this->dfs($tree, $depth + 1, 2 * $pos - 1, $currentSum) + $this->dfs($tree, $depth + 1, 2 * $pos, $currentSum);
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

Создайте структуру данных, которая будет инициализироваться массивом строк, а затем должна отвечать на запросы о наименьшем расстоянии между двумя разными строками из массива.
Реализуйте класс WordDistance:
WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

// PHP
class WordDistance {
    private $locations;

    function __construct($words) {
        $this->locations = [];
        foreach ($words as $i => $word) {
            if (!isset($this->locations[$word])) {
                $this->locations[$word] = [];
            }
            $this->locations[$word][] = $i;
        }
    }

    function shortest($word1, $word2) {
        $loc1 = $this->locations[$word1];
        $loc2 = $this->locations[$word2];
        $l1 = 0;
        $l2 = 0;
        $minDiff = PHP_INT_MAX;

        while ($l1 < count($loc1) && $l2 < count($loc2)) {
            $minDiff = min($minDiff, abs($loc1[$l1] - $loc2[$l2]));
            if ($loc1[$l1] < $loc2[$l2]) {
                $l1++;
            } else {
                $l2++;
            }
        }
        return $minDiff;

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

Задача: 563. Binary Tree Tilt
Сложность: easy

Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.
Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

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

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;
    }
}

class Solution {
    private $totalTilt = 0;
    
    function findTilt($root) {
        $this->sumAndTilt($root);
        return $this->totalTilt;
    }
    
    private function sumAndTilt($node) {
        if ($node === null) {
            return 0;
        }
        $leftSum = $this->sumAndTilt($node->left);
        $rightSum = $this->sumAndTilt($node->right);
        $nodeTilt = abs($leftSum - $rightSum);
        $this->totalTilt += $nodeTilt;
        return $node->val + $leftSum + $rightSum;
    }
}

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

Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
    private $inorderNodes = [];
    
    private function inorderTraversal($root) {
        if ($root === null) {
            return;
        }
        
        $this->inorderTraversal($root->left);
        $this->inorderNodes[] = $root->val;
        $this->inorderTraversal($root->right);
    }
    
    public function minDiffInBST($root) {
        $this->inorderTraversal($root);
        
        $minDistance = PHP_INT_MAX;
        for ($i = 1; $i < count($this->inorderNodes); $i++) {
            $minDistance = min($minDistance, $this->inorderNodes[$i] - $this->inorderNodes[$i - 1]);
        }
        
        return $minDistance;
    }
}

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

Задача: 990. Satisfiability of Equality Equations
Сложность: medium

Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.

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

Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

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

1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.

2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.

3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.

😎 Решение:

class UnionFind {
    private $parent;

    public function __construct($size) {
        $this->parent = range(0, $size - 1);
    }

    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX != $rootY) {
            $this->parent[$rootX] = $rootY;
        }
    }

    public function connected($x, $y) {
        return $this->find($x) == $this->find($y);
    }
}

class Solution {
    function equationsPossible($equations) {
        $uf = new UnionFind(26);
        
        foreach ($equations as $eq) {
            if ($eq[1] == '=') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                $uf->union($x, $y);
            }
        }
        
        foreach ($equations as $eq) {
            if ($eq[1] == '!') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                if ($uf->connected($x, $y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

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

Задача: 913. Cat and Mouse4
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

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

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

function catMouseGame($graph) {
    $n = count($graph);
    $DRAW = 0; $MOUSE = 1; $CAT = 2;
    $dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2, $DRAW)));
    $queue = [];

    for ($i = 1; $i < $n; $i++) {
        $dp[0][$i][0] = $MOUSE;
        $dp[0][$i][1] = $MOUSE;
        $dp[$i][$i][0] = $CAT;
        $dp[$i][$i][1] = $CAT;
        $queue[] = [0, $i, 0, $MOUSE];
        $queue[] = [0, $i, 1, $MOUSE];
        $queue[] = [$i, $i, 0, $CAT];
        $queue[] = [$i, $i, 1, $CAT];
    }

    function parents($graph, $mouse, $cat, $turn) {
        $res = [];
        if ($turn == 1) {
            foreach ($graph[$mouse] as $m) {
                $res[] = [$m, $cat, 0];
            }
        } else {
            foreach ($graph[$cat] as $c) {
                if ($c > 0) $res[] = [$mouse, $c, 1];
            }
        }
        return $res;
    }

    while (!empty($queue)) {
        list($mouse, $cat, $turn, $winner) = array_shift($queue);
        foreach (parents($graph, $mouse, $cat, $turn) as list($m, $c, $t)) {
            if ($dp[$m][$c][$t] == $DRAW) {
                if (($t == 0 && $winner == $MOUSE) || ($t == 1 && $winner == $CAT)) {
                    $dp[$m][$c][$t] = $winner;
                    $queue[] = [$m, $c, $t, $winner];
                } else {
                    $degrees = 0;
                    foreach (parents($graph, $m, $c, $t) as $_) $degrees++;
                    if ($degrees == 0) {
                        $dp[$m][$c][$t] = $winner;
                        $queue[] = [$m, $c, $t, $winner];
                    }
                }
            }
        }
    }

    return $dp[1][2][0];
}

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

Задача: 88. Merge Sorted Array
Сложность: easy

Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.

Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.

Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.

Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

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

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

2⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1.
Инициализируйте указатель для чтения p1 в начале nums1Copy.
Инициализируйте указатель для чтения p2 в начале nums2.

3⃣Инициализируйте указатель для записи p в начале nums1.
Пока p все еще находится внутри nums1:
Если nums1Copy[p1] существует и меньше или равно nums2[p2]:
Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1.
Иначе
Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1.
Увеличьте p на 1.

😎 Решение:

class Solution {

    public function merge(&$nums1, $m, $nums2, $n) {
        $nums1Copy = array_slice($nums1, 0, $m);
        $p1 = 0;
        $p2 = 0;
        
        for ($p = 0; $p < $n + $m; $p++) {
            if ($p2 >= $n || ($p1 < $m && $nums1Copy[$p1] <= $nums2[$p2])) {
                $nums1[$p] = $nums1Copy[$p1];
                $p1++;
            } else {
                $nums1[$p] = $nums2[$p2];
                $p2++;
            }
        }
    }
}

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

Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium

Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.

Пример:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

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

1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).

2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.

3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.

😎 Решение:

class CustomFunction {
    public function f($x, $y) {}
}

function findSolution($customfunction, $z) {
    $result = [];
    $x = 1;
    $y = 1000;
    
    while ($x <= 1000 && $y >= 1) {
        $value = $customfunction->f($x, $y);
        if ($value == $z) {
            $result[] = [$x, $y];
            $x++;
        } else if ($value < $z) {
            $x++;
        } else {
            $y--;
        }
    }
    
    return $result;
}

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

Задача: 45. Jump Game II
Сложность: medium

Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].
Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:
0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].

Пример:

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

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

1⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.

2⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).

3⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.

😎 Решение:

function jump($nums) {
    $answer = 0;
    $n = count($nums);
    $curEnd = 0;
    $curFar = 0;
    for ($i = 0; $i < $n - 1; ++$i) {
        $curFar = max($curFar, $i + $nums[$i]);
        if ($i === $curEnd) {
            ++$answer;
            $curEnd = $curFar;
        }
    }
    return $answer;
}

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