Задача: 863. All Nodes Distance K in Binary Tree
Сложность: medium

Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла.

Ответ можно вернуть в любом порядке.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

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

1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя).

2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь.

3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS.

😎 Решение:

class Solution {
    function distanceK($root, $target, $k) {
        $this->addParent($root, null);
        
        $answer = [];
        $visited = new SplObjectStorage();
        
        $this->dfs($target, $k, $visited, $answer);
        return $answer;
    }
    
    private function addParent($cur, $parent) {
        if ($cur) {
            $cur->parent = $parent;
            $this->addParent($cur->left, $cur);
            $this->addParent($cur->right, $cur);
        }
    }
    
    private function dfs($cur, $distance, $visited, &$answer) {
        if (!$cur || $visited->contains($cur)) return;
        $visited->attach($cur);
        if ($distance == 0) {
            $answer[] = $cur->val;
            return;
        }
        $this->dfs($cur->parent, $distance - 1, $visited, $answer);
        $this->dfs($cur->left, $distance - 1, $visited, $answer);
        $this->dfs($cur->right, $distance - 1, $visited, $answer);
    }
}

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

Задача: 1469. Find All The Lonely Nodes
Сложность: easy

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

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

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

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 {
    function DFS($root, $isLonely, &$ans) {
        if ($root === null) {
            return;
        }
        
        if ($isLonely) {
            $ans[] = $root->val;
        }
        
        $this->DFS($root->left, $root->right === null, $ans);
        $this->DFS($root->right, $root->left === null, $ans);
    }
    
    function getLonelyNodes($root) {
        $ans = [];
        $this->DFS($root, false, $ans);
        return $ans;
    }
}

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

Задача: 233. Number of Digit One
Сложность: hard

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

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

function countDigitOne($n) {
    $countr = 0;
    for ($i = 1; $i <= $n; $i *= 10) {
        $divider = $i * 10;
        $countr += intval($n / $divider) * $i + min(max($n % $divider - $i + 1, 0), $i);
    }
    return $countr;
}

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

Задача: 137. Single Number II
Сложность: medium

Дан массив целых чисел nums, в котором каждый элемент встречается три раза, кроме одного, который встречается ровно один раз. Найдите этот единственный элемент и верните его.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

Input: nums = [2,2,3,2]
Output: 3

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

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

2⃣Итерация с проверкой:
Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива.
Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла.

3⃣Возврат уникального элемента:
Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе.
Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше.

😎 Решение:

function singleNumber($nums) {
    sort($nums);
    $len = count($nums);
    for ($i = 0; $i < $len - 1; $i += 3) {
        if ($nums[$i] !== $nums[$i + 1]) {
            return $nums[$i];
        }
    }
    return $nums[$len - 1];
}

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

Задача: 282. Expression Add Operators
Сложность: hard

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.
Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

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

2⃣Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.

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

😎 Решение:

class Solution {
    private $answer;
    private $digits;
    private $target;

    private function recurse($index, $previousOperand, $currentOperand, $value, &$ops) {
        if ($index == strlen($this->digits)) {
            if ($value == $this->target && $currentOperand == 0) {
                $this->answer[] = implode("", $ops);
            }
            return;
        }

        $currentOperand = $currentOperand * 10 + intval($this->digits[$index]);
        $currentValRep = strval($currentOperand);

        if ($currentOperand > 0) {
            $this->recurse($index + 1, $previousOperand, $currentOperand, $value, $ops);
        }

        $ops[] = "+";
        $ops[] = $currentValRep;
        $this->recurse($index + 1, $currentOperand, 0, $value + $currentOperand, $ops);
        array_pop($ops);
        array_pop($ops);

        if (count($ops) > 0) {
            $ops[] = "-";
            $ops[] = $currentValRep;
            $this->recurse($index + 1, -$currentOperand, 0, $value - $currentOperand, $ops);
            array_pop($ops);
            array_pop($ops);

            $ops[] = "*";
            $ops[] = $currentValRep;
            $this->recurse($index + 1, $currentOperand * $previousOperand, 0, $value - $previousOperand + ($currentOperand * $previousOperand), $ops);
            array_pop($ops);
            array_pop($ops);
        }
    }

