Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard

Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

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

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

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

😎 Решение:

class TreeNode {
    public $val = 0;
    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 {
    function recoverFromPreorder($S) {
        $stack = [];
        $i = 0;
        
        while ($i < strlen($S)) {
            $level = 0;
            while ($i < strlen($S) && $S[$i] == '-') {
                $level++;
                $i++;
            }
            
            $value = 0;
            while ($i < strlen($S) && is_numeric($S[$i])) {
                $value = $value * 10 + intval($S[$i]);
                $i++;
            }
            
            $node = new TreeNode($value);
            if ($level == count($stack)) {
                if (!empty($stack)) {
                    $stack[count($stack) - 1]->left = $node;
                }
            } else {
                while ($level != count($stack)) {
                    array_pop($stack);
                }
                $stack[count($stack) - 1]->right = $node;
            }
            array_push($stack, $node);
        }
        
        while (count($stack) > 1) {
            array_pop($stack);
        }
        
        return $stack[0];
    }
}

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

Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

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

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

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 FindElements {
    private $root;
    private $values;

    function __construct($root) {
        $this->root = $root;
        $this->values = [];
        $this->root->val = 0;
        $this->values[0] = true;
        $this->recover($root);
    }
    
    function recover($node) {
        if ($node->left !== null) {
            $node->left->val = 2 * $node->val + 1;
            $this->values[$node->left->val] = true;
            $this->recover($node->left);
        }
        if ($node->right !== null) {
            $node->right->val = 2 * $node->val + 2;
            $this->values[$node->right->val] = true;
            $this->recover($node->right);
        }
    }
    
    function find($target) {
        return isset($this->values[$target]);
    }
}

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

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

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

Пример:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

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

1⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1.

2⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов.

3⃣Пока очередь не пуста:
Извлеките первый узел из очереди.
Увеличьте nodesVisited на 1.
Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor.
Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь.
Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses.

😎 Решение:

class Solution {
    function canFinish($numCourses, $prerequisites) {
        $indegree = array_fill(0, $numCourses, 0);
        $adj = array_fill(0, $numCourses, []);

        foreach ($prerequisites as $prerequisite) {
            $adj[$prerequisite[1]][] = $prerequisite[0];
            $indegree[$prerequisite[0]]++;
        }

        $q = [];
        for ($i = 0; $i < $numCourses; $i++) {
            if ($indegree[$i] == 0) {
                $q[] = $i;
            }
        }

        $nodesVisited = 0;
        while (!empty($q)) {
            $node = array_shift($q);
            $nodesVisited++;

            foreach ($adj[$node] as $neighbor) {
                $indegree[$neighbor]--;
                if ($indegree[$neighbor] == 0) {
                    $q[] = $neighbor;
                }
            }
        }

        return $nodesVisited == $numCourses;
    }
}

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

Задача: 46. Permutations
Сложность: medium

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

Пример:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

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

1⃣Если длина curr равна длине nums, добавьте копию curr в ans и вернитесь.

2⃣Итерируйтесь по nums. Для каждого num, если num не в curr, выполните следующее:
Добавьте num в curr и вызовите backtrack(curr), затем удалите num из curr.

3⃣Вызовите backtrack с изначально пустым curr.
Верните ans.

😎 Решение:

function permute($nums) {
    $ans = [];
    $backtrack = function (&$curr) use (&$ans, &$backtrack, $nums) {
        if (count($curr) === count($nums)) {
            $ans[] = $curr;
            return;
        }
        foreach ($nums as $num) {
            if (!in_array($num, $curr)) {
                $curr[] = $num;
                $backtrack($curr);
                array_pop($curr);
            }
        }
    };
    $backtrack([]);
    return $ans;
}

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

Задача: 1539. Kth Missing Positive Number
Сложность: easy

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

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение:

class Solution {
    function findKthPositive($arr, $k) {
        if ($k <= $arr[0] - 1) {
            return $k;
        }
        $k -= $arr[0] - 1;
        $n = count($arr);
        for ($i = 0; $i < $n - 1; ++$i) {
            $currMissing = $arr[$i + 1] - $arr[$i] - 1;
            if ($k <= $currMissing) {
                return $arr[$i] + $k;
            }
            $k -= $currMissing;
        }
        return $arr[$n - 1] + $k;
    }
}

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.
Возвращает после добавления тегов, выделенных жирным шрифтом. Возвращаемая строка должна содержать как можно меньшее количество тегов, и теги должны образовывать допустимую комбинацию.

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

function addBoldTags($keywords, $s) {
    $n = strlen($s);
    $bold = array_fill(0, $n, false);
    
    foreach ($keywords as $word) {
        $start = strpos($s, $word);
        while ($start !== false) {
            for ($i = $start; $i < $start + strlen($word); $i++) {
                $bold[$i] = true;
            }
            $start = strpos($s, $word, $start + 1);
        }
    }
    
    $result = '';
    $i = 0;
    while ($i < $n) {
        if ($bold[$i]) {
            $result .= '<b>';
            while ($i < $n && $bold[$i]) {
                $result .= $s[$i];
                $i++;
            }
            $result .= '</b>';
        } else {
            $result .= $s[$i];
            $i++;
        }
    }
    
    return $result;
}

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

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

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
    function isSubsequence($x, $y) {
        $j = 0;
        for ($i = 0; $i < strlen($y) && $j < strlen($x); $i++) {
            if ($x[$j] == $y[$i]) {
                $j++;
            }
        }
        return $j == strlen($x);
    }

