Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

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

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

function candyCrush($board) {
    $m = count($board);
    $n = count($board[0]);
    $stable = false;

    while (!$stable) {
        $stable = true;
        $crush = array_fill(0, $m, array_fill(0, $n, false));

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n - 2; $j++) {
                $v = abs($board[$i][$j]);
                if ($v != 0 && $v == abs($board[$i][$j + 1]) && $v == abs($board[$i][$j + 2])) {
                    $stable = false;
                    $crush[$i][$j] = $crush[$i][$j + 1] = $crush[$i][$j + 2] = true;
                }
            }
        }

        for ($i = 0; $i < $m - 2; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $v = abs($board[$i][$j]);
                if ($v != 0 && $v == abs($board[$i + 1][$j]) && $v == abs($board[$i + 2][$j])) {
                    $stable = false;
                    $crush[$i][$j] = $crush[$i + 1][$j] = $crush[$i + 2][$j] = true;
                }
            }
        }

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($crush[$i][$j]) {
                    $board[$i][$j] = 0;
                }
            }
        }

        for ($j = 0; $j < $n; $j++) {
            $idx = $m - 1;
            for ($i = $m - 1; $i >= 0; $i--) {
                if ($board[$i][$j] != 0) {
                    $board[$idx][$j] = $board[$i][$j];
                    $idx--;
                }
            }
            for ($i = $idx; $i >= 0; $i--) {
                $board[$i][$j] = 0;
            }
        }
    }

    return $board;
}

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

Задача: 658. Find K Closest Elements
Сложность: easy

Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания.

Целое число a ближе к x, чем целое число b, если:

|a - x| < |b - x|, или
|a - x| == |b - x| и a < b.

Пример:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

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

1⃣Бинарный поиск:
Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска.

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

3⃣Сортировка:
Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован).

😎 Решение:

class Solution {
    function findClosestElements($arr, $k, $x) {
        $left = 0;
        $right = count($arr) - $k;

        while ($left < $right) {
            $mid = (int)(($left + $right) / 2);
            if ($x - $arr[$mid] > $arr[$mid + $k] - $x) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }

        return array_slice($arr, $left, $k);
    }
}

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

Задача: 145. Binary Tree Postorder Traversal
Сложность: easy

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

Пример:

Input: root = [1,null,2,3]
Output: [3,2,1]

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

1⃣Заполнение стека по стратегии право->узел->лево:
Инициируйте стек и добавьте в него корень дерева.
Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода.

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

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

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

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

function postorderTraversal($root) {
    $output = [];
    $stack = [];
    if ($root === null) return $output;
    array_push($stack, $root);
    while (!empty($stack)) {
        $root = array_pop($stack);
        array_push($output, $root->val);
        if ($root->left !== null) array_push($stack, $root->left);
        if ($root->right !== null) array_push($stack, $root->right);
    }
    return array_reverse($output);
}

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

Задача: 1675. Minimize Deviation in Array
Сложность: hard

Вам дан массив nums из n положительных целых чисел.
Вы можете выполнять два типа операций над любым элементом массива любое количество раз:
Если элемент четный, разделите его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].
Если элемент нечетный, умножьте его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].
Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.
Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.

Пример:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

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

1⃣Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

2⃣Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

3⃣Повторяйте шаг 2 до тех пор, пока максимальный элемент в evens не станет нечетным. Верните минимальное отклонение.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function minimumDeviation($nums) {
        $evens = new SplPriorityQueue();
        $minimum = PHP_INT_MAX;
        
        foreach ($nums as $num) {
            if ($num % 2 == 0) {
                $evens->insert($num, $num);
                $minimum = min($minimum, $num);
            } else {
                $evens->insert($num * 2, $num * 2);
                $minimum = min($minimum, $num * 2);
            }
        }
        
        $minDeviation = PHP_INT_MAX;
        
        while (!$evens->isEmpty()) {
            $currentValue = $evens->extract();
            $minDeviation = min($minDeviation, $currentValue - $minimum);
            if ($currentValue % 2 == 0) {
                $evens->insert($currentValue / 2, $currentValue / 2);
                $minimum = min($minimum, $currentValue / 2);
            } else {
                break;
            }
        }
        
        return $minDeviation;
    }
}

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

