Задача: 322. Coin Change
Сложность: medium

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

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

class Solution {
    public function coinChange($coins, $amount) {
        return $this->coinChangeHelper(0, $coins, $amount);
    }

    private function coinChangeHelper($idxCoin, $coins, $amount) {
        if ($amount == 0) return 0;
        if ($idxCoin < count($coins) && $amount > 0) {
            $maxVal = intdiv($amount, $coins[$idxCoin]);
            $minCost = PHP_INT_MAX;
            for ($x = 0; $x <= $maxVal; $x++) {
                if ($amount >= $x * $coins[$idxCoin]) {
                    $res = $this->coinChangeHelper($idxCoin + 1, $coins, $amount - $x * $coins[$idxCoin]);
                    if ($res != -1) {
                        $minCost = min($minCost, $res + $x);
                    }
                }
            }
            return $minCost == PHP_INT_MAX ? -1 : $minCost;
        }
        return -1;
    }
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.

Необходимо написать алгоритм, который работает за время O(n).

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

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

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

function arrayContains($arr, $num) {
    foreach ($arr as $item) {
        if ($item === $num) {
            return true;
        }
    }
    return false;
}

function longestConsecutive($nums) {
    $longestStreak = 0;
    foreach ($nums as $num) {
        $currentNum = $num;
        $currentStreak = 1;
        while (arrayContains($nums, $currentNum + 1)) {
            $currentNum += 1;
            $currentStreak += 1;
        }
        if ($currentStreak > $longestStreak) {
            $longestStreak = $currentStreak;
        }
    }
    return $longestStreak;
}

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

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

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

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

Пример:

Input: s = "bcabc"
Output: "abc"

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

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

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

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

😎 Решение:

class Solution {
    function removeDuplicateLetters($s) {
        $stack = [];
        $seen = [];
        $lastOccurrence = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $lastOccurrence[$s[$i]] = $i;
        }

        for ($i = 0; $i < strlen($s); $i++) {
            $c = $s[$i];
            if (!isset($seen[$c])) {
                while (!empty($stack) && $c < end($stack) && $i < $lastOccurrence[end($stack)]) {
                    unset($seen[array_pop($stack)]);
                }
                $seen[$c] = true;
                $stack[] = $c;
            }
        }
        return implode('', $stack);
    }
}

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

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

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

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

class Solution {
    function numBusesToDestination($routes, $source, $target) {
        if ($source == $target) return 0;

        $adjList = [];
        foreach ($routes as $route => $stops) {
            foreach ($stops as $stop) {
                if (!isset($adjList[$stop])) {
                    $adjList[$stop] = [];
                }
                $adjList[$stop][] = $route;
            }
        }

        $q = [];
        $vis = [];
        foreach ($adjList[$source] ?? [] as $route) {
            $q[] = $route;
            $vis[$route] = true;
        }

        $busCount = 1;
        while (count($q) > 0) {
            $size = count($q);
            for ($i = 0; $i < $size; $i++) {
                $route = array_shift($q);
                foreach ($routes[$route] as $stop) {
                    if ($stop == $target) return $busCount;
                    foreach ($adjList[$stop] ?? [] as $nextRoute) {
                        if (!isset($vis[$nextRoute])) {
                            $vis[$nextRoute] = true;
                            $q[] = $nextRoute;
                        }
                    }
                }
            }
            $busCount++;
        }
        return -1;
    }
}

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

Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

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

Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

class Solution {
    function countOrders($n) {
        $MOD = 1_000_000_007;
        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = 1;
        
        for ($i = 1; $i <= $n; $i++) {
            $dp[$i] = $dp[$i - 1] * (2 * $i - 1) * $i % $MOD;
        }
        
        return $dp[$n];
    }
}

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

Задача: 965. Univalued Binary Tree
Сложность: easy

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список.

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

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

class Solution {
    private $vals;
    
