Задача: 166. Fraction to Recurring Decimal
Сложность: medium

Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

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

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

3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

class Solution {
    function fractionToDecimal($numerator, $denominator) {
        if ($numerator == 0) {
            return "0";
        }

        $fraction = "";
        if (($numerator < 0) xor ($denominator < 0)) {
            $fraction .= "-";
        }

        $dividend = abs($numerator);
        $divisor = abs($denominator);

        $fraction .= intval($dividend / $divisor);
        $remainder = $dividend % $divisor;
        if ($remainder == 0) {
            return $fraction;
        }

        $fraction .= ".";
        $lookup = [];
        while ($remainder != 0) {
            if (isset($lookup[$remainder])) {
                $pos = $lookup[$remainder];
                $fraction = substr($fraction, 0, $pos) . "(" . substr($fraction, $pos) . ")";
                break;
            }
            $lookup[$remainder] = strlen($fraction);
            $remainder *= 10;
            $fraction .= intval($remainder / $divisor);
            $remainder %= $divisor;
        }

        return $fraction;
    }
}

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

Задача: 298. Binary Tree Longest Consecutive Sequence
Сложность: medium

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

Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

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

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

2⃣Сравнение текущего узла с родительским узлом:
Для каждого узла сравните его значение со значением родительского узла.
Если значение текущего узла на единицу больше значения родительского узла, увеличьте length.
Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1.

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

😎 Решение:

class Solution {
    private $maxLength = 0;

    public function longestConsecutive($root) {
        $this->dfs($root, null, 0);
        return $this->maxLength;
    }

    private function dfs($node, $parent, $length) {
        if ($node === null) return;
        if ($parent !== null && $node->val === $parent->val + 1) {
            $length++;
        } else {
            $length = 1;
        }
        $this->maxLength = max($this->maxLength, $length);
        $this->dfs($node->left, $node, $length);
        $this->dfs($node->right, $node, $length);
    }
}
?>

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

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

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

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

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

3⃣Вернуть минимальное значение в последней строке dp массива.

😎 Решение:

function minFallingPathSum($matrix) {
    $n = count($matrix);
    $dp = $matrix[0];
    
    for ($i = 1; $i < $n; $i++) {
        $newDp = array_fill(0, $n, 0);
        for ($j = 0; $j < $n; $j++) {
            $newDp[$j] = $matrix[$i][$j] + min($dp[$j], $j > 0 ? $dp[$j - 1] : PHP_INT_MAX, $j < $n - 1 ? $dp[$j + 1] : PHP_INT_MAX);
        }
        $dp = $newDp;
    }
    
    return min($dp);
}

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

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Сложность: hard

Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу.

Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно.

Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1.
Нулевая матрица - это матрица, в которой все ячейки равны 0.

Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

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

1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой.

2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed:
Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1.
Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке.

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

😎 Решение:

class Solution {
    private function better($x, $y) {
        return $x < 0 || ($y >= 0 && $y < $x) ? $y : $x;
    }

    private function dfs($mat, &$operations) {
        if (count($operations) == count($mat[0])) {
            $changed = array_fill(0, count($mat[0]), 0);
            $lastState = $operations;
            $maybe = 0;
            foreach ($mat as $row) {
                $state = $changed;
                foreach ($row as $j => $cell) {
                    $state[$j] ^= $cell;
                    if ($lastState[$j]) {
                        $state[$j] ^= 1;
                        if ($j > 0) {
                            $state[$j - 1] ^= 1;
                        }
                        if ($j + 1 < count($row)) {
                            $state[$j + 1] ^= 1;
                        }
                        $maybe++;
                    }
                }
                $changed = $lastState;
                $lastState = $state;
            }
            foreach ($lastState as $x) {
                if ($x) {
                    return -1;
                }
            }
            return $maybe;
        }
        $operations[] = 0;
        $maybe1 = $this->dfs($mat, $operations);
        $operations[count($operations) - 1] = 1;
        $maybe2 = $this->dfs($mat, $operations);
        array_pop($operations);
        return $this->better($maybe1, $maybe2);
    }

    public function minFlips($mat) {
        $operations = [];
        return $this->dfs($mat, $operations);
    }
}

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

Задача: 1021. Remove Outermost Parentheses
Сложность: easy

Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.

Пример:

Input: s = "(()())(())"
Output: "()()()"

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

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

2⃣Обработка строки:
Итерируйте по каждому символу строки.
Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат.
Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат.