Задача: 105. Construct Binary Tree from Preorder and Inorder Traversal
Сложность: medium

Даны два массива целых чисел: preorder и inorder, где preorder — это результат преордер обхода бинарного дерева, а inorder — результат инордер обхода того же дерева. Постройте и верните бинарное дерево.

Пример:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

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

1⃣Создайте хеш-таблицу для записи соотношения значений и их индексов в массиве inorder, чтобы можно было быстро найти позицию корня.

2⃣Инициализируйте переменную целочисленного типа preorderIndex для отслеживания элемента, который будет использоваться для создания корня. Реализуйте рекурсивную функцию arrayToTree, которая принимает диапазон массива inorder и возвращает построенное бинарное дерево:
Если диапазон пуст, возвращается null;
Инициализируйте корень элементом preorder[preorderIndex], затем увеличьте preorderIndex;
Рекурсивно используйте левую и правую части массива inorder для построения левого и правого поддеревьев.

3⃣Просто вызовите функцию рекурсии с полным диапазоном массива inorder.

😎 Решение:

function buildTree($preorder, $inorder) {
    static $preorderIndex = 0;
    $inorderIndexMap = [];
    foreach ($inorder as $i => $value) {
        $inorderIndexMap[$value] = $i;
    }
    
    return arrayToTree(0, count($preorder) - 1, $preorder, $inorderIndexMap, $preorderIndex);
}

function arrayToTree($left, $right, &$preorder, &$inorderIndexMap, &$preorderIndex) {
    if ($left > $right) {
        return null;
    }
    
    $rootValue = $preorder[$preorderIndex++];
    $root = new TreeNode($rootValue);
    $root->left = arrayToTree($left, $inorderIndexMap[$rootValue] - 1, $preorder, $inorderIndexMap, $preorderIndex);
    $root->right = arrayToTree($inorderIndexMap[$rootValue] + 1, $right, $preorder, $inorderIndexMap, $preorderIndex);
    return $root;
}

class TreeNode {
    public $val;
    public $left;
    public $right;

    public function __construct($value) {
        $this->val = $value;
        $this->left = null;
        $this->right = null;
    }
}

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

Задача: 413. Arithmetic Slices
Сложность: medium

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов.

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

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

function numberOfArithmeticSlices($nums) {
    $count = 0;
    $currentLength = 0;
    for ($i = 2; $i < count($nums); $i++) {
        if ($nums[$i] - $nums[$i - 1] == $nums[$i - 1] - $nums[$i - 2]) {
            $currentLength++;
            $count += $currentLength;
        } else {
            $currentLength = 0;
        }
    }
    return $count;
}

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

Задача: 625. Minimum Factorization
Сложность: medium

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.

😎 Решение:

function smallestFactorization($num) {
    if ($num == 1) {
        return 1;
    }
    
    $factors = [];
    
    for ($i = 9; $i >= 2; $i--) {
        while ($num % $i == 0) {
            $factors[] = $i;
            $num /= $i;
        }
    }
    
    if ($num > 1) {
        return 0;
    }
    
    $result = 0;
    foreach (array_reverse($factors) as $factor) {
        $result = $result * 10 + $factor;
        if ($result > PHP_INT_MAX) {
            return 0;
        }
    }
    
    return $result;
}

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

Задача: 728. Self Dividing Numbers
Сложность: hard

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

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

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

😎 Решение:

function selfDividingNumbers($left, $right) {
    $result = [];
    for ($num = $left; $num <= $right; $num++) {
        if (isSelfDividing($num)) {
            $result[] = $num;
        }
    }
    return $result;
}

function isSelfDividing($num) {
    $n = $num;
    while ($n > 0) {
        $digit = $n % 10;
        if ($digit == 0 || $num % $digit != 0) {
            return false;
        }
        $n = (int)($n / 10);
    }
    return true;
}

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

