#easy
Задача: 590. N-ary Tree Postorder Traversal

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

Сериализация входных данных 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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

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

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

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

😎 Решение:

class Node {
    public $val;
    public $children;

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

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

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

#medium
Задача: 592. Fraction Addition and Subtraction

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

Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

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

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

😎 Решение:

class Solution {
    function fractionAddition($expression) {
        $sign = [];
        if ($expression[0] !== '-') $sign[] = '+';
        for ($i = 0; $i < strlen($expression); $i++) {
            if ($expression[$i] == '+' || $expression[$i] == '-') {
                $sign[] = $expression[$i];
            }
        }

        $fractions = preg_split('/(?=[+-])/', $expression);
        $prev_num = 0;
        $prev_den = 1;
        $i = 0;

        foreach ($fractions as $sub) {
            if ($sub == "") continue;
            list($num, $den) = sscanf($sub, '%d/%d');
            $g = abs($this->gcd($prev_den, $den));
            if ($sign[$i++] == '+') $prev_num = $prev_num * $den / $g + $num * $prev_den / $g;
            else $prev_num = $prev_num * $den / $g - $num * $prev_den / $g;
            $prev_den = $prev_den * $den / $g;
            $g = abs($this->gcd($prev_den, $prev_num));
            $prev_num /= $g;
            $prev_den /= $g;
        }

        return "$prev_num/$prev_den";
    }

    private function gcd($a, $b) {
        while ($b != 0) {
            $t = $b;
            $b = $a % $b;
            $a = $t;
        }
        return $a;
    }
}

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

#medium
Задача: 593. Valid Square

Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.

Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.

Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).

Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

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

2⃣Проверьте, равны ли все стороны и диагонали для трех уникальных случаев перестановки точек.

3⃣Верните true, если хотя бы одна из проверок проходит.

😎 Решение:

class Solution {
    private function dist($p1, $p2) {
        return pow($p2[1] - $p1[1], 2) + pow($p2[0] - $p1[0], 2);
    }

    private function check($p1, $p2, $p3, $p4) {
        return $this->dist($p1, $p2) > 0 &&
               $this->dist($p1, $p2) == $this->dist($p2, $p3) &&
               $this->dist($p2, $p3) == $this->dist($p3, $p4) &&
               $this->dist($p3, $p4) == $this->dist($p4, $p1) &&
               $this->dist($p1, $p3) == $this->dist($p2, $p4);
    }

    public function validSquare($p1, $p2, $p3, $p4) {
        return $this->check($p1, $p2, $p3, $p4) ||
               $this->check($p1, $p3, $p2, $p4) ||
               $this->check($p1, $p2, $p4, $p3);
    }
}

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

#Easy
Задача: 598. Range Addition II

Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.

Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.

Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

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

1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).

2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).

3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.

😎 Решение:

class Solution {
    function maxCount($m, $n, $ops) {
        $minA = $m;
        $minB = $n;
        foreach ($ops as $op) {
            $minA = min($minA, $op[0]);
            $minB = min($minB, $op[1]);
        }
        return $minA * $minB;
    }
}

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

#easy
Задача: 594. Longest Harmonious Subsequence

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

Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

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

😎 Решение:

class Solution {
    function findLHS($nums) {
        $count = [];
        $res = 0;
        
        foreach ($nums as $num) {
            if (isset($count[$num])) {
                $count[$num]++;
            } else {
                $count[$num] = 1;
            }
            if (isset($count[$num + 1])) {
                $res = max($res, $count[$num] + $count[$num + 1]);
            }
            if (isset($count[$num - 1])) {
                $res = max($res, $count[$num] + $count[$num - 1]);
            }
        }
        
        return $res;
    }
}

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

#Easy
Задача: 599. Minimum Index Sum of Two Lists

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появляется и в list1, и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

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

1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

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

😎 Решение:

class Solution {
    function findRestaurant($list1, $list2) {
        $map = [];
        for ($i = 0; $i < count($list1); $i++) {
            for ($j = 0; $j < count($list2); $j++) {
                if ($list1[$i] == $list2[$j]) {
                    if (!isset($map[$i + $j])) {
                        $map[$i + $j] = [];
                    }
                    $map[$i + $j][] = $list1[$i];
                }
            }
        }
        $minIndexSum = min(array_keys($map));
        return $map[$minIndexSum];
    }
}

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

#Hard
Задача: 600. Non-negative Integers without Consecutive Ones

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

class Solution {
    function findIntegers($num) {
        $count = 0;
        for ($i = 0; $i <= $num; $i++) {
            if ($this->check($i)) {
                $count++;
            }
        }
        return $count;
    }

    function check($n) {
        $i = 31;
        while ($i > 0) {
            if (($n & (1 << $i)) != 0 && ($n & (1 << ($i - 1))) != 0) {
                return false;
            }
            $i--;
        }
        return true;
    }
}

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

#medium
Задача: 513. Find Bottom Left Tree Value

Дан корень двоичного дерева, верните самое левое значение в последней строке дерева.