    function findLongestWord($s, $d) {
        $max_str = "";
        foreach ($d as $str) {
            if ($this->isSubsequence($str, $s)) {
                if (strlen($str) > strlen($max_str) || (strlen($str) == strlen($max_str) && strcmp($str, $max_str) < 0)) {
                    $max_str = $str;
                }
            }
        }
        return $max_str;
    }
}

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

Задача: 227. Basic Calculator II
Сложность: medium

Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.
Целочисленное деление должно округляться к нулю.
Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval().

Пример:

Input: s = "3+2*2"
Output: 7

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

1⃣Вместо использования стека, используем переменную lastNumber для отслеживания значения последнего вычисленного выражения.

2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации.

3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки.

😎 Решение:

class Solution {
    function calculate($s) {
        $length = strlen($s);
        if ($length == 0) return 0;
        $currentNumber = 0;
        $lastNumber = 0;
        $result = 0;
        $sign = '+';
        
        for ($i = 0; $i < $length; $i++) {
            $currentChar = $s[$i];
            if (ctype_digit($currentChar)) {
                $currentNumber = ($currentNumber * 10) + intval($currentChar);
            }
            if (!ctype_digit($currentChar) && !ctype_space($currentChar) || $i == $length - 1) {
                if ($sign == '+' || $sign == '-') {
                    $result += $lastNumber;
                    $lastNumber = ($sign == '+') ? $currentNumber : -$currentNumber;
                } else if ($sign == '*') {
                    $lastNumber *= $currentNumber;
                } else if ($sign == '/') {
                    $lastNumber /= $currentNumber;
                }
                $sign = $currentChar;
                $currentNumber = 0;
            }
        }
        $result += $lastNumber;
        return $result;  
    }
}

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

Задача: 127. Word Ladder
Сложность: Hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:
Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

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

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

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

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

function ladderLength($beginWord, $endWord, $wordList) {
    $L = strlen($beginWord);
    $allComboDict = [];
    foreach ($wordList as $word) {
        for ($i = 0; $i < $L; $i++) {
            $newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
            if (!isset($allComboDict[$newWord])) {
                $allComboDict[$newWord] = [];
            }
            $allComboDict[$newWord][] = $word;
        }
    }

    $queue = [[$beginWord, 1]];
    $visited = [$beginWord => true];
    while (count($queue) > 0) {
        $node = array_shift($queue);
        $word = $node[0];
        $level = $node[1];
        for ($i = 0; $i < $L; $i++) {
            $newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
            if (!isset($allComboDict[$newWord])) {
                $allComboDict[$newWord] = [];
            }
            foreach ($allComboDict[$newWord] as $adjacentWord) {
                if ($adjacentWord === $endWord) {
                    return $level + 1;
                }
                if (!isset($visited[$adjacentWord])) {
                    $visited[$adjacentWord] = true;
                    $queue[] = [$adjacentWord, $level + 1];
                }
            }
        }
    }

    return 0;
}

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

Задача: 320. Generalized Abbreviation
Сложность: medium

Обобщённая аббревиатура слова может быть построена путём замены несмежных и неперекрывающихся подстрок на их длины.
Например, для слова "abcde" возможны сокращения:
"a3e" — "bcd" заменено на "3"
"1bcd1" — "a" и "e" заменены на "1"
"5" — всё слово заменено на длину
"abcde" — без сокращений
Недопустимы:
"23" — замены "ab" и "cde" смежны
"22de" — замены "ab" и "bc" перекрываются
Нужно вернуть все возможные обобщённые аббревиатуры слова word.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

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

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