3⃣Возврат результата:
Верните результат, содержащий строку без крайних скобок из каждой примитивной строки.

😎 Решение:

class Solution {
    function removeOuterParentheses($s) {
        $result = '';
        $level = 0;
        
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] == '(') {
                if ($level > 0) {
                    $result .= $s[$i];
                }
                $level++;
            } else {
                $level--;
                if ($level > 0) {
                    $result .= $s[$i];
                }
            }
        }
        
        return $result;
    }
}

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

Задача: 646. Maximum Length of Pair Chain
Сложность: medium

Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример:

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

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

1⃣Отсортируйте пары по второму элементу каждой пары (righti).

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

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

😎 Решение:

function findLongestChain($pairs) {
    usort($pairs, function($a, $b) {
        return $a[1] - $b[1];
    });
    $currentEnd = -PHP_INT_MAX;
    $count = 0;
    foreach ($pairs as $pair) {
        if ($currentEnd < $pair[0]) {
            $currentEnd = $pair[1];
            $count++;
        }
    }
    return $count;
}

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

Задача: 75. Sort Colors
Сложность: medium

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

Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.

Вы должны решить эту задачу без использования функции сортировки библиотеки.

Пример:

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

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

1⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0.

2⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2.

3⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0.
Пока curr <= p2:
Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо.
Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево.
Если nums[curr] = 1: сдвинуть указатель curr вправо.

😎 Решение:

function sortColors(&$nums) {
    $p0 = 0;
    $curr = 0;
    $p2 = count($nums) - 1;
    
    while ($curr <= $p2) {
        if ($nums[$curr] === 0) {
            // Swap elements at indices curr and p0
            $temp = $nums[$curr];
            $nums[$curr] = $nums[$p0];
            $nums[$p0] = $temp;
            $curr++;
            $p0++;
        } elseif ($nums[$curr] === 2) {
            // Swap elements at indices curr and p2
            $temp = $nums[$curr];
            $nums[$curr] = $nums[$p2];
            $nums[$p2] = $temp;
            $p2--;
        } else {
            $curr++;
        }
    }
}

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

Задача: 1166. Design File System
Сложность: medium

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

Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.

Реализуйте класс FileSystem:

- bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.

Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

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

1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.

2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.

3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.

😎 Решение:

class FileSystem {

    private $paths;

    function __construct() {
        $this->paths = array();
    }

    function createPath($path, $value) {
        if (empty($path) || (strlen($path) == 1 && $path == "/") || array_key_exists($path, $this->paths)) {
            return false;
        }

        $delimIndex = strrpos($path, "/");
        $parent = substr($path, 0, $delimIndex);

        if (strlen($parent) > 1 && !array_key_exists($parent, $this->paths)) {
            return false;
        }

        $this->paths[$path] = $value;
        return true;
    }

    function get($path) {
        return array_key_exists($path, $this->paths) ? $this->paths[$path] : -1;
    }
}

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

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

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

Пример:

Input: s = "abc"
Output: 7

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

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

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

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

😎 Решение:

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

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

Задача: 751. IP to CIDR
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

function ipToInt($ip) {
    $parts = explode('.', $ip);
    return ($parts[0] << 24) + ($parts[1] << 16) + ($parts[2] << 8) + $parts[3];
}

function intToIp($num) {
    return (($num >> 24) & 255) . "." . (($num >> 16) & 255) . "." . (($num >> 8) & 255) . "." . ($num & 255);
}

function cidr($ip, $prefixLength) {
    return "$ip/$prefixLength";
}

function findCidrBlocks($startIp, $n) {
    $start = ipToInt($startIp);
    $result = [];
    
    while ($n > 0) {
        $maxSize = 1;
        while ($maxSize <= $start && $maxSize <= $n) {
            $maxSize <<= 1;
        }
        $maxSize >>= 1;
        
        while ($start % $maxSize != 0) {
            $maxSize >>= 1;
        }
        
        $result[] = cidr(intToIp($start), 32 - log($maxSize, 2) + 1);
        $start += $maxSize;
        $n -= $maxSize;
    }
    
    return $result;
}

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

Задача: 92. Reverse Linked List II
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse.
В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно.

3⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next.
Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката.
Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.
Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;

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

class Solution {
    private $left;
    private $stop = false;

    public function reverseBetween($head, $m, $n) {
        if ($head === null) {
            return null;
        }

        $this->left = $head;
        $right = $head;
        $this->stop = false;

        $this->recurseAndReverse($right, $m, $n);
        return $head;
    }

