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

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

class Solution {
    function isPossible($target) {
        $pq = new SplPriorityQueue();
        $total = array_sum($target);
        foreach ($target as $num) {
            $pq->insert($num, $num);
        }
        
        while ($pq->top() > 1) {
            $maxVal = $pq->extract();
            $total -= $maxVal;
            if ($maxVal < $total || $total == 0 || $maxVal % $total == 0) {
                return false;
            }
            $pq->insert($maxVal % $total, $maxVal % $total);
            $total += $pq->top();
        }
        return true;
    }
}

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

Задача: 281. Zigzag Iterator
Сложность: medium

Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.
Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.

Пример:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

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

1⃣Инициализация объекта:
Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors.
Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст.

2⃣Метод next:
Удалите первую пару индексов из очереди.
Извлеките элемент из соответствующего списка по указанным индексам.
Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди.
Верните извлеченный элемент.

3⃣Метод hasNext:
Проверьте, пуста ли очередь.
Верните true, если в очереди есть элементы, и false в противном случае.

😎 Решение:

class ZigzagIterator {
    private $vectors = [];
    private $queue = [];

    public function __construct($v1, $v2) {
        $this->vectors[] = $v1;
        $this->vectors[] = $v2;
        foreach ($this->vectors as $index => $vec) {
            if (count($vec) > 0) {
                $this->queue[] = [$index, 0];
            }
        }
    }

    public function next() {
        list($vecIndex, $elemIndex) = array_shift($this->queue);
        $nextElemIndex = $elemIndex + 1;
        if ($nextElemIndex < count($this->vectors[$vecIndex])) {
            $this->queue[] = [$vecIndex, $nextElemIndex];
        }

        return $this->vectors[$vecIndex][$elemIndex];
    }

    public function hasNext() {
        return count($this->queue) > 0;
    }
}

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

Задача: 339. Nested List Weight Sum
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.
Верните сумму каждого целого числа в nestedList, умноженного на его глубину.

Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

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

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

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

😎 Решение:

class Solution {
    function depthSum($nestedList) {
        return $this->dfs($nestedList, 1);
    }
    
    private function dfs($list, $depth) {
        $total = 0;
        foreach ($list as $nested) {
            if ($nested->isInteger()) {
                $total += $nested->getInteger() * $depth;
            } else {
                $total += $this->dfs($nested->getList(), $depth + 1);
            }
        }
        return $total;
    }
}

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

Задача: 921. Minimum Add to Make Parentheses Valid4
Сложность: medium

Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

1⃣Инициализировать два счетчика open_needed и close_needed.

2⃣Пройти по строке s символ за символом:
Если текущий символ - открывающая скобка (, увеличьте open_needed.
Если текущий символ - закрывающая скобка ), проверьте:
Если open_needed больше 0, уменьшите open_needed.
Иначе увеличьте close_needed.

3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок.

😎 Решение:

function minAddToMakeValid($s) {
    $openNeeded = 0;
    $closeNeeded = 0;
    
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] == '(') {
            $openNeeded++;
        } elseif ($s[$i] == ')') {
            if ($openNeeded > 0) {
                $openNeeded--;
            } else {
                $closeNeeded++;
            }
        }
    }
    
    return $openNeeded + $closeNeeded;
}

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

Задача: 919. Complete Binary Tree Inserter
Сложность: medium

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

Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.

Пример:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

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 CBTInserter {
    private $root;
    private $deque;

    function __construct($root) {
        $this->root = $root;
        $this->deque = [];
        $queue = [$root];
        while (!empty($queue)) {
            $node = array_shift($queue);
            if ($node->left === null || $node->right === null) {
                $this->deque[] = $node;
            }
            if ($node->left !== null) {
                $queue[] = $node->left;
            }
            if ($node->right !== null) {
                $queue[] = $node->right;
            }
        }
    }

    function insert($v) {
        $node = $this->deque[0];
        $newNode = new TreeNode($v);
        if ($node->left === null) {
            $node->left = $newNode;
        } else {
            $node->right = $newNode;
            array_shift($this->deque);
        }
        $this->deque[] = $newNode;
        return $node->val;
    }

    function get_root() {
        return $this->root;
    }
}

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

Задача: 688. Knight Probability in Chessboard
Сложность: medium

На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).

Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.

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

Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.

Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы.

Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

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

1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.

2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j].

3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.

😎 Решение:

class Solution {
    function knightProbability($n, $k, $row, $column) {
        $directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]];
        $dp = array_fill(0, $k + 1, array_fill(0, $n, array_fill(0, $n, 0)));
        $dp[0][$row][$column] = 1;

        for ($moves = 1; $moves <= $k; $moves++) {
            for ($i = 0; $i < $n; $i++) {
                for ($j = 0; $j < $n; $j++) {
                    foreach ($directions as $direction) {
                        $prevI = $i - $direction[0];
                        $prevJ = $j - $direction[1];
                        if ($prevI >= 0 && $prevI < $n && $prevJ >= 0 && $prevJ < $n) {
                            $dp[$moves][$i][$j] += $dp[$moves - 1][$prevI][$prevJ] / 8;
                        }
                    }
                }
            }
        }

        $totalProbability = 0;
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $totalProbability += $dp[$k][$i][$j];
            }
        }

        return $totalProbability;
    }
}

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