Пример:

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

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

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

2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    private $maxDepth = -1;
    private $bottomLeftValue = 0;
    
    function findBottomLeftValue($root) {
        $this->dfs($root, 0);
        return $this->bottomLeftValue;
    }
    
    private function dfs($current, $depth) {
        if ($current == null) return;
        
        if ($depth > $this->maxDepth) {
            $this->maxDepth = $depth;
            $this->bottomLeftValue = $current->val;
        }
        
        $this->dfs($current->left, $depth + 1);
        $this->dfs($current->right, $depth + 1);
    }
}

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

#medium
Задача: 1286. Iterator for Combination

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

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

😎 Решение:

class CombinationIterator {
    private $combinations;

    function __construct($characters, $combinationLength) {
        $this->combinations = [];
        $n = strlen($characters);
        $k = $combinationLength;
        for ($bitmask = 0; $bitmask < (1 << $n); $bitmask++) {
            if (substr_count(decbin($bitmask), '1') == $k) {
                $curr = [];
                for ($j = 0; $j < $n; $j++) {
                    if ($bitmask & (1 << ($n - $j - 1))) {
                        $curr[] = $characters[$j];
                    }
                }
                $this->combinations[] = implode('', $curr);
            }
        }
    }

    function next() {
        return array_pop($this->combinations);
    }

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

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

#hard
Задача: 1675. Minimize Deviation in Array

Вам дан массив nums из n положительных целых чисел.

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

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

Пример:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

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

1⃣ Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

2⃣ Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

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

😎 Решение:

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function minimumDeviation($nums) {
        $evens = new SplPriorityQueue();
        $minimum = PHP_INT_MAX;
        
        foreach ($nums as $num) {
            if ($num % 2 == 0) {
                $evens->insert($num, $num);
                $minimum = min($minimum, $num);
            } else {
                $evens->insert($num * 2, $num * 2);
                $minimum = min($minimum, $num * 2);
            }
        }
        
        $minDeviation = PHP_INT_MAX;
        
        while (!$evens->isEmpty()) {
            $currentValue = $evens->extract();
            $minDeviation = min($minDeviation, $currentValue - $minimum);
            if ($currentValue % 2 == 0) {
                $evens->insert($currentValue / 2, $currentValue / 2);
                $minimum = min($minimum, $currentValue / 2);
            } else {
                break;
            }
        }
        
        return $minDeviation;
    }
}

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

#medium
Задача: 515. Find Largest Value in Each Tree Row

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

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

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

1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

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

3⃣Добавьте currMax в ans. Верните ans.

😎 Решение:

class Solution {
    function largestValues($root) {
        if ($root == null) return [];
        
        $ans = [];
        $queue = new SplQueue();
        $queue->enqueue($root);
        
        while (!$queue->isEmpty()) {
            $currentLength = $queue->count();
            $currMax = PHP_INT_MIN;
            
            for ($i = 0; $i < $currentLength; $i++) {
                $node = $queue->dequeue();
                $currMax = max($currMax, $node->val);
                if ($node->left != null) $queue->enqueue($node->left);
                if ($node->right != null) $queue->enqueue($node->right);
            }
            
            $ans[] = $currMax;
        }
        
        return $ans;
    }
}

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

#medium
Задача: 516. Longest Palindromic Subsequence

Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s.

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

Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎 Решение:

class Solution {
    function longestPalindromeSubseq($s) {
        $n = strlen($s);
        $memo = [];
        
        function lps($s, $l, $r, &$memo) {
            $key = $l . "," . $r;
            if (isset($memo[$key])) return $memo[$key];
            if ($l > $r) return 0;
            if ($l == $r) return 1;
            
            if ($s[$l] == $s[$r]) {
                $memo[$key] = lps($s, $l + 1, $r - 1, $memo) + 2;
            } else {
                $memo[$key] = max(lps($s, $l, $r - 1, $memo), lps($s, $l + 1, $r, $memo));
            }
            return $memo[$key];
        }
        
        return lps($s, 0, $n - 1, $memo);
    }
}

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

#hard
Задача: 517. Super Washing Machines

У вас есть 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;
    }
}

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

#medium
Задача: 518. Coin Change II

Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.

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

Ответ гарантированно вписывается в знаковое 32-битное целое число.

Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.

3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.

😎 Решение:

class Solution {
    function change($amount, $coins) {
        $memo = array_fill(0, count($coins), array_fill(0, $amount + 1, -1));

        function numberOfWays($i, $amount, $coins, &$memo) {
            if ($amount == 0) return 1;
            if ($i == count($coins)) return 0;
            if ($memo[$i][$amount] != -1) return $memo[$i][$amount];

            if ($coins[$i] > $amount) {
                $memo[$i][$amount] = numberOfWays($i + 1, $amount, $coins, $memo);
            } else {
                $memo[$i][$amount] = numberOfWays($i, $amount - $coins[$i], $coins, $memo) + numberOfWays($i + 1, $amount, $coins, $memo);
            }
            return $memo[$i][$amount];
        }

        return numberOfWays(0, $amount, $coins, $memo);
    }
}

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