    private function recurseAndReverse($right, $m, $n) {
        if ($n == 1) {
            return;
        }

        $right = $right->next;

        if ($m > 1) {
            $this->left = $this->left->next;
        }

        $this->recurseAndReverse($right, $m - 1, $n - 1);

        if ($this->left === $right || ($right->next === $this->left)) {
            $this->stop = true;
        }

        if (!$this->stop) {
            $temp = $this->left->val;
            $this->left->val = $right->val;
            $right->val = $temp;

            $this->left = $this->left->next;
        }
    }
}

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 637. Average of Levels in Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа.

Пример:

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

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

1⃣Обход дерева
Используйте обход в ширину (BFS) для обхода каждого уровня дерева.

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

3⃣Сохранение результата
Сохраните среднее значение каждого уровня в массив и верните его.

😎 Решение:

function averageOfLevels($root) {
    $result = [];
    $queue = new SplQueue();
    $queue->enqueue($root);
    
    while (!$queue->isEmpty()) {
        $levelSum = 0;
        $levelCount = $queue->count();
        for ($i = 0; $i < $levelCount; $i++) {
            $node = $queue->dequeue();
            $levelSum += $node->val;
            if ($node->left) $queue->enqueue($node->left);
            if ($node->right) $queue->enqueue($node->right);
        }
        $result[] = $levelSum / $levelCount;
    }
    
    return $result;
}

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

Задача: 44. Wildcard Matching
Сложность: hard

Дана входная строка (s) и шаблон (p), реализуйте сопоставление с шаблоном с поддержкой символов '?' и '*' где:
'?' соответствует любому одиночному символу.
'*' соответствует любой последовательности символов (включая пустую последовательность).
Сопоставление должно покрывать всю входную строку (не частично).

Пример:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

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

1⃣Очистите входные данные, заменив несколько звездочек подряд одной звездочкой: p = remove_duplicate_stars(p).
Инициируйте хеш-карту для мемоизации dp.
Верните вспомогательную функцию с очищенным входом: helper(s, p).

2⃣Функция helper(s, p):
Если пара (s, p) уже известна и сохранена в dp, верните значение.
Если строки равны (p == s) или шаблон соответствует любой строке (p == '*'), добавьте dp[(s, p)] = True.
В противном случае, если p пусто или s пусто, добавьте dp[(s, p)] = False.
Если текущие символы совпадают (p[0] == s[0] или p[0] == '?'), то сравните следующие и добавьте dp[(s, p)] = helper(s[1:], p[1:]).

3⃣Если текущий символ шаблона - звездочка (p[0] == '*'), то возможны две ситуации: звездочка не соответствует никаким символам, и звездочка соответствует одному или нескольким символам: dp[(s, p)] = helper(s, p[1:]) или helper(s[1:], p).
Если p[0] != s[0], тогда добавьте dp[(s, p)] = False.
Когда значение вычислено, верните его: dp[(s, p)].

😎 Решение:

function isMatch($s, $p) {
    $dp = [];

    function removeDuplicateStars($p) {
        $newString = "";
        for ($i = 0; $i < strlen($p); $i++) {
            if ($newString === "" || $p[$i] !== "*") {
                $newString .= $p[$i];
            } elseif ($newString[strlen($newString) - 1] !== "*") {
                $newString .= $p[$i];
            }
        }
        return $newString;
    }

    function helper($si, $pi, $s, $p, &$dp) {
        $key = $si . "," . $pi;
        if (array_key_exists($key, $dp)) {
            return $dp[$key];
        }

        if ($pi == strlen($p)) {
            $dp[$key] = $si == strlen($s);
        } elseif ($si == strlen($s)) {
            $dp[$key] = $pi + 1 == strlen($p) && $p[$pi] == "*";
        } elseif ($p[$pi] == $s[$si] || $p[$pi] == "?") {
            $dp[$key] = helper($si + 1, $pi + 1, $s, $p, $dp);
        } elseif ($p[$pi] == "*") {
            $dp[$key] = helper($si, $pi + 1, $s, $p, $dp) || helper($si + 1, $pi, $s, $p, $dp);
        } else {
            $dp[$key] = false;
        }
        return $dp[$key];
    }

    $p = removeDuplicateStars($p);
    return helper(0, 0, $s, $p, $dp);
}

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

Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: medium

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

Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).

Гарантируется, что решение существует.

Пример:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

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

1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement.

