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

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

Задача: 1353. Maximum Number of Events That Can Be Attended
Сложность: medium

Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi.

Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d.

Верните максимальное количество событий, которые вы можете посетить.

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    function maxEvents($events) {
        usort($events, function($a, $b) {
            return $a[1] <=> $b[1];
        });

        $visitedDays = [];
        $count = 0;
        foreach ($events as $event) {
            list($start, $end) = $event;
            for ($day = $start; $day <= $end; $day++) {
                if (!in_array($day, $visitedDays)) {
                    $visitedDays[] = $day;
                    $count++;
                    break;
                }
            }
        }

        return $count;
    }
}

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

Задача: 155. Min Stack
Сложность: medium

Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

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

2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

class MinStack {
    private $stack = [];

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

    private function last() {
        return end($this->stack);
    }

    public function push($x) {
        if (empty($this->stack)) {
            array_push($this->stack, [$x, $x]);
            return;
        }

        $currentMin = $this->last()[1];
        array_push($this->stack, [$x, min($currentMin, $x)]);
    }

    public function pop() {
        array_pop($this->stack);
    }

    public function top() {
        $last = $this->last();
        return $last[0];
    }

    public function getMin() {
        $last = $this->last();
        return $last[1];
    }
}

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

Задача: 80. Remove Duplicates from Sorted Array II
Сложность: medium

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

Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.

Верните k после размещения итогового результата в первые k слотов массива nums.

Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).

Пример:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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

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

2⃣Обработка элементов массива: Для каждого элемента в массиве:

3⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count.
Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент.
Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1.
Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи.

😎 Решение:

function removeDuplicates(&$nums) {
    $j = 0;
    for ($i = 0; $i < count($nums); $i++) {
        if ($j < 2 || $nums[$i] > $nums[$j - 2]) {
            $nums[$j++] = $nums[$i];
        }
    }
    return $j;
}

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

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

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution {
    function isMajorityElement($nums, $target) {
        $count = 0;
        foreach ($nums as $num) {
            if ($num == $target) {
                $count++;
            }
        }
        return $count > count($nums) / 2;
    }
}

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

Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

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

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

class Solution {
    function pruneTree($root) {
        return $this->containsOne($root) ? $root : null;
    }

    private function containsOne($node) {
        if ($node === null) return false;

        $leftContainsOne = $this->containsOne($node->left);
        $rightContainsOne = $this->containsOne($node->right);

        if (!$leftContainsOne) $node->left = null;
        if (!$rightContainsOne) $node->right = null;

        return $node->val === 1 || $leftContainsOne || $rightContainsOne;
    }
}

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

Задача: 1514. Path with Maximum Probability
Сложность: medium

Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].

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

Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.

Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

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

1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.

2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].

3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].

😎 Решение:

class Solution {
    function maxProbability($n, $edges, $succProb, $start, $end) {
        $maxProb = array_fill(0, $n, 0.0);
        $maxProb[$start] = 1.0;

        for ($i = 0; $i < $n - 1; $i++) {
            $hasUpdate = false;
            for ($j = 0; $j < count($edges); $j++) {
                $u = $edges[$j][0];
                $v = $edges[$j][1];
                $pathProb = $succProb[$j];
                if ($maxProb[$u] * $pathProb > $maxProb[$v]) {
                    $maxProb[$v] = $maxProb[$u] * $pathProb;
                    $hasUpdate = true;
                }
                if ($maxProb[$v] * $pathProb > $maxProb[$u]) {
                    $maxProb[$u] = $maxProb[$v] * $pathProb;
                    $hasUpdate = true;
                }
            }
            if (!$hasUpdate) {
                break;
            }
        }

        return $maxProb[$end];
    }
}

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

Задача: 77. Combinations
Сложность: medium

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

function combine($n, $k) {
    $ans = [];

    $backtrack = function (&$curr, $firstNum) use ($n, $k, &$ans, &$backtrack) {
        if (count($curr) === $k) {
            array_push($ans, $curr);
            return;
        }

        $need = $k - count($curr);
        $remain = $n - $firstNum + 1;
        $available = $remain - $need;

        for ($num = $firstNum; $num <= $firstNum + $available; $num++) {
            array_push($curr, $num);
            $backtrack($curr, $num + 1);
            array_pop($curr);
        }
    };

    $backtrack([], 1);
    return $ans;
}

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

Задача: 1162. As Far from Land as Possible
Сложность: medium

Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1.

Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.

Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

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

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

2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance.

3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1).

😎 Решение:

class Solution {
    function maxDistance($grid) {
        $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        $visited = $grid;
        $q = [];
        
        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] == 1) {
                    $q[] = [$i, $j];
                }
            }
        }
        
        $distance = -1;
        while (count($q) > 0) {
            $qSize = count($q);
            while ($qSize-- > 0) {
                list($landX, $landY) = array_shift($q);
                foreach ($directions as $dir) {
                    $x = $landX + $dir[0];
                    $y = $landY + $dir[1];
                    if ($x >= 0 && $y >= 0 && $x < count($grid) && $y < count($grid[0]) && $visited[$x][$y] == 0) {
                        $visited[$x][$y] = 1;
                        $q[] = [$x, $y];
                    }
                }
            }
            $distance++;
        }
        
        return $distance == 0 ? -1 : $distance;
    }
}

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

Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

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

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

function mergeSort(&$nums) {
    if (count($nums) > 1) {
        $mid = count($nums) / 2;
        $left_half = array_slice($nums, 0, $mid);
        $right_half = array_slice($nums, $mid);

        mergeSort($left_half);
        mergeSort($right_half);

        $i = $j = $k = 0;
        while ($i < count($left_half) && $j < count($right_half)) {
            if ($left_half[$i] < $right_half[$j]) {
                $nums[$k++] = $left_half[$i++];
            } else {
                $nums[$k++] = $right_half[$j++];
            }
        }

        while ($i < count($left_half)) {
            $nums[$k++] = $left_half[$i++];
        }

        while ($j < count($right_half)) {
            $nums[$k++] = $right_half[$j++];
        }
    }
}

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

Задача: 1423. Maximum Points You Can Obtain from Cards
Сложность: medium

Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints.
За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.
Ваш результат - это сумма очков взятых карт.

Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.

Пример:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

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

1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.

2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.

3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.

😎 Решение:

class Solution {
    function maxScore($cardPoints, $k) {
        $n = count($cardPoints);
        $frontSetOfCards = array_fill(0, $k + 1, 0);
        $rearSetOfCards = array_fill(0, $k + 1, 0);
        
        for ($i = 0; $i < $k; $i++) {
            $frontSetOfCards[$i + 1] = $cardPoints[$i] + $frontSetOfCards[$i];
            $rearSetOfCards[$i + 1] = $cardPoints[$n - $i - 1] + $rearSetOfCards[$i];
        }
        
        $maxScore = 0;
        for ($i = 0; $i <= $k; $i++) {
            $currentScore = $frontSetOfCards[$i] + $rearSetOfCards[$k - $i];
            $maxScore = max($maxScore, $currentScore);
        }
        
        return $maxScore;
    }
}

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