Задача: 470. Implement Rand10() Using Rand7()
Сложность: medium

Дано API rand7(), возвращающее случайное целое число от 1 до 7.
Нужно реализовать функцию rand10(), возвращающую случайное число от 1 до 10, используя только rand7().

Пример:

Input: n = 1
Output: [2]

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

1⃣Используем формулу:
idx = (row - 1) * 7 + col — генерирует числа от 1 до 49.

2⃣Принимаем только значения 1..40, т.к. они равномерно делятся на 10.

3⃣Остальные (41..49) отбрасываем и пробуем снова — чтобы не нарушить равномерность.

😎 Решение:

class Solution {
    public function rand10() {
        do {
            $row = rand7();
            $col = rand7();
            $idx = $col + ($row - 1) * 7;
        } while ($idx > 40);
        return 1 + ($idx - 1) % 10;
    }
}

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

Задача: 1220. Count Vowels Permutation
Сложность: hard

Дано целое число n, ваша задача состоит в том, чтобы посчитать, сколько строк длины n можно сформировать по следующим правилам:
Каждый символ является строчной гласной буквой ('a', 'e', 'i', 'o', 'u')
Каждая гласная 'a' может быть только перед 'e'.
Каждая гласная 'e' может быть только перед 'a' или 'i'.
Каждая гласная 'i' не может быть перед другой 'i'.
Каждая гласная 'o' может быть только перед 'i' или 'u'.
Каждая гласная 'u' может быть только перед 'a'.
Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

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

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

2⃣Заполнение массивов в соответствии с правилами:
Проходите по длине строки от 1 до n.
Обновляйте значения массивов, следуя правилам для каждой гласной, учитывая предыдущие значения.

3⃣Суммирование и возврат результата:
Возьмите сумму последних элементов всех пяти массивов.
Верните результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
    function countVowelPermutation($n) {
        $MOD = 1000000007;
        $a = array_fill(0, $n, 0);
        $e = array_fill(0, $n, 0);
        $i = array_fill(0, $n, 0);
        $o = array_fill(0, $n, 0);
        $u = array_fill(0, $n, 0);

        $a[0] = 1;
        $e[0] = 1;
        $i[0] = 1;
        $o[0] = 1;
        $u[0] = 1;

        for ($k = 1; $k < $n; $k++) {
            $a[$k] = ($e[$k - 1] + $i[$k - 1] + $u[$k - 1]) % $MOD;
            $e[$k] = ($a[$k - 1] + $i[$k - 1]) % $MOD;
            $i[$k] = ($e[$k - 1] + $o[$k - 1]) % $MOD;
            $o[$k] = $i[$k - 1] % $MOD;
            $u[$k] = ($i[$k - 1] + $o[$k - 1]) % $MOD;
        }

        return ($a[$n - 1] + $e[$n - 1] + $i[$n - 1] + $o[$n - 1] + $u[$n - 1]) % $MOD;
    }
}

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

Задача: 685. Redundant Connection II
Сложность: hard

В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.

Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

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

Пример:

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

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

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.

😎 Решение:

class Solution {
    function findRedundantDirectedConnection($edges) {
        $N = count($edges);
        $parent = [];
        $candidates = [];
        foreach ($edges as $edge) {
            if (isset($parent[$edge[1]])) {
                $candidates[] = [$parent[$edge[1]], $edge[1]];
                $candidates[] = $edge;
            } else {
                $parent[$edge[1]] = $edge[0];
            }
        }

        $root = $this->orbit(1, $parent)->node;
        if (empty($candidates)) {
            $cycle = $this->orbit($root, $parent)->seen;
            $ans = [0, 0];
            foreach ($edges as $edge) {
                if (in_array($edge[0], $cycle) && in_array($edge[1], $cycle)) {
                    $ans = $edge;
                }
            }
            return $ans;
        }

        $children = [];
        foreach ($parent as $v => $pv) {
            if (!isset($children[$pv])) {
                $children[$pv] = [];
            }
            $children[$pv][] = $v;
        }

        $seen = array_fill(0, $N + 1, false);
        $seen[0] = true;
        $stack = [$root];
        while (!empty($stack)) {
            $node = array_pop($stack);
            if (!$seen[$node]) {
                $seen[$node] = true;
                if (isset($children[$node])) {
                    foreach ($children[$node] as $c) {
                        $stack[] = $c;
                    }
                }
            }
        }
        foreach ($seen as $b) {
            if (!$b) {
                return $candidates[0];
            }
        }
        return $candidates[1];
    }