class Solution {
    function generateAbbreviations($word) {
        $result = [];
        $n = strlen($word);
        
        for ($x = 0; $x < (1 << $n); $x++) {
            $result[] = $this->abbr($word, $x);
        }
        
        return $result;
    }

    private function abbr($word, $x) {
        $builder = "";
        $k = 0;
        $n = strlen($word);
        
        for ($i = 0; $i < $n; $i++, $x >>= 1) {
            if (($x & 1) == 0) {
                if ($k != 0) {
                    $builder .= $k;
                    $k = 0;
                }
                $builder .= $word[$i];
            } else {
                $k++;
            }
        }
        
        if ($k != 0) $builder .= $k;
        return $builder;
    }
}

$sol = new Solution();
print_r($sol->generateAbbreviations("word"));

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

class Solution {
    function maxScoreSightseeingPair($values) {
        $maxScore = 0;
        $maxIPlusValue = $values[0];
        
        for ($j = 1; $j < count($values); $j++) {
            $maxScore = max($maxScore, $maxIPlusValue + $values[$j] - $j);
            $maxIPlusValue = max($maxIPlusValue, $values[$j] + $j);
        }
        
        return $maxScore;
    }
}

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

Задача: 940. Distinct Subsequences II4
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

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

3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎 Решение:

function countSubsequences($s) {
    $MOD = 1000000007;
    $dp = array_fill(0, 26, 0);
    foreach (str_split($s) as $c) {
        $index = ord($c) - ord('a');
        $dp[$index] = (array_sum($dp) + 1) % $MOD;
    }
    return array_sum($dp) % $MOD;
}

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

Задача: 834. Sum of Distances in Tree
Сложность: hard

Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.

Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.

Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.

Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

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

2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.

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

😎 Решение:

class Solution {
    private $ans;
    private $count;
    private $graph;
    private $N;

    function sumOfDistancesInTree($N, $edges) {
        $this->N = $N;
        $this->graph = array_fill(0, $N, []);
        $this->ans = array_fill(0, $N, 0);
        $this->count = array_fill(0, $N, 1);

        foreach ($edges as $edge) {
            $this->graph[$edge[0]][] = $edge[1];
            $this->graph[$edge[1]][] = $edge[0];
        }

        $this->dfs(0, -1);
        $this->dfs2(0, -1);
        return $this->ans;
    }

    function dfs($node, $parent) {
        foreach ($this->graph[$node] as $child) {
            if ($child != $parent) {
                $this->dfs($child, $node);
                $this->count[$node] += $this->count[$child];
                $this->ans[$node] += $this->ans[$child] + $this->count[$child];
            }
        }
    }

    function dfs2($node, $parent) {
        foreach ($this->graph[$node] as $child) {
            if ($child != $parent) {
                $this->ans[$child] = $this->ans[$node] - $this->count[$child] + $this->N - $this->count[$child];
                $this->dfs2($child, $node);
            }
        }
    }
}

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

Задача: 268. Missing Number
Сложность: easy

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

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

😎 Решение:

class Solution {
    function missingNumber($nums) {
        sort($nums);
        if ($nums[count($nums) - 1] != count($nums)) {
            return count($nums);
        } else if ($nums[0] != 0) {
            return 0;
        }
        for ($i = 1; $i < count($nums); $i++) {
            $expectedNum = $nums[$i - 1] + 1;
            if ($nums[$i] != $expectedNum) {
                return $expectedNum;
            }
        }
        return -1;
    }
}

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

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

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

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

class Solution {
    function twoCitySchedCost($costs) {
        usort($costs, function($a, $b) {
            return ($a[0] - $a[1]) - ($b[0] - $b[1]);
        });
        $totalCost = 0;
        $n = count($costs) / 2;
        for ($i = 0; $i < $n; $i++) {
            $totalCost += $costs[$i][0];
            $totalCost += $costs[$i + $n][1];
        }
        return $totalCost;
    }
}

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

Задача: 664. Strange Printer
Сложность: hard

Существует странный принтер с двумя особыми свойствами:

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

Пример:

Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

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

1⃣Инициализация и подсчет:
Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1].

2⃣Динамическое программирование:
Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим.
В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов.


3⃣Возврат результата:
Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки.

