Задача: 301. Remove Invalid Parentheses
Сложность: hard

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

Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

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

1⃣Инициализация:
Инициализируйте массив, который будет хранить все допустимые выражения.
Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо.
Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно.

2⃣Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.

3⃣Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений.

😎 Решение:

class Solution {
    private $validExpressions;
    private $minimumRemoved;

    function __construct() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function reset() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function recurse($s, $index, $leftCount, $rightCount, $expression, $removedCount) {
        if ($index === strlen($s)) {
            if ($leftCount === $rightCount) {
                if ($removedCount <= $this->minimumRemoved) {
                    $possibleAnswer = implode('', $expression);
                    if ($removedCount < $this->minimumRemoved) {
                        $this->validExpressions = [];
                        $this->minimumRemoved = $removedCount;
                    }
                    $this->validExpressions[$possibleAnswer] = true;
                }
            }
            return;
        }

        $currentCharacter = $s[$index];
        $length = count($expression);

        if ($currentCharacter !== '(' && $currentCharacter !== ')') {
            array_push($expression, $currentCharacter);
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount);
            array_pop($expression);
        } else {
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount + 1);
            array_push($expression, $currentCharacter);

            if ($currentCharacter === '(') {
                $this->recurse($s, $index + 1, $leftCount + 1, $rightCount, $expression, $removedCount);
            } else if ($rightCount < $leftCount) {
                $this->recurse($s, $index + 1, $leftCount, $rightCount + 1, $expression, $removedCount);
            }

            array_pop($expression);
        }
    }

    function removeInvalidParentheses($s) {
        $this->reset();
        $this->recurse($s, 0, 0, 0, [], 0);
        return array_keys($this->validExpressions);
    }
}

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

Задача: 725. Split Linked List in Parts
Сложность: medium

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

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

1⃣Определите общую длину связного списка.

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

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

😎 Решение:

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

function splitListToParts($root, $k) {
    $length = 0;
    $node = $root;
    while ($node != null) {
        $length++;
        $node = $node->next;
    }

    $partLength = intdiv($length, $k);
    $extraParts = $length % $k;

    $parts = array_fill(0, $k, null);
    $node = $root;
    for ($i = 0; $i < $k; $i++) {
        $partHead = $node;
        $partSize = $partLength + ($i < $extraParts ? 1 : 0);
        for ($j = 0; $j < $partSize - 1; $j++) {
            if ($node != null) {
                $node = $node->next;
            }
        }
        if ($node != null) {
            $nextPart = $node->next;
            $node->next = null;
            $node = $nextPart;
        }
        $parts[$i] = $partHead;
    }

    return $parts;
}

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.
Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.
Реализуйте класс MedianFinder:
MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

class MedianFinder {
    private $numbers;

    public function __construct() {
        $this->numbers = [];
    }

    public function addNum($num) {
        $this->numbers[] = $num;
    }

    public function findMedian() {
        sort($this->numbers);
        $n = count($this->numbers);
        if ($n % 2 == 0) {
            return ($this->numbers[$n / 2 - 1] + $this->numbers[$n / 2]) / 2.0;
        } else {
            return $this->numbers[$n / 2];
        }
    }
}
?>

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

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

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

function longestSubstring($s, $k) {
    if (strlen($s) == 0 || $k > strlen($s)) {
        return 0;
    }
    $result = 0;

    for ($start = 0; $start < strlen($s); $start++) {
        $countMap = array_fill(0, 26, 0);
        for ($end = $start; $end < strlen($s); $end++) {
            $countMap[ord($s[$end]) - ord('a')]++;
            if (isValid($countMap, $k)) {
                $result = max($result, $end - $start + 1);
            }
        }
    }
    return $result;
}

function isValid($countMap, $k) {
    $countLetters = 0;
    $countAtLeastK = 0;
    foreach ($countMap as $count) {
        if ($count > 0) $countLetters++;
        if ($count >= $k) $countAtLeastK++;
    }
    return $countLetters == $countAtLeastK;
}

echo longestSubstring("aaabb", 3); // Output: 3
echo "\n";
echo longestSubstring("ababbc", 2); // Output: 5

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

Задача: 74. Search a 2D Matrix
Сложность: medium

Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами:

Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.

Вы должны написать решение с временной сложностью O(log(m * n)).

Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

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

1⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1.

2⃣Пока left <= right:
Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2.

3⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части.
Сравните pivot_element и target, чтобы определить, в какой части нужно искать target.

😎 Решение:

function searchMatrix($matrix, $target) {
    $m = count($matrix);
    if ($m == 0) return false;
    $n = count($matrix[0]);
    $left = 0;
    $right = $m * $n - 1;

    while ($left <= $right) {
        $pivotIdx = intdiv($left + $right, 2);
        $pivotElement = $matrix[intdiv($pivotIdx, $n)][$pivotIdx % $n];
        if ($target == $pivotElement) {
            return true;
        } else {
            if ($target < $pivotElement) {
                $right = $pivotIdx - 1;
            } else {
                $left = $pivotIdx + 1;
            }
        }
    }
    return false;
}

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

Задача: 766. Toeplitz Matrix
Сложность: easy

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.
Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

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

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

class Solution {
    function isToeplitzMatrix($matrix) {
        $groups = [];
        for ($r = 0; $r < count($matrix); ++$r) {
            for ($c = 0; $c < count($matrix[0]); ++$c) {
                if (!array_key_exists($r - $c, $groups))
                    $groups[$r - $c] = $matrix[$r][$c];
                else if ($groups[$r - $c] != $matrix[$r][$c])
                    return false;
            }
        }
        return true;
    }
}

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

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

😎 Решение:

function isRobotBounded($instructions) {
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $x = 0;
    $y = 0;
    $direction = 0;
    
    for ($i = 0; $i < strlen($instructions); $i++) {
        $instruction = $instructions[$i];
        if ($instruction == 'G') {
            $x += $directions[$direction][0];
            $y += $directions[$direction][1];
        } elseif ($instruction == 'L') {
            $direction = ($direction + 3) % 4;
        } elseif ($instruction == 'R') {
            $direction = ($direction + 1) % 4;
        }
    }
    
    return ($x == 0 && $y == 0) || $direction != 0;
}

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

Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium

Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.

Пример:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

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

2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:

Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).
Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.

3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.

😎 Решение:

class Solution {
    function minFlips($a, $b, $c) {
        $answer = 0;
        while ($a != 0 || $b != 0 || $c != 0) {
            if (($c & 1) == 1) {
                if (($a & 1) == 0 && ($b & 1) == 0) {
                    $answer++;
                }
            } else {
                $answer += ($a & 1) + ($b & 1);
            }
            $a >>= 1;
            $b >>= 1;
            $c >>= 1;
        }
        return $answer;
    }
}

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

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

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