    function orbit($node, $parent) {
        $seen = [];
        while (isset($parent[$node]) && !in_array($node, $seen)) {
            $seen[] = $node;
            $node = $parent[$node];
        }
        return (object)[
            'node' => $node,
            'seen' => $seen
        ];
    }
}

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

Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

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

function increasingBST($root) {
    $nodes = [];
    
    function inorder($node, &$nodes) {
        if ($node === null) return;
        inorder($node->left, $nodes);
        $nodes[] = $node;
        inorder($node->right, $nodes);
    }
    
    inorder($root, $nodes);
    
    for ($i = 0; $i < count($nodes) - 1; $i++) {
        $nodes[$i]->left = null;
        $nodes[$i]->right = $nodes[$i + 1];
    }
    
    $nodes[count($nodes) - 1]->left = null;
    $nodes[count($nodes) - 1]->right = null;
    return $nodes[0];
}

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

Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Отсортировать массив arr.

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

function threeSumMulti($arr, $target) {
    sort($arr);
    $MOD = 1_000_000_007;
    $count = 0;
    
    for ($i = 0; $i < count($arr); $i++) {
        $j = $i + 1;
        $k = count($arr) - 1;
        while ($j < $k) {
            $sum = $arr[$i] + $arr[$j] + $arr[$k];
            if ($sum == $target) {
                if ($arr[$j] == $arr[$k]) {
                    $count += ($k - $j + 1) * ($k - $j) / 2;
                    break;
                } else {
                    $left = 1;
                    $right = 1;
                    while ($j + 1 < $k && $arr[$j] == $arr[$j + 1]) {
                        $left++;
                        $j++;
                    }
                    while ($k - 1 > $j && $arr[$k] == $arr[$k - 1]) {
                        $right++;
                        $k--;
                    }
                    $count += $left * $right;
                    $j++;
                    $k--;
                }
            } elseif ($sum < $target) {
                $j++;
            } else {
                $k--;
            }
        }
    }
    
    return $count % $MOD;
}

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

Сложность: medium
Задача: 1428. Leftmost Column with at Least a One

Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

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

Пример:

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

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

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

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

3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1.

😎 Решение:

class Solution {
    function leftMostColumnWithOne($binaryMatrix) {
        list($rows, $cols) = $binaryMatrix->dimensions();
        $currentRow = 0;
        $currentCol = $cols - 1;
        
        while ($currentRow < $rows && $currentCol >= 0) {
            if ($binaryMatrix->get($currentRow, $currentCol) == 0) {
                $currentRow++;
            } else {
                $currentCol--;
            }
        }
        
        return ($currentCol == $cols - 1) ? -1 : $currentCol + 1;
    }
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

function crackSafe($n, $k) {
    $seen = [];
    $result = [];

    function dfs($node, $k, &$seen, &$result) {
        for ($x = 0; $x < $k; $x++) {
            $neighbor = $node . $x;
            if (!in_array($neighbor, $seen)) {
                $seen[] = $neighbor;
                dfs(substr($neighbor, 1), $k, $seen, $result);
                $result[] = $x;
            }
        }
    }

    $startNode = str_repeat("0", $n - 1);
    dfs($startNode, $k, $seen, $result);

    return $startNode . implode('', $result);
}

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

Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 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 maxAncestorDiff($root) {
        return $this->dfs($root, $root->val, $root->val);
    }
    