    function isUnivalTree($root) {
        $this->vals = [];
        $this->dfs($root);
        foreach ($this->vals as $v) {
            if ($v != $this->vals[0]) {
                return false;
            }
        }
        return true;
    }

    function dfs($node) {
        if ($node != null) {
            $this->vals[] = $node->val;
            $this->dfs($node->left);
            $this->dfs($node->right);
        }
    }
}

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

Задача: 752. Open the Lock
Сложность: medium

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

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

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

function openLock($deadends, $target) {
    function neighbors($node) {
        $res = [];
        for ($i = 0; $i < 4; $i++) {
            $x = intval($node[$i]);
            for ($d = -1; $d <= 1; $d += 2) {
                $y = ($x + $d + 10) % 10;
                $res[] = substr($node, 0, $i) . $y . substr($node, $i + 1);
            }
        }
        return $res;
    }

    $dead = array_flip($deadends);
    $queue = [['0000', 0]];
    $visited = ['0000' => true];

    while (!empty($queue)) {
        list($node, $steps) = array_shift($queue);
        if ($node === $target) return $steps;
        if (isset($dead[$node])) continue;
        foreach (neighbors($node) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = [$neighbor, $steps + 1];
            }
        }
    }

    return -1;
}

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

Задача: 1094. Car Pooling
Сложность: medium

Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).

Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.

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

Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

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

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

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

😎 Решение:

class Solution {
    function carPooling($trips, $capacity) {
        $timestamp = [];
        foreach ($trips as $trip) {
            $timestamp[$trip[1]] = ($timestamp[$trip[1]] ?? 0) + $trip[0];
            $timestamp[$trip[2]] = ($timestamp[$trip[2]] ?? 0) - $trip[0];
        }
        ksort($timestamp);
        $usedCapacity = 0;
        foreach ($timestamp as $change) {
            $usedCapacity += $change;
            if ($usedCapacity > $capacity) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

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

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

3⃣Объединить массивы, созданные для четных и нечетных индексов, в результирующий массив.

😎 Решение:

function beautifulArray($n) {
    return construct($n);
}

function construct($n) {
    if ($n == 1) return [1];
    $odd = array_map(fn($x) => 2 * $x - 1, construct(($n + 1) / 2));
    $even = array_map(fn($x) => 2 * $x, construct($n / 2));
    return array_merge($odd, $even);
}

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

Задача: 859. Buddy Strings
Сложность: easy

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

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

class Solution {
    function buddyStrings($s, $goal) {
        if (strlen($s) != strlen($goal)) return false;
        if ($s == $goal) {
            $freq = array_fill(0, 26, 0);
            foreach (str_split($s) as $ch) {
                if (++$freq[ord($ch) - ord('a')] > 1) return true;
            }
            return false;
        }

        $firstIndex = -1;
        $secondIndex = -1;
        for ($i = 0; $i < strlen($s); ++$i) {
            if ($s[$i] != $goal[$i]) {
                if ($firstIndex == -1) $firstIndex = $i;
                else if ($secondIndex == -1) $secondIndex = $i;
                else return false;
            }
        }

        return $secondIndex != -1 &&
               $s[$firstIndex] == $goal[$secondIndex] &&
               $s[$secondIndex] == $goal[$firstIndex];
    }
}

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

Задача: 477. Total Hamming Distance
Сложность: Medium

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

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

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

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

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

class Solution {
    function totalHammingDistance($nums) {
        $ans = 0;

        if (empty($nums)) {
            return $ans;
        }

        for ($i = 0; $i < count($nums) - 1; $i++) {
            for ($j = $i + 1; $j < count($nums); $j++) {
                $ans += $this->countBits($nums[$i] ^ $nums[$j]);
            }
        }

        return $ans;
    }

    private function countBits($n) {
        $count = 0;
        while ($n > 0) {
            $count += $n & 1;
            $n >>= 1;
        }
        return $count;
    }
}

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

Задача: 779. K-th Symbol in Grammar
Сложность: medium

Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10.

Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110.
Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк.

Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

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

1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal.

2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal).

3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal).

😎 Решение:

class Solution {
    private function depthFirstSearch(int $n, int $k, int $rootVal): int {
        if ($n === 1) return $rootVal;
        $totalNodes = 1 << ($n - 1);
        if ($k > $totalNodes / 2) {
            $nextRootVal = $rootVal === 0 ? 1 : 0;
            return $this->depthFirstSearch($n - 1, $k - $totalNodes / 2, $nextRootVal);
        } else {
            $nextRootVal = $rootVal === 0 ? 0 : 1;
            return $this->depthFirstSearch($n - 1, $k, $nextRootVal);
        }
    }