😎 Решение:

class Solution {
    function strangePrinter($s) {
        $n = strlen($s);
        $dp = array_fill(0, $n, array_fill(0, $n, 0));
        
        for ($length = 1; $length <= $n; $length++) {
            for ($i = 0; $i <= $n - $length; $i++) {
                $j = $i + $length - 1;
                $dp[$i][$j] = ($i === $j) ? 1 : $dp[$i][$j - 1] + 1;
                for ($k = $i; $k < $j; $k++) {
                    if ($s[$k] === $s[$j]) {
                        $dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + ($k + 1 <= $j - 1 ? $dp[$k + 1][$j - 1] : 0));
                    }
                }
            }
        }
        return $dp[0][$n - 1];
    }
}

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

Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard

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

Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.

Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.

Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

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

1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.

2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.

3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.

😎 Решение:

class Solution {
    function numSubmatrixSumTarget($matrix, $target) {
        $r = count($matrix);
        $c = count($matrix[0]);
        $ps = array_fill(0, $r + 1, array_fill(0, $c + 1, 0));
        
        for ($i = 1; $i <= $r; ++$i) {
            for ($j = 1; $j <= $c; ++$j) {
                $ps[$i][$j] = $ps[$i - 1][$j] + $ps[$i][$j - 1] - $ps[$i - 1][$j - 1] + $matrix[$i - 1][$j - 1];
            }
        }
        
        $count = 0;
        
        for ($r1 = 1; $r1 <= $r; ++$r1) {
            for ($r2 = $r1; $r2 <= $r; ++$r2) {
                $h = array();
                $h[0] = 1;
                for ($col = 1; $col <= $c; ++$col) {
                    $currSum = $ps[$r2][$col] - $ps[$r1 - 1][$col];
                    if (isset($h[$currSum - $target])) {
                        $count += $h[$currSum - $target];
                    }
                    if (isset($h[$currSum])) {
                        $h[$currSum]++;
                    } else {
                        $h[$currSum] = 1;
                    }
                }
            }
        }
        
        return $count;
    }
}

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

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

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

Задача: 988. Smallest String Starting From Leaf
Сложность: medium

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.

Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

1⃣Инициализация и подготовка:
Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк).
Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы.

2⃣Обход дерева:
Если текущий узел пуст (null), просто вернитесь из функции.
Добавьте текущий символ (соответствующий значению узла) в начало строки пути.
Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше.
Рекурсивно вызовите dfs для левого и правого потомков текущего узла.

3⃣Возврат результата:
Вызовите функцию dfs с корневым узлом и пустым путем.
Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня.

😎 Решение:

class Solution {
    private $ans = "~";

    function smallestFromLeaf($root) {
        $this->dfs($root, "");
        return $this->ans;
    }

    private function dfs($node, $path) {
        if ($node === null) return;
        $path = chr($node->val + ord('a')) . $path;
        if ($node->left === null && $node->right === null) {
            if (strcmp($path, $this->ans) < 0) {
                $this->ans = $path;
            }
        }
        $this->dfs($node->left, $path);
        $this->dfs($node->right, $path);
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    function wordPatternMatch($pattern, $s) {
        $symbolMap = [];
        $wordSet = [];
        return $this->isMatch($s, 0, $pattern, 0, $symbolMap, $wordSet);
    }

    private function isMatch($s, $sIndex, $pattern, $pIndex, &$symbolMap, &$wordSet) {
        if ($pIndex == strlen($pattern)) {
            return $sIndex == strlen($s);
        }
        $symbol = $pattern[$pIndex];
        if (isset($symbolMap[$symbol])) {
            $word = $symbolMap[$symbol];
            if (substr($s, $sIndex, strlen($word)) !== $word) {
                return false;
            }
            return $this->isMatch($s, $sIndex + strlen($word), $pattern, $pIndex + 1, $symbolMap, $wordSet);
        }
        for ($k = $sIndex + 1; $k <= strlen($s); $k++) {
            $newWord = substr($s, $sIndex, $k - $sIndex);
            if (in_array($newWord, $wordSet)) {
                continue;
            }
            $symbolMap[$symbol] = $newWord;
            $wordSet[] = $newWord;
            if ($this->isMatch($s, $k, $pattern, $pIndex + 1, $symbolMap, $wordSet)) {
                return true;
            }
            unset($symbolMap[$symbol]);
            array_pop($wordSet);
        }
        return false;
    }
}
?>

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