2⃣Итерация по всем делителям от 1 до maxElement:
Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог.
Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums.

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

😎 Решение:

class Solution {
    function smallestDivisor($nums, $threshold) {
        $maxElement = max($nums);
        
        for ($divisor = 1; $divisor <= $maxElement; $divisor++) {
            $sumOfDivisionResults = 0;
            $thresholdExceeded = true;
            
            foreach ($nums as $num) {
                $sumOfDivisionResults += ceil($num / $divisor);
                if ($sumOfDivisionResults > $threshold) {
                    $thresholdExceeded = false;
                    break;
                }
            }
            
            if ($thresholdExceeded) {
                return $divisor;
            }
        }
        
        return -1;
    }
}

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

Задача: 499. The Maze III
Сложность: hard

В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него.
Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).
Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

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

😎 Решение:

class State {
    public $row, $col, $dist, $path;
    public function __construct($r, $c, $d, $p) {
        $this->row = $r; $this->col = $c; $this->dist = $d; $this->path = $p;
    }
}

class MinHeap extends SplMinHeap {
    protected function compare($a, $b) {
        return $a->dist === $b->dist ? strcmp($a->path, $b->path) : $a->dist - $b->dist;
    }
}

class Solution {
    private $dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]];
    private $dirText = ["l", "u", "r", "d"];

    function findShortestWay($maze, $ball, $hole) {
        $m = count($maze); $n = count($maze[0]);
        $heap = new MinHeap();
        $seen = array_fill(0, $m, array_fill(0, $n, false));
        $heap->insert(new State($ball[0], $ball[1], 0, ""));
        
        while (!$heap->isEmpty()) {
            $curr = $heap->extract();
            if ($seen[$curr->row][$curr->col]) continue;
            if ($curr->row == $hole[0] && $curr->col == $hole[1]) return $curr->path;
            $seen[$curr->row][$curr->col] = true;

            foreach ($this->dirs as $i => [$dy, $dx]) {
                $r = $curr->row; $c = $curr->col; $dist = 0;
                while ($r + $dy >= 0 && $r + $dy < $m && $c + $dx >= 0 && $c + $dx < $n && $maze[$r + $dy][$c + $dx] == 0) {
                    $r += $dy; $c += $dx; $dist++;
                    if ($r == $hole[0] && $c == $hole[1]) break;
                }
                $heap->insert(new State($r, $c, $curr->dist + $dist, $curr->path . $this->dirText[$i]));
            }
        }
        return "impossible";
    }
}

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

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

class Solution {
    private $memo = [];
    private $add = [1 => true, 9 => true, 99 => true];

    function getLengthOfOptimalCompression($s, $k) {
        return $this->dp($s, 0, chr(ord('a') + 26), 0, $k);
    }

    private function dp($s, $idx, $lastChar, $lastCharCount, $k) {
        if ($k < 0) {
            return PHP_INT_MAX / 2;
        }

        if ($idx == strlen($s)) {
            return 0;
        }

        $key = $idx * 101 * 27 * 101 + (ord($lastChar) - ord('a')) * 101 * 101 + $lastCharCount * 101 + $k;

        if (isset($this->memo[$key])) {
            return $this->memo[$key];
        }

        $deleteChar = $this->dp($s, $idx + 1, $lastChar, $lastCharCount, $k - 1);
        if ($s[$idx] == $lastChar) {
            $keepChar = $this->dp($s, $idx + 1, $lastChar, $lastCharCount + 1, $k) + (isset($this->add[$lastCharCount]) ? 1 : 0);
        } else {
            $keepChar = $this->dp($s, $idx + 1, $s[$idx], 1, $k) + 1;
        }

        $res = min($keepChar, $deleteChar);
        $this->memo[$key] = $res;

        return $res;
    }
}

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

Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

1⃣Создайте функцию для вычисления оценки слова.

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

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

😎 Решение:

class Solution {
    function maxScoreWords($words, $letters, $score) {
        $letterCount = array_count_values($letters);
        $maxScore = 0;
        
        $n = count($words);
        for ($i = 1; $i < (1 << $n); $i++) {
            $currScore = 0;
            $usedLetters = [];
            $valid = true;
            for ($j = 0; $j < $n; $j++) {
                if ($i & (1 << $j)) {
                    foreach (str_split($words[$j]) as $ch) {
                        if (isset($usedLetters[$ch])) {
                            $usedLetters[$ch]++;
                        } else {
                            $usedLetters[$ch] = 1;
                        }
                        if (!isset($letterCount[$ch]) || $usedLetters[$ch] > $letterCount[$ch]) {
                            $valid = false;
                            break;
                        }
                        $currScore += $score[ord($ch) - ord('a')];
                    }
                }
                if (!$valid) break;
            }
            if ($valid) {
                $maxScore = max($maxScore, $currScore);
            }
        }

        return $maxScore;
    }
}

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