    public function addOperators($num, $target) {
        if (strlen($num) == 0) {
            return [];
        }

        $this->target = $target;
        $this->digits = $num;
        $this->answer = [];
        $ops = [];
        $this->recurse(0, 0, 0, 0, $ops);
        return $this->answer;
    }
}

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

Задача: 645. Set Mismatch
Сложность: easy

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

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

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

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

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

function findErrorNums($nums) {
    $n = count($nums);
    $numSet = [];
    $duplicate = -1;
    foreach ($nums as $num) {
        if (in_array($num, $numSet)) {
            $duplicate = $num;
        }
        $numSet[] = $num;
    }
    $missing = ($n * ($n + 1)) / 2 - array_sum(array_unique($numSet));
    return [$duplicate, $missing];
}

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

function checkInclusion($s1, $s2) {
    $s1Len = strlen($s1);
    $s2Len = strlen($s2);
    if ($s1Len > $s2Len) return false;

    $s1Count = array_fill(0, 26, 0);
    $s2Count = array_fill(0, 26, 0);

    for ($i = 0; $i < $s1Len; $i++) {
        $s1Count[ord($s1[$i]) - ord('a')]++;
        $s2Count[ord($s2[$i]) - ord('a')]++;
    }

    for ($i = 0; $i < $s2Len - $s1Len; $i++) {
        if ($s1Count == $s2Count) return true;
        $s2Count[ord($s2[$i]) - ord('a')]--;
        $s2Count[ord($s2[$i + $s1Len]) - ord('a')]++;
    }

    return $s1Count == $s2Count;
}

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

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число" от 1 до n.
Есть предопределённая функция guess(int num), которая возвращает:
-1 — если num больше загаданного числа
1 — если num меньше загаданного числа
0 — если num совпадает с загаданным числом

Пример:

Input: n = 10, pick = 6
Output: 6

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

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

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

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

😎 Решение:

class Solution extends GuessGame {
    function guessNumber($n) {
        $low = 1;
        $high = $n;
        while ($low <= $high) {
            $mid = $low + intdiv($high - $low, 2);
            $res = guess($mid);
            if ($res == 0)
                return $mid;
            else if ($res < 0)
                $high = $mid - 1;
            else
                $low = $mid + 1;
        }
        return -1;
    }
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

function deleteTreeNodes($nodes, $parent, $value) {
    $tree = [];
    for ($i = 0; $i < $nodes; $i++) {
        if (!isset($tree[$parent[$i]])) $tree[$parent[$i]] = [];
        $tree[$parent[$i]][] = $i;
    }

    function dfs($node, &$tree, &$value) {
        $totalSum = $value[$node];
        $totalCount = 1;
        if (isset($tree[$node])) {
            foreach ($tree[$node] as $child) {
                list($childSum, $childCount) = dfs($child, $tree, $value);
                $totalSum += $childSum;
                $totalCount += $childCount;
            }
        }
        return $totalSum == 0 ? [0, 0] : [$totalSum, $totalCount];
    }

    return dfs(0, $tree, $value)[1];
}

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

Задача: 538. Convert BST to Greater 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⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево.

2⃣Посещаем текущий узел, обновляем его значение и общую сумму.

3⃣Рекурсивно обрабатываем левое поддерево.

😎 Решение:

class Solution {
    private $sum = 0;