    public function kthGrammar(int $n, int $k): int {
        return $this->depthFirstSearch($n, $k, 0);
    }
}

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

Задача: 411. Minimum Unique Word Abbreviation
Сложность: hard

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):
"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.
Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

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

1⃣Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.

2⃣Сгенерируйте все возможные аббревиатуры для строки target.

3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:

function generateAbbreviations($word) {
    $result = [];
    generateAbbreviationsHelper(str_split($word), "", 0, 0, $result);
    return $result;
}

function generateAbbreviationsHelper($word, $current, $pos, $count, &$result) {
    if ($pos == count($word)) {
        $result[] = $current . ($count > 0 ? $count : "");
        return;
    }
    generateAbbreviationsHelper($word, $current, $pos + 1, $count + 1, $result);
    generateAbbreviationsHelper($word, $current . ($count > 0 ? $count : "") . $word[$pos], $pos + 1, 0, $result);
}

function minAbbreviation($target, $dictionary) {
    $targetAbbrs = generateAbbreviations($target);
    $dictAbbrs = [];
    foreach ($dictionary as $word) {
        $dictAbbrs = array_merge($dictAbbrs, generateAbbreviations($word));
    }
    $dictAbbrs = array_flip(array_flip($dictAbbrs));
    $validAbbrs = array_diff($targetAbbrs, $dictAbbrs);
    usort($validAbbrs, function($a, $b) { return strlen($a) - strlen($b); });
    return $validAbbrs[0];
}

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

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

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

function toHexString($num) {
    $hexStr = strtoupper(dechex($num));
    $hexStr = str_replace(['0', '1'], ['O', 'I'], $hexStr);
    foreach (str_split($hexStr) as $char) {
        if (!in_array($char, str_split('ABCDEFIO'))) {
            return "ERROR";
        }
    }
    return $hexStr;
}

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

Задача №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n,
- a, b, c и d различны,
- nums[a] + nums[b] + nums[c] + nums[d] == target.
Вы можете вернуть ответ в любом порядке.

Пример:

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

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

1⃣Отсортировать массив для удобного поиска.

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

3⃣Для k = 2 использовать метод двух указателей twoSum.

😎 Решение:

class Solution { 
 
    function fourSum($nums, $target) { 
        sort($nums); 
        return $this->kSum($nums, $target, 4); 
    } 
 
    function kSum($nums, $target, $k) { 
        $res = []; 
 
        if (!count($nums)) { 
            return $res; 
        } 
 
        $averageValue = $target / $k; 
        if ($averageValue < $nums[0] || $nums[count($nums)-1] < $averageValue) { 
            return $res; 
        } 
 
        if ($k == 2) { 
            return $this->twoSum($nums, $target); 
        } 
 
        for ($i = 0; $i < count($nums); $i++) { 
            if ($i == 0 || $nums[$i - 1] != $nums[$i]) { 
                $kSum = $this->kSum(array_slice($nums, $i+1), $target - $nums[$i], $k - 1); 
                foreach ($kSum as $item) { 
                    $res[] = array_merge([$nums[$i]], $item); 
                } 
            } 
        } 
        return $res; 
    } 
 
