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

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

Задача: 1436. Destination City
Сложность: easy

Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.

Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.

Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

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

1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.

2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).

3⃣Верните город, который не имеет исходящих путей.

😎 Решение:

class Solution {
    function destCity($paths) {
        foreach ($paths as $path) {
            $candidate = $path[1];
            $good = true;
            foreach ($paths as $p) {
                if ($p[0] === $candidate) {
                    $good = false;
                    break;
                }
            }
            if ($good) {
                return $candidate;
            }
        }
        return "";
    }
}

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

Задача: 234. Palindrome Linked List
Сложность: easy

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

Пример:

Input: head = [1,2,2,1]
Output: true

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

1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null.

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

3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата.

😎 Решение:

class Solution {
    function isPalindrome($head) {
        $vals = [];
        $currentNode = $head;

        while ($currentNode !== null) {
            $vals[] = $currentNode->val;
            $currentNode = $currentNode->next;
        }

        $front = 0;
        $back = count($vals) - 1;
        while ($front < $back) {
            if ($vals[$front] != $vals[$back]) {
                return false;
            }
            $front++;
            $back--;
        }
        return true;
    }
}

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

Задача: 287. Find the Duplicate Number
Сложность: medium

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

Пример:

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

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

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

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

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

class Solution {
    function findDuplicate($nums) {
        $duplicate = -1;
        for ($i = 0; $i < count($nums); $i++) {
            $cur = abs($nums[$i]);
            if ($nums[$cur] < 0) {
                $duplicate = $cur;
                break;
            }
            $nums[$cur] *= -1;
        }
        for ($i = 0; $i < count($nums); $i++) {
            $nums[$i] = abs($nums[$i]);
        }
        return $duplicate;
    }
}

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

Задача: 1023. Camelcase Matching
Сложность: medium

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

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

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

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

3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.

😎 Решение:

class Solution {
    function camelMatch($queries, $pattern) {
        function matches($query, $pattern) {
            $i = 0;
            $j = 0;
            
            while ($i < strlen($query)) {
                if ($j < strlen($pattern) && $query[$i] == $pattern[$j]) {
                    $j++;
                } else if (ctype_upper($query[$i])) {
                    return false;
                }
                $i++;
            }
            
            return $j == strlen($pattern);
        }
        
        $answer = [];
        foreach ($queries as $query) {
            $answer[] = matches($query, $pattern);
        }
        
        return $answer;
    }
}

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

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

Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

class Solution {
    private $reversiblePairs = [
        ['0', '0'], ['1', '1'],
        ['6', '9'], ['8', '8'], ['9', '6']
    ];

    private function generateStroboNumbers($n, $finalLength) {
        if ($n == 0) {
            return [""];
        }

        if ($n == 1) {
            return ["0", "1", "8"];
        }

        $prevStroboNums = $this->generateStroboNumbers($n - 2, $finalLength);
        $currStroboNums = [];

        foreach ($prevStroboNums as $prevStroboNum) {
            foreach ($this->reversiblePairs as $pair) {
                if ($pair[0] != '0' || $n != $finalLength) {
                    $currStroboNums[] = $pair[0] . $prevStroboNum . $pair[1];
                }
            }
        }

        return $currStroboNums;
    }

    public function findStrobogrammatic($n) {
        return $this->generateStroboNumbers($n, $n);
    }
}

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

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

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution {
    function validSubarrays($nums) {
        $ans = 0;
        $st = [];
        
        for ($i = 0; $i < count($nums); $i++) {
            while (!empty($st) && $nums[$i] < $nums[end($st)]) {
                $ans += ($i - array_pop($st));
            }
            $st[] = $i;
        }
        
        while (!empty($st)) {
            $ans += (count($nums) - array_pop($st));
        }
        
        return $ans;
    }
}

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