    public function convertBST($root) {
        if ($root !== null) {
            $this->convertBST($root->right);
            $this->sum += $root->val;
            $root->val = $this->sum;
            $this->convertBST($root->left);
        }
        return $root;
    }
}

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

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

Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.

Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

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

1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.

2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.

3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива.

😎 Решение:

class Solution {
    function rotate(&$nums, $k) {
        $n = count($nums);
        $a = array_fill(0, $n, 0);
        for ($i = 0; $i < $n; $i++) {
            $a[($i + $k) % $n] = $nums[$i];
        }
        for ($i = 0; $i < $n; $i++) {
            $nums[$i] = $a[$i];
        }
    }
}

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

Задача: 1044. Longest Duplicate Substring
Сложность: hard

Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Пример:

Input: s = "banana"
Output: "ana"

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

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

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

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

function longestDupSubstring($s) {
    function search($s, $length) {
        $seen = [];
        for ($i = 0; $i <= strlen($s) - $length; $i++) {
            $sub = substr($s, $i, $length);
            if (isset($seen[$sub])) {
                return $sub;
            }
            $seen[$sub] = true;
        }
        return "";
    }

    $left = 1;
    $right = strlen($s);
    $result = "";
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        $dup = search($s, $mid);
        if ($dup !== "") {
            $result = $dup;
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $result;
}

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

Задача: 358. Rearrange String k Distance Apart
Сложность: hard

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

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

class Solution {
    function rearrangeString($s, $k) {
        $freqs = [];
        $maxFreq = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (!isset($freqs[$char])) {
                $freqs[$char] = 0;
            }
            $freqs[$char]++;
            $maxFreq = max($maxFreq, $freqs[$char]);
        }

        $mostChars = [];
        $secondChars = [];

        foreach ($freqs as $char => $freq) {
            if ($freq == $maxFreq) {
                $mostChars[] = $char;
            } else if ($freq == $maxFreq - 1) {
                $secondChars[] = $char;
            }
        }

        $segments = array_fill(0, $maxFreq, "");

        for ($i = 0; $i < $maxFreq; $i++) {
            foreach ($mostChars as $char) {
                $segments[$i] .= $char;
            }
            if ($i < $maxFreq - 1) {
                foreach ($secondChars as $char) {
                    $segments[$i] .= $char;
                }
            }
        }

        $segmentId = 0;

        foreach ($freqs as $char => $freq) {
            if (in_array($char, $mostChars) || in_array($char, $secondChars)) {
                continue;
            }

            for ($j = 0; $j < $freq; $j++) {
                $segments[$segmentId] .= $char;
                $segmentId = ($segmentId + 1) % ($maxFreq - 1);
            }
        }

        for ($i = 0; $i < $maxFreq - 1; $i++) {
            if (strlen($segments[$i]) < $k) {
                return "";
            }
        }

        return implode("", $segments);
    }
}

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

Задача: 908. Smallest Range I
Сложность: easy

Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.

Пример:

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

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

1⃣Найти минимальное и максимальное значения массива nums.

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

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

😎 Решение:

function smallestRangeI($nums, $k) {
    $minVal = min($nums);
    $maxVal = max($nums);
    return max(0, ($maxVal - $k) - ($minVal + $k));
}

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

Задача: 366. Find Leaves of Binary Tree
Сложность: medium

Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

class Solution {
    private $pairs = [];

    private function getHeight($node) {
        if ($node === null) return -1;
        $leftHeight = $this->getHeight($node->left);
        $rightHeight = $this->getHeight($node->right);
        $currHeight = max($leftHeight, $rightHeight) + 1;
        $this->pairs[] = [$currHeight, $node->val];
        return $currHeight;
    }

    public function findLeaves($root) {
        $this->getHeight($root);
        usort($this->pairs, function($a, $b) {
            return $a[0] <=> $b[0];
        });
        $solution = [];
        $currentHeight = -1;
        foreach ($this->pairs as $pair) {
            if ($pair[0] !== $currentHeight) {
                $solution[] = [];
                $currentHeight = $pair[0];
            }
            $solution[count($solution) - 1][] = $pair[1];
        }
        return $solution;
    }
}

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

Задача: 148. Sort List
Сложность: Medium

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

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

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

2⃣Сортировка подсписков и их объединение (Фаза слияния):
Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3⃣Иллюстрация процесса сортировки:
Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

class ListNode {
    public $val;
    public $next;

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

class Solution {
    public function sortList($head) {
        if ($head === null || $head->next === null) {
            return $head;
        }
        $mid = $this->getMid($head);
        $left = $this->sortList($head);
        $right = $this->sortList($mid);
        return $this->merge($left, $right);
    }

    private function merge($list1, $list2) {
        $dummyHead = new ListNode();
        $tail = $dummyHead;
        while ($list1 !== null && $list2 !== null) {
            if ($list1->val < $list2->val) {
                $tail->next = $list1;
                $list1 = $list1->next;
            } else {
                $tail->next = $list2;
                $list2 = $list2->next;
            }
            $tail = $tail->next;
        }
        $tail->next = $list1 ?? $list2;
        return $dummyHead->next;
    }

    private function getMid($head) {
        $midPrev = null;
        $slow = $head;
        $fast = $head;
        while ($fast !== null && $fast->next !== null) {
            $midPrev = ($midPrev === null) ? $slow : $midPrev->next;
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        $mid = $midPrev->next;
        $midPrev->next = null;
        return $mid;
    }
}

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

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

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

Задача: 487. Max Consecutive Ones II
Сложность: medium

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

Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

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

1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей.

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

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

😎 Решение:

class Solution {
    function findMaxConsecutiveOnes($nums) {
        $longestSequence = 0;
        for ($left = 0; $left < count($nums); $left++) {
            $numZeroes = 0;
            for ($right = $left; $right < count($nums); $right++) {
                if ($nums[$right] == 0) {
                    $numZeroes++;
                }
                if ($numZeroes <= 1) {
                    $longestSequence = max($longestSequence, $right - $left + 1);
                }
            }
        }
        return $longestSequence;
    }
}

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

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

Дан список слов, и нам нужно реализовать проверку орфографии, которая преобразует слово запроса в правильное слово.

Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания:
Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов.
Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow"

Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов.
Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения)
Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения)

Кроме того, проверка орфографии работает по следующим правилам приоритета:
Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово.
Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов.
Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов.
Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку.
Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i].

Пример:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

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

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

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

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

😎 Решение:

class Solution {
    private $wordsPerfect;
    private $wordsCap;
    private $wordsVow;

    /**
     * @param String[] $wordlist
     * @param String[] $queries
     * @return String[]
     */
    function spellchecker($wordlist, $queries) {
        $this->wordsPerfect = array_flip($wordlist);
        $this->wordsCap = [];
        $this->wordsVow = [];

        foreach ($wordlist as $word) {
            $wordlow = strtolower($word);
            if (!isset($this->wordsCap[$wordlow])) {
                $this->wordsCap[$wordlow] = $word;
            }

            $wordlowDV = $this->devowel($wordlow);
            if (!isset($this->wordsVow[$wordlowDV])) {
                $this->wordsVow[$wordlowDV] = $word;
            }
        }

        $result = [];
        foreach ($queries as $query) {
            $result[] = $this->solve($query);
        }
        return $result;
    }

    private function solve($query) {
        if (isset($this->wordsPerfect[$query])) {
            return $query;
        }

        $queryL = strtolower($query);
        if (isset($this->wordsCap[$queryL])) {
            return $this->wordsCap[$queryL];
        }

        $queryLV = $this->devowel($queryL);
        if (isset($this->wordsVow[$queryLV])) {
            return $this->wordsVow[$queryLV];
        }

        return "";
    }

    private function devowel($word) {
        return preg_replace('/[aeiou]/', '*', $word);
    }
}

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

Задача: 731. My Calendar II
Сложность: medium

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

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

2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями.

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

😎 Решение:

class MyCalendarTwo {
    private $events;
    private $overlaps;

    function __construct() {
        $this->events = [];
        $this->overlaps = [];
    }

    function book($start, $end) {
        foreach ($this->overlaps as $overlap) {
            if ($start < $overlap[1] && $end > $overlap[0]) {
                return false;
            }
        }
        foreach ($this->events as $event) {
            if ($start < $event[1] && $end > $event[0]) {
                $this->overlaps[] = [max($start, $event[0]), min($end, $event[1])];
            }
        }
        $this->events[] = [$start, $end];
        return true;
    }
}

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