Задача: 517. Super Washing Machines
Сложность: hard

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.
За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.
Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1.

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

class Solution {
    function findMinMoves($machines) {
        $n = count($machines);
        $dressTotal = array_sum($machines);
        if ($dressTotal % $n != 0) return -1;

        $dressPerMachine = intval($dressTotal / $n);
        for ($i = 0; $i < $n; $i++) $machines[$i] -= $dressPerMachine;

        $currSum = 0;
        $maxSum = 0;
        $res = 0;
        foreach ($machines as $m) {
            $currSum += $m;
            $maxSum = max($maxSum, abs($currSum));
            $res = max($res, max($maxSum, $m));
        }
        return $res;
    }
}

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

Задача: 992. Subarrays with K Different Integers
Сложность: hard

Дан целочисленный массив nums и целое число k, верните количество "хороших" подмассивов в nums.

"Хороший" массив - это массив, в котором количество различных целых чисел равно k.

Например, в массиве [1,2,3,1,2] есть 3 различных целых числа: 1, 2 и 3.
Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

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

1⃣Подсчет подмассивов с различными элементами:
Используйте два указателя для определения границ текущего подмассива.
Используйте хэш-таблицу для подсчета количества различных элементов в текущем подмассиве.
Перемещайте правый указатель для расширения подмассива и добавления новых элементов.

2⃣Проверка условий:
Как только количество различных элементов достигнет k, перемещайте левый указатель, чтобы уменьшить размер подмассива и попытаться найти все возможные "хорошие" подмассивы.
Подсчитывайте количество подмассивов, удовлетворяющих условию.

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

😎 Решение:

class Solution {
    function countGoodSubarrays($nums, $k) {
        $count = 0;
        $left = 0;
        $right = 0;
        $distinctCount = 0;
        $freq = [];
        
        while ($right < count($nums)) {
            if (!isset($freq[$nums[$right]])) {
                $freq[$nums[$right]] = 0;
            }
            $freq[$nums[$right]]++;
            if ($freq[$nums[$right]] == 1) {
                $distinctCount++;
            }
            $right++;
            
            while ($distinctCount > $k) {
                $freq[$nums[$left]]--;
                if ($freq[$nums[$left]] == 0) {
                    $distinctCount--;
                }
                $left++;
            }
            
            if ($distinctCount == $k) {
                $count++;
            }
        }
        
        return $count;
    }
}

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

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

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

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

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

😎 Решение:

function lastStoneWeightII($stones) {
    $totalSum = array_sum($stones);
    $halfSum = intdiv($totalSum, 2);
    $dp = array_fill(0, $halfSum + 1, 0);

    foreach ($stones as $stone) {
        for ($j = $halfSum; $j >= $stone; $j--) {
            $dp[$j] = max($dp[$j], $dp[$j - $stone] + $stone);
        }
    }

    return $totalSum - 2 * $dp[$halfSum];
}

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

Задача: 383. Ransom Note
Сложность: easy

Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае.
Каждая буква из magazine может быть использована в ransomNote только один раз.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

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

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

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

😎 Решение:

function canConstruct($ransomNote, $magazine) {
    for ($i = 0; $i < strlen($ransomNote); $i++) {
        $char = $ransomNote[$i];
        $index = strpos($magazine, $char);
        if ($index === false) {
            return false;
        }
        $magazine = substr($magazine, 0, $index) . substr($magazine, $index + 1);
    }
    return true;
}

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

Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

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

1⃣Представить каждую строку и столбец как узлы в графе.

2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

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

😎 Решение:

function removeStones($stones) {
    $parent = [];
    
    function find($x) {
        global $parent;
        if (!isset($parent[$x])) $parent[$x] = $x;
        if ($parent[$x] != $x) $parent[$x] = find($parent[$x]);
        return $parent[$x];
    }
    
    function union($x, $y) {
        global $parent;
        $parent[find($x)] = find($y);
    }
    
    foreach ($stones as $stone) {
        union($stone[0], ~$stone[1]);
    }
    
    $uniqueRoots = [];
    foreach ($parent as $key => $value) {
        $uniqueRoots[find($key)] = true;
    }
    
    return count($stones) - count($uniqueRoots);
}

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

Задача: 736. Parse Lisp Expression
Сложность: hard

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

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

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

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

😎 Решение:

class Solution {
    public function evaluate($expression) {
        return $this->evaluateExpression($expression, []);
    }