    private function dfs($node, $minVal, $maxVal) {
        if ($node === null) return $maxVal - $minVal;
        $minVal = min($minVal, $node->val);
        $maxVal = max($maxVal, $node->val);
        $left = $this->dfs($node->left, $minVal, $maxVal);
        $right = $this->dfs($node->right, $minVal, $maxVal);
        return max($left, $right);
    }
}

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

Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

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

1⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.

2⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

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

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

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

class Solution {
    function zigzagLevelOrder($root) {
        $result = [];
        if ($root === null) {
            return $result;
        }

        $nodeQueue = new SplQueue();
        $nodeQueue->enqueue($root);
        $nodeQueue->enqueue(null);
        $isOrderLeft = true;
        $levelList = [];

        while (!$nodeQueue->isEmpty()) {
            $currentNode = $nodeQueue->dequeue();

            if ($currentNode !== null) {
                if ($isOrderLeft) {
                    $levelList[] = $currentNode->val;
                } else {
                    array_unshift($levelList, $currentNode->val);
                }

                if ($currentNode->left !== null) {
                    $nodeQueue->enqueue($currentNode->left);
                }
                if ($currentNode->right !== null) {
                    $nodeQueue->enqueue($currentNode->right);
                }
            } else {
                $result[] = $levelList;
                $levelList = [];
                if (!$nodeQueue->isEmpty()) {
                    $nodeQueue->enqueue(null);
                }
                $isOrderLeft = !$isOrderLeft;
            }
        }

        return $result;
    }
}

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

Задача: 968. Binary Tree Cameras
Сложность: hard

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

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

Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

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

1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.

2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.

3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.

😎 Решение:

class Solution {
    function minCameraCover($root) {
        $ans = $this->solve($root);
        return min($ans[1], $ans[2]);
    }

    private function solve($node) {
        if ($node == null) {
            return [0, 0, 99999];
        }

        $L = $this->solve($node->left);
        $R = $this->solve($node->right);
        $mL12 = min($L[1], $L[2]);
        $mR12 = min($R[1], $R[2]);

        $d0 = $L[1] + $R[1];
        $d1 = min($L[2] + $mR12, $R[2] + $mL12);
        $d2 = 1 + min($L[0], $mL12) + min($R[0], $mR12);
        return [$d0, $d1, $d2];
    }
}

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

Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: Hard

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:
[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums, который может содержать дубликаты, верните минимальный элемент этого массива.
Необходимо максимально уменьшить количество операций.

Пример:

Input: nums = [1,3,5]
Output: 1

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

1⃣Сравнение с правой границей:
В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2⃣Обновление указателей:
Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.
Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.
Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.

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

😎 Решение:

class Solution {
    function findMin($nums) {
        $low = 0;
        $high = count($nums) - 1;
        
        while ($low < $high) {
            $pivot = $low + intdiv($high - $low, 2);
            if ($nums[$pivot] < $nums[$high]) {
                $high = $pivot;
            } else if ($nums[$pivot] > $nums[$high]) {
                $low = $pivot + 1;
            } else {
                $high -= 1;
            }
        }
        return $nums[$low];
    }
}

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

Задача: 498. Diagonal Traverse
Сложность: medium

Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.

Пример:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

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

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

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

3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎 Решение:

class Solution {
    function findDiagonalOrder($mat) {
        if (empty($mat) || empty($mat[0])) return [];
        $N = count($mat);
        $M = count($mat[0]);
        $result = [];
        
        for ($d = 0; $d < $N + $M - 1; $d++) {
            $intermediate = [];
            $r = $d < $M ? 0 : $d - $M + 1;
            $c = $d < $M ? $d : $M - 1;
            
            while ($r < $N && $c >= 0) {
                $intermediate[] = $mat[$r][$c];
                $r++;
                $c--;
            }
            
            if ($d % 2 == 0) {
                $intermediate = array_reverse($intermediate);
            }
            $result = array_merge($result, $intermediate);
        }
        
        return $result;
    }
}

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