Задача: 31. Next Permutation
Сложность: medium

Дан массив целых чисел nums, представляющий перестановку его элементов. Нужно изменить nums, чтобы получить его следующую перестановку в лексикографическом порядке. Если это невозможно, преобразовать массив в наименьшую возможную перестановку (отсортировать по возрастанию).
Замена должна происходить на месте, используя только постоянную дополнительную память.

Пример:

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

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

1⃣Найти первую пару чисел, идущих по убыванию справа налево.

2⃣Найти наименьшее число справа, которое больше найденного, и поменять их местами.

3⃣Отсортировать оставшуюся часть массива после измененного элемента.

😎 Решение:

class Solution {
    function nextPermutation(&$nums) {
        if (count($nums) <= 1) return;
        
        $i = count($nums) - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) $i--;
        
        if ($i >= 0) {
            $j = count($nums) - 1;
            while ($nums[$j] <= $nums[$i]) $j--;
            $this->swap($nums, $i, $j);
        }
        
        $this->reverse($nums, $i + 1, count($nums) - 1);
    }
    
    function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }
    
    function reverse(&$nums, $start, $end) {
        while ($start < $end) {
            $this->swap($nums, $start, $end);
            $start++;
            $end--;
        }
    }
}

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

Задача: 609. Find Duplicate File in System
Сложность: medium

Получив список paths информации о каталоге, включающий путь к каталогу и все файлы с содержимым в этом каталоге, верните все дубликаты файлов в файловой системе по их путям. Вы можете вернуть ответ в любом порядке. Группа дубликатов состоит как минимум из двух файлов с одинаковым содержимым. Одна строка информации о каталоге во входном списке имеет следующий формат: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" Это означает, что в каталоге "root/d1/d2/.../dm" имеется n файлов (f1.txt, f2.txt ... fn.txt) с содержимым (f1_content, f2_content ... fn_content) соответственно. Обратите внимание, что n >= 1 и m >= 0. Если m = 0, это означает, что каталог является только корневым. На выходе получается список групп дублирующихся путей к файлам. Для каждой группы он содержит все пути к файлам, которые имеют одинаковое содержимое. Путь к файлу - это строка, имеющая следующий формат: "каталог_путь/имя_файла.txt".

Пример:

Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

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

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

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

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

😎 Решение:

function findDuplicate($paths) {
    $contentToFilePaths = [];
    
    foreach ($paths as $path) {
        $parts = explode(" ", $path);
        $root = array_shift($parts);
        
        foreach ($parts as $part) {
            list($fileName, $content) = explode("(", $part);
            $content = rtrim($content, ")");
            
            $filePath = $root . "/" . $fileName;
            if (!isset($contentToFilePaths[$content])) {
                $contentToFilePaths[$content] = [];
            }
            $contentToFilePaths[$content][] = $filePath;
        }
    }
    
    return array_values(array_filter($contentToFilePaths, function($paths) {
        return count($paths) > 1;
    }));
}

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

Задача: 38. Count and Say
Сложность: medium

Последовательность "Count and Say" определяется рекурсивно:
- countAndSay(1) = "1"
- countAndSay(n) — это результат кодирования длин серий countAndSay(n - 1).
Кодирование длин серий (RLE) заменяет повторяющиеся символы на их количество и сам символ.
Например, "3322251" превращается в "23321511".

Пример:

Input: n = 4  
Output: "1211"  

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

1⃣Начинаем с s = "1".

2⃣Для каждого n, начиная с 2, применяем RLE (считаем подряд идущие цифры и формируем новую строку).

3⃣Используем регулярное выражение /(.)\1*/, чтобы находить группы одинаковых символов.

😎 Решение:

function countAndSay($n) {
    $s = "1";
    for ($i = 2; $i <= $n; $i++) {
        $t = "";
        preg_match_all('/(.)\1*/', $s, $matches, PREG_SET_ORDER);
        foreach ($matches as $match) {
            $t .= strlen($match[0]) . $match[1];
        }
        $s = $t;
    }
    return $s;
}

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