    private function evaluateExpression($expression, $env) {
        if ($expression[0] !== '(') {
            if (is_numeric($expression) || $expression[0] === '-') {
                return intval($expression);
            }
            return $env[$expression] ?? 0;
        }

        $tokens = $this->tokenize($expression);
        if ($tokens[0] === "let") {
            for ($i = 1; $i < count($tokens) - 2; $i += 2) {
                $env[$tokens[$i]] = $this->evaluateExpression($tokens[$i + 1], $env);
            }
            return $this->evaluateExpression($tokens[count($tokens) - 1], $env);
        } elseif ($tokens[0] === "add") {
            return $this->evaluateExpression($tokens[1], $env) + $this->evaluateExpression($tokens[2], $env);
        } elseif ($tokens[0] === "mult") {
            return $this->evaluateExpression($tokens[1], $env) * $this->evaluateExpression($tokens[2], $env);
        }
        return 0;
    }

    private function tokenize($expression) {
        $tokens = [];
        $token = '';
        $parens = 0;

        for ($i = 0; $i < strlen($expression); $i++) {
            $c = $expression[$i];
            if ($c === '(') {
                $parens++;
                if ($parens === 1) continue;
            } elseif ($c === ')') {
                $parens--;
                if ($parens === 0) {
                    $tokens = array_merge($tokens, $this->tokenize($token));
                    $token = '';
                    continue;
                }
            } elseif ($c === ' ' && $parens === 1) {
                if ($token !== '') {
                    $tokens[] = $token;
                    $token = '';
                }
                continue;
            }
            $token .= $c;
        }
        if ($token !== '') {
            $tokens[] = $token;
        }
        return $tokens;
    }
}

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

Задача: 94. Binary Tree Inorder Traversal
Сложность: easy

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

Пример:

Input: root = [1,null,2,3]
Output: [1,3,2]

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

1⃣Если узел пустой — ничего не делаем.

2⃣Рекурсивно вызываем обход для левого поддерева.

3⃣Добавляем значение текущего узла и затем рекурсивно вызываем обход для правого поддерева.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

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

class Solution {
    public function inorderTraversal($root) {
        $res = [];
        $this->helper($root, $res);
        return $res;
    }

    private function helper($root, &$res) {
        if ($root !== null) {
            $this->helper($root->left, $res);
            $res[] = $root->val;
            $this->helper($root->right, $res);
        }
    }
}

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

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

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

class Solution {
    function powerfulIntegers($x, $y, $bound) {
        $a = $x == 1 ? $bound : intval(log($bound) / log($x));
        $b = $y == 1 ? $bound : intval(log($bound) / log($y));
        $powerfulIntegers = [];

        for ($i = 0; $i <= $a; $i++) {
            for ($j = 0; $j <= $b; $j++) {
                $value = pow($x, $i) + pow($y, $j);
                if ($value <= $bound) {
                    $powerfulIntegers[$value] = true;
                }
                if ($y == 1) break;
            }
            if ($x == 1) break;
        }

        return array_keys($powerfulIntegers);
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

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

😎 Решение:

class Solution {
    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function longestMountain($arr) {
        $n = count($arr);
        $ans = 0;
        $base = 0;

        while ($base < $n) {
            $end = $base;
            if ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
                while ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
                    $end++;
                }
                if ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
                    while ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
                        $end++;
                    }
                    $ans = max($ans, $end - $base + 1);
                }
            }
            $base = max($end, $base + 1);
        }

        return $ans;
    }
}

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

Задача: 1200. Minimum Absolute Difference
Сложность: easy

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

Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr

Пример:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

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

1⃣Инициализация вспомогательного массива:
Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr.
Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement.
Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1.

2⃣Поиск минимальной абсолютной разницы:
Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу.
Проверьте значения на каждом индексе curr:
- если line[curr] равно 0, пропустите этот индекс.
- если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff.
- если currPairDiff больше minPairDiff, продолжайте.
- если currPairDiff равно minPairDiff, добавьте эту пару в список ответов.
- если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff.

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

😎 Решение:

class Solution {
    function minimumAbsDifference($arr) {
        sort($arr);
        $minDiff = PHP_INT_MAX;
        $result = [];
        
        for ($i = 1; $i < count($arr); $i++) {
            $diff = $arr[$i] - $arr[$i - 1];
            if ($diff < $minDiff) {
                $minDiff = $diff;
                $result = [[$arr[$i - 1], $arr[$i]]];
            } else if ($diff == $minDiff) {
                $result[] = [$arr[$i - 1], $arr[$i]];
            }
        }
        
        return $result;
    }
}

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

Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

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

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

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

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function widthOfBinaryTree($root) {
        if ($root === null) return 0;
        
        $maxWidth = 0;
        $queue = [[$root, 0]];

        while (!empty($queue)) {
            $levelSize = count($queue);
            $firstPos = $queue[0][1];
            for ($i = 0; $i < $levelSize; $i++) {
                list($node, $pos) = array_shift($queue);
                if ($node->left !== null) $queue[] = [$node->left, 2 * $pos];
                if ($node->right !== null) $queue[] = [$node->right, 2 * $pos + 1];
            }
            $lastPos = !empty($queue) ? end($queue)[1] : $firstPos;
            $maxWidth = max($maxWidth, $lastPos - $firstPos + 1);
        }

        return $maxWidth;
    }
}

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

Задача: 588. Design In-Memory File System
Сложность: hard

Спроектируйте структуру данных, которая симулирует файловую систему в памяти.
Реализуйте класс FileSystem:
FileSystem() Инициализирует объект системы.
List<String> ls(String path)
Если path является путем к файлу, возвращает список, содержащий только имя этого файла.
Если path является путем к директории, возвращает список имен файлов и директорий в этой директории.
Ответ должен быть в лексикографическом порядке.
void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их.
void addContentToFile(String filePath, String content)
Если filePath не существует, создает файл, содержащий заданный контент.
Если filePath уже существует, добавляет заданный контент к исходному содержимому.
String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath.

Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

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

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

2⃣Обработка команд:
Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом.
Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их.
Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его.
Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути.

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

😎 Решение:

class File {
    public $isFile = false;
    public $files = [];
    public $content = "";
}

class FileSystem {
    private $root;

    public function __construct() {
        $this->root = new File();
    }

    private function navigate($path) {
        $t = $this->root;
        if ($path !== "/") {
            $dirs = explode("/", $path);
            foreach ($dirs as $dir) {
                if (!empty($dir)) {
                    if (!isset($t->files[$dir])) {
                        $t->files[$dir] = new File();
                    }
                    $t = $t->files[$dir];
                }
            }
        }
        return $t;
    }

    public function ls($path) {
        $t = $this->navigate($path);
        if ($t->isFile) return [basename($path)];
        $res = array_keys($t->files);
        sort($res);
        return $res;
    }

    public function mkdir($path) {
        $this->navigate($path);
    }

    public function addContentToFile($filePath, $content) {
        $t = $this->navigate($filePath);
        $t->isFile = true;
        $t->content .= $content;
    }

    public function readContentFromFile($filePath) {
        return $this->navigate($filePath)->content;
    }
}

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

Задача: 330. Patching Array
Сложность: hard

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

Пример:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

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

1⃣Инициализация переменных:
Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums.

2⃣Основной цикл:
Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n.
Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches.

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

😎 Решение:

class Solution {
    function minPatches($nums, $n) {
        $patches = 0;
        $i = 0;
        $miss = 1;
        while ($miss <= $n) {
            if ($i < count($nums) && $nums[$i] <= $miss) {
                $miss += $nums[$i++];
            } else {
                $miss += $miss;
                $patches++;
            }
        }
        return $patches;
    }
}

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

Задача №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

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

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

3⃣Добавлять полученные комбинации в результирующий массив.

😎 Решение:

class Solution { 
 
    public $result = []; 
 
    function letterCombinations($digits) { 
        if(strlen($digits) == 0) { 
            return []; 
        } 
 
        $layouts = [ 
            2 => range('a', 'c'), 
            3 => range('d', 'f'), 
            4 => range('g', 'i'), 
            5 => range('j', 'l'),  
            6 => range('m', 'o'),  
            7 => range('p', 's'), 
            8 => range('t', 'v'), 
            9 => range('w', 'z'), 
        ]; 
 
        return $this->recursive(0, $digits, $layouts); 
    } 
 
    function recursive ($index, $chars, $layouts, $combine = '') { 
        foreach($layouts[$chars[$index]] as $currentLayout) { 
            if($layouts[$chars[$index + 1]]) { 
                $this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout); 
            } else { 
                $this->result[] = $combine . $currentLayout; 
            } 
        } 
 
        return $this->result; 
    } 
}

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

Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

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

2⃣Итеративный обход
Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

3⃣Возврат результата
Верните список output как результат.

😎 Решение:

class Node {
    public $val;
    public $children;

    function __construct($val = 0, $children = []) {
        $this->val = $val;
        $this->children = $children;
    }
}