#easy
Задача: 520. Detect Capital

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

class Solution {
    function detectCapitalUse($word) {
        $pattern = '/^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$/';
        return preg_match($pattern, $word) === 1;
    }
}

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

#hard
Задача: 632. Smallest Range Covering Elements from K Lists

У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.

Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

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

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

2⃣Нахождение минимального диапазона
Используйте кучу для извлечения минимального элемента и обновления текущего диапазона. Обновляйте максимальный элемент в текущем диапазоне при добавлении новых элементов.

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

😎 Решение:

function smallestRange($nums) {
    $minHeap = new SplPriorityQueue();
    $minHeap->setExtractFlags(SplPriorityQueue::EXTR_DATA);
    $maxValue = PHP_INT_MIN;

    foreach ($nums as $i => $list) {
        $minHeap->insert([$list[0], $i, 0], -$list[0]);
        $maxValue = max($maxValue, $list[0]);
    }

    $rangeStart = 0;
    $rangeEnd = PHP_INT_MAX;

    while ($minHeap->count() == count($nums)) {
        [$minValue, $row, $col] = $minHeap->extract();
        if ($maxValue - $minValue < $rangeEnd - $rangeStart) {
            $rangeStart = $minValue;
            $rangeEnd = $maxValue;
        }

        if ($col + 1 < count($nums[$row])) {
            $value = $nums[$row][$col + 1];
            $minHeap->insert([$value, $row, $col + 1], -$value);
            $maxValue = max($maxValue, $value);
        }
    }

    return [$rangeStart, $rangeEnd];
}

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

#easy
Задача: 521. Longest Uncommon Subsequence I

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.

Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.

Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

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

1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности.

2⃣В противном случае: Вычислите длины строк a и b. Верните длину более длинной строки.

😎 Решение:

class Solution {
    function findLUSlength($a, $b) {
        if ($a == $b) {
            return -1;
        } else {
            return max(strlen($a), strlen($b));
        }
    }
}

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

#medium
Задача: 523. Continuous Subarray Sum

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.

Хороший подмассив — это подмассив, который:

имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:

Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

class Solution {
    function checkSubarraySum($nums, $k) {
        $prefixMod = 0;
        $modSeen = [0 => -1];
        
        for ($i = 0; $i < count($nums); $i++) {
            $prefixMod = ($prefixMod + $nums[$i]) % $k;
            
            if (array_key_exists($prefixMod, $modSeen)) {
                if ($i - $modSeen[$prefixMod] > 1) {
                    return true;
                }
            } else {
                $modSeen[$prefixMod] = $i;
            }
        }
        
        return false;
    }
}

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

#Easy
Задача: 604. Design Compressed String Iterator

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

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

- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.

Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

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

1⃣Предварительная обработка
Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

2⃣Операция next()
Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

3⃣Операция hasNext()
Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎 Решение:

class StringIterator {
    private $res = [];
    private $ptr = 0;

    public function __construct($s) {
        $i = 0;
        while ($i < strlen($s)) {
            $ch = $s[$i++];
            $num = 0;
            while ($i < strlen($s) && is_numeric($s[$i])) {
                $num = $num * 10 + intval($s[$i]);
                $i++;
            }
            for ($j = 0; $j < $num; $j++) {
                $this->res[] = $ch;
            }
        }
    }

    public function next() {
        return $this->hasNext() ? $this->res[$this->ptr++] : ' ';
    }

    public function hasNext() {
        return $this->ptr < count($this->res);
    }
}

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

#medium
Задача: 524. Longest Word in Dictionary through Deleting


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

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

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

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
    function isSubsequence($x, $y) {
        $j = 0;
        for ($i = 0; $i < strlen($y) && $j < strlen($x); $i++) {
            if ($x[$j] == $y[$i]) {
                $j++;
            }
        }
        return $j == strlen($x);
    }

    function findLongestWord($s, $d) {
        $max_str = "";
        foreach ($d as $str) {
            if ($this->isSubsequence($str, $s)) {
                if (strlen($str) > strlen($max_str) || (strlen($str) == strlen($max_str) && strcmp($str, $max_str) < 0)) {
                    $max_str = $str;
                }
            }
        }
        return $max_str;
    }
}

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

#Easy
Задача: 605. Can Place Flowers

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

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    function canPlaceFlowers($flowerbed, $n) {
        $count = 0;
        for ($i = 0; $i < count($flowerbed); $i++) {
            if ($flowerbed[$i] == 0) {
                $emptyLeft = $i == 0 || $flowerbed[$i - 1] == 0;
                $emptyRight = $i == count($flowerbed) - 1 || $flowerbed[$i + 1] == 0;
                if ($emptyLeft && $emptyRight) {
                    $flowerbed[$i] = 1;
                    $count++;
                }
            }
        }
        return $count >= $n;
    }
}

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