    function twoSum($nums, $target) { 
        $res = []; 
        $lo = 0; 
        $hi = count($nums) - 1; 
 
        while ($lo < $hi) { 
            $currSum = $nums[$lo] + $nums[$hi]; 
            if ($currSum < $target || ($lo > 0 && $nums[$lo] == $nums[$lo - 1])) { 
                $lo++; 
            } elseif ($currSum > $target || ($hi < count($nums) - 1 && $nums[$hi] == $nums[$hi + 1])) { 
                $hi--; 
            } else { 
                $res[] = [$nums[$lo], $nums[$hi]]; 
                $lo++; 
                $hi--; 
            } 
        } 
        return $res; 
    } 
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

function minCostPath($coins, $maxJump) {
    $n = count($coins);
    if ($coins[0] == -1) return [];
    
    $dp = array_fill(0, $n, PHP_INT_MAX);
    $dp[0] = $coins[0];
    $path = array_fill(0, $n, []);
    $path[0] = [1];
    
    $heap = new SplPriorityQueue();
    $heap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $heap->insert([0, 0], -$coins[0]);
    
    while (!$heap->isEmpty()) {
        $current = $heap->extract();
        $current_cost = -$current['priority'];
        $i = $current['data'][1];
        if ($current_cost > $dp[$i]) continue;
        for ($k = 1; $k <= $maxJump; $k++) {
            if ($i + $k < $n && $coins[$i + $k] != -1) {
                $new_cost = $current_cost + $coins[$i + $k];
                if ($new_cost < $dp[$i + $k] || ($new_cost == $dp[$i + $k] && $path[$i] < array_merge($path[$i], [$i + $k + 1]))) {
                    $dp[$i + $k] = $new_cost;
                    $path[$i + $k] = array_merge($path[$i], [$i + $k + 1]);
                    $heap->insert([$new_cost, $i + $k], -$new_cost);
                }
            }
        }
    }
    
    return $dp[$n - 1] == PHP_INT_MAX ? [] : $path[$n - 1];
}

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

function numSubarraysWithSum($nums, $goal) {
    $prefixSumCount = [0 => 1];
    $currentSum = 0;
    $count = 0;
    
    foreach ($nums as $num) {
        $currentSum += $num;
        if (isset($prefixSumCount[$currentSum - $goal])) {
            $count += $prefixSumCount[$currentSum - $goal];
        }
        if (isset($prefixSumCount[$currentSum])) {
            $prefixSumCount[$currentSum]++;
        } else {
            $prefixSumCount[$currentSum] = 1;
        }
    }
    
    return $count;
}

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

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

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

3⃣Вернуть размер множества.

😎 Решение:

function subarrayBitwiseORs($arr) {
    $result = [];
    $current = [];
    foreach ($arr as $num) {
        $next = [$num];
        foreach ($current as $x) {
            $next[] = $x | $num;
        }
        $current = array_unique($next);
        foreach ($current as $x) {
            $result[$x] = true;
        }
    }
    return count($result);
}

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

Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

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

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

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

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

😎 Решение:

function findLength($nums1, $nums2) {
    $dp = array_fill(0, count($nums1) + 1, array_fill(0, count($nums2) + 1, 0));
    $maxLength = 0;
    for ($i = count($nums1) - 1; $i >= 0; $i--) {
        for ($j = count($nums2) - 1; $j >= 0; $j--) {
            if ($nums1[$i] == $nums2[$j]) {
                $dp[$i][$j] = $dp[$i + 1][$j + 1] + 1;
                $maxLength = max($maxLength, $dp[$i][$j]);
            }
        }
    }
    return $maxLength;
}

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

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray {
    private $sum;

    function __construct($nums) {
        $this->sum = array_fill(0, count($nums) + 1, 0);
        for ($i = 0; $i < count($nums); $i++) {
            $this->sum[$i + 1] = $this->sum[$i] + $nums[$i];
        }
    }

    function sumRange($i, $j) {
        return $this->sum[$j + 1] - $this->sum[$i];
    }
}

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