class Solution {
    function preorder($root) {
        if ($root === null) return [];
        $stack = [$root];
        $output = [];
        
        while (!empty($stack)) {
            $node = array_pop($stack);
            $output[] = $node->val;
            $children = array_reverse($node->children);
            foreach ($children as $child) {
                $stack[] = $child;
            }
        }
        
        return $output;
    }
}

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

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

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

function treeDiameter($edges) {
    if (count($edges) === 0) return 0;

    $graph = [];
    foreach ($edges as $edge) {
        if (!isset($graph[$edge[0]])) $graph[$edge[0]] = [];
        if (!isset($graph[$edge[1]])) $graph[$edge[1]] = [];
        $graph[$edge[0]][] = $edge[1];
        $graph[$edge[1]][] = $edge[0];
    }

    $farthestNode = 0;

    function dfs($node, $parent, &$graph, &$farthestNode) {
        $maxDepth = 0;
        foreach ($graph[$node] as $neighbor) {
            if ($neighbor !== $parent) {
                $depth = dfs($neighbor, $node, $graph, $farthestNode);
                if ($depth + 1 > $maxDepth) {
                    $maxDepth = $depth + 1;
                    $farthestNode = $neighbor;
                }
            }
        }
        return $maxDepth;
    }

    dfs(0, -1, $graph, $farthestNode);
    $startNode = $farthestNode;

    dfs($startNode, -1, $graph, $farthestNode);
    return dfs($farthestNode, -1, $graph, $farthestNode);
}

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter {
    private $prefixSuffixMap = [];
    
    function __construct($words) {
        foreach ($words as $index => $word) {
            $length = strlen($word);
            for ($prefixLength = 1; $prefixLength <= $length; $prefixLength++) {
                for ($suffixLength = 1; $suffixLength <= $length; $suffixLength++) {
                    $prefix = substr($word, 0, $prefixLength);
                    $suffix = substr($word, $length - $suffixLength);
                    $key = $prefix . '#' . $suffix;
                    $this->prefixSuffixMap[$key] = $index;
                }
            }
        }
    }
    
    function f($pref, $suff) {
        $key = $pref . '#' . $suff;
        return array_key_exists($key, $this->prefixSuffixMap) ? $this->prefixSuffixMap[$key] : -1;
    }
}

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

Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

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

3⃣Верни максимальную длину среди всех цепочек.

😎 Решение:

function longestStrChain($words) {
    usort($words, function($a, $b) {
        return strlen($a) - strlen($b);
    });
    
    $dp = [];
    $longestChain = 1;
    
    foreach ($words as $word) {
        $dp[$word] = 1;
        for ($i = 0; $i < strlen($word); $i++) {
            $predecessor = substr($word, 0, $i) . substr($word, $i + 1);
            if (isset($dp[$predecessor])) {
                $dp[$word] = max($dp[$word], $dp[$predecessor] + 1);
            }
        }
        $longestChain = max($longestChain, $dp[$word]);
    }
    
    return $longestChain;
}

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

Задача: 606. Construct String from Binary Tree
Сложность: medium

Дано бинарное дерево, необходимо вернуть его строковое представление, используя прямой обход (preorder traversal) и правила со скобками:
Скобки для детей обязательны, если есть правый ребёнок
Пропускать пустые скобки, кроме случая, когда отсутствует левый, но есть правый ребёнок

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

class Solution {
    function tree2str($t) {
        $res = "";
        $this->dfs($t, $res);
        return $res;
    }

    function dfs($t, &$res) {
        if ($t == null)
            return;
        $res .= $t->val;
        if ($t->left == null && $t->right == null)
            return;
        $res .= '(';
        $this->dfs($t->left, $res);
        $res .= ')';
        if ($t->right != null) {
            $res .= '(';
            $this->dfs($t->right, $res);
            $res .= ')';
        }
    }
}

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

Задача: 1065. Index Pairs of a String
Сложность: easy

Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words.

Верните пары [i, j] в отсортированном порядке (то есть отсортируйте их по первой координате, а в случае совпадения сортируйте их по второй координате).

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Поддерживайте хэш-набор слов.

2⃣Итерируйте i от 0 до text.length-1. Итерируйте j от i до text.length-1. Если подстрока text[i...j] принадлежит хэш-набору слов, добавьте пару [i, j] в ответ.

3⃣Верните ответ.

😎 Решение:

class Solution {
    function indexPairs($text, $words) {
        $wordsSet = array_flip($words);
        $ans = [];
        
        for ($i = 0; $i < strlen($text); $i++) {
            for ($j = $i; $j < strlen($text); $j++) {
                if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
                    $ans[] = [$i, $j];
                }
            }
        }
        return $ans;
    }
}

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