Задача: 746. Min Cost Climbing Stairs
Сложность: easy

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

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

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
    return min(dp[-1], dp[-2])

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

Задача: 765. Couples Holding Hands
Сложность: hard

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом.

3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.

😎 Решение:

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        self.N = len(row) // 2
        self.pairs = [[0, 0] for _ in range(self.N)]
        for i in range(self.N):
            self.pairs[i][0] = row[2 * i] // 2
            self.pairs[i][1] = row[2 * i + 1] // 2
        return self.solve(0)
    
    def swap(self, a: int, b: int, c: int, d: int):
        self.pairs[a][b], self.pairs[c][d] = self.pairs[c][d], self.pairs[a][b]
    
    def solve(self, i: int) -> int:
        if i == self.N:
            return 0
        x, y = self.pairs[i]
        if x == y:
            return self.solve(i + 1)
        
        jx, kx, jy, ky = 0, 0, 0, 0
        for j in range(i + 1, self.N):
            for k in range(2):
                if self.pairs[j][k] == x:
                    jx, kx = j, k
                if self.pairs[j][k] == y:
                    jy, ky = j, k
        
        self.swap(i, 1, jx, kx)
        ans1 = 1 + self.solve(i + 1)
        self.swap(i, 1, jx, kx)
        
        self.swap(i, 0, jy, ky)
        ans2 = 1 + self.solve(i + 1)
        self.swap(i, 0, jy, ky)
        
        return min(ans1, ans2)

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

Задача: 213. House Robber II
Сложность: medium

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

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

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1️⃣Обработка базовых случаев:
Если массив nums пуст, возвращаем 0. Если в массиве nums только один дом, возвращаем значение этого дома.

2️⃣Разделение задачи на две подзадачи:
Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и len(nums) - 2. Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и len(nums) - 1.

3️⃣Сравнение результатов и возврат максимального значения:
Возвращаем максимальное значение из двух полученных результатов.

😎 Решение:

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        max1 = self.rob_simple(nums, 0, len(nums) - 2)
        max2 = self.rob_simple(nums, 1, len(nums) - 1)

        return max(max1, max2)

    def rob_simple(self, nums, start, end):
        t1, t2 = 0, 0

        for i in range(start, end + 1):
            temp = t1
            current = nums[i]
            t1 = max(current + t2, t1)
            t2 = temp

        return t1

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

Задача: 472. Concatenated Words
Сложность: hard

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.

Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

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

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

class Solution:
    def dfs(self, word, length, visited, dictionary):
        if length == len(word):
            return True
        if visited[length]:
            return False
        visited[length] = True
        for i in range(len(word) - (1 if length == 0 else 0), length, -1):
            if word[length:i] in dictionary and self.dfs(word, i, visited, dictionary):
                return True
        return False

    def findAllConcatenatedWordsInADict(self, words):
        dictionary = set(words)
        answer = []
        for word in words:
            visited = [False] * len(word)
            if self.dfs(word, 0, visited, dictionary):
                answer.append(word)
        return answer

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

def addBoldTags(keywords, s):
    n = len(s)
    bold = [False] * n
    for word in keywords:
        start = s.find(word)
        while start != -1:
            for i in range(start, start + len(word)):
                bold[i] = True
            start = s.find(word, start + 1)
    
    result = []
    i = 0
    while i < n:
        if bold[i]:
            result.append("<b>")
            while i < n and bold[i]:
                result.append(s[i])
                i += 1
            result.append("</b>")
        else:
            result.append(s[i])
            i += 1
    return "".join(result)

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

Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard

Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.

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

Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

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

1️⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2️⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием: dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой). dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3️⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)        if not prices or k == 0:
            return 0

        if k * 2 >= n:
            res = 0
            for i, j in zip(prices[1:], prices[:-1]):
                res += max(0, i - j)
            return res][ishold] = balance
        dp = [[[-math.inf] * 2 for _ in range(k + 1)] for _ in range(n)]
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]
        for i in range(1, n):
            for j in range(k + 1):
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]
                if j > 0:
                    dp[i][j][1] = max(
                        dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]
                    )

        res = max(dp[n - 1][j][0] for j in range(k + 1))
        return res

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        
        def powmod(x, y, mod):
            result = 1
            x = x % mod
            while y > 0:
                if y % 2 == 1:
                    result = (result * x) % mod
                y = y // 2
                x = (x * x) % mod
            return result
        
        def superPowHelper(a, b, mod):
            if not b:
                return 1
            last_digit = b.pop()
            part1 = powmod(a, last_digit, mod)
            part2 = powmod(superPowHelper(a, b, mod), 10, mod)
            return (part1 * part2) % mod
        
        return superPowHelper(a, b, MOD)

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

Задача: 1089. Duplicate Zeros
Сложность: easy

Дан массив целых чисел фиксированной длины arr, дублируйте каждое вхождение нуля, сдвигая оставшиеся элементы вправо.

Учтите, что элементы за пределами длины исходного массива не записываются. Внесите указанные изменения в массив на месте и ничего не возвращайте.

Пример:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

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

1⃣Найдите количество нулей, которые будут продублированы, назовем это possible_dups. Необходимо убедиться, что мы не считаем нули, которые будут отброшены, так как отброшенные нули не будут частью итогового массива. Количество possible_dups даст нам количество элементов, которые будут отброшены из исходного массива. В любой момент времени length_ - possible_dups — это количество элементов, которые будут включены в итоговый массив.

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

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

😎 Решение:

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        possibleDups = 0
        length_ = len(arr) - 1

        for left in range(length_ + 1):
            if left > length_ - possibleDups:
                break
            if arr[left] == 0:
                if left == length_ - possibleDups:
                    arr[length_] = 0
                    length_ -= 1
                    break
                possibleDups += 1

        last = length_ - possibleDups

        for i in range(last, -1, -1):
            if arr[i] == 0:
                arr[i + possibleDups] = 0
                possibleDups -= 1
                arr[i + possibleDups] = 0
            else:
                arr[i + possibleDups] = arr[i]

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

Задача: 1125. Smallest Sufficient Team
Сложность: hard

В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.

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

Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.

Гарантируется, что ответ существует.

Пример:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],["algorithms","math","reactjs"],
["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

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

1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.

2⃣Динамическое программирование (DP):
Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1.
Установите dp[0] в 0 (базовый случай).
Для каждого skillsMask от 1 до 2^m - 1:
- для каждого человека i:
- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].
- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).

3⃣Формирование ответа:
Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду.

😎 Решение:

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(people)
        m = len(req_skills)
        skillId = {skill: i for i, skill in enumerate(req_skills)}
        skillsMaskOfPerson = [0] * n
        for i in range(n):
            for skill in people[i]:
                if skill in skillId:
                    skillsMaskOfPerson[i] |= 1 << skillId[skill]
        
        dp = [(1 << n) - 1] * (1 << m)
        dp[0] = 0
        for skillsMask in range(1, 1 << m):
            for i in range(n):
                smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i]
                if smallerSkillsMask != skillsMask:
                    peopleMask = dp[smallerSkillsMask] | (1 << i)
                    if bin(peopleMask).count('1') < bin(dp[skillsMask]).count('1'):
                        dp[skillsMask] = peopleMask
        
        answerMask = dp[(1 << m) - 1]
        return [i for i in range(n) if (answerMask >> i) & 1]

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

Задача: 1016. Binary String With Substrings Representing 1 To N
Сложность: medium

Если задана двоичная строка s и положительное целое число n, верните true, если двоичное представление всех целых чисел в диапазоне [1, n] является подстрокой s, или false в противном случае. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "0110", n = 3
Output: true

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

1⃣Генерация двоичных строк:
Для каждого числа в диапазоне [1, n] сгенерируйте его двоичное представление.

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

3⃣Возврат результата:
Если все двоичные представления являются подстроками строки s, верните true. В противном случае, верните false.

😎 Решение:

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        for i in range(1, n + 1):
            if bin(i)[2:] not in s:
                return false
        return true

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

Задача: 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:
    def countOrders(self, n: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1):
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD
        
        return dp[n]

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

Задача: 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:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        base = 0

        while base < n:
            end = base
            if end + 1 < n and arr[end] < arr[end + 1]:
                while end + 1 < n and arr[end] < arr[end + 1]:
                    end += 1
                if end + 1 < n and arr[end] > arr[end + 1]:
                    while end + 1 < n and arr[end] > arr[end + 1]:
                        end += 1
                    ans = max(ans, end - base + 1)
            base = max(end, base + 1)

        return ans

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

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

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

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

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        to_delete_set = set(to_delete)
        forest = []

        def process_node(node):
            if not node:
                return None

            node.left = process_node(node.left)
            node.right = process_node(node.right)

            if node.val in to_delete_set:
                if node.left:
                    forest.append(node.left)
                if node.right:
                    forest.append(node.right)
                return None
            return node

        root = process_node(root)
        if root:
            forest.append(root)

        return forest

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

Задача: 991. Broken Calculator
Сложность: medium

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

Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.

Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.

2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.

3⃣Возврат результата:
Возвращайте суммарное количество выполненных операций.

😎 Решение:

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        operations = 0
        
        while target > startValue:
            operations += 1
            if target % 2 == 0:
                target //= 2
            else:
                target += 1
                
        return operations + (startValue - target)

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

Задача: 263. Ugly Number
Сложность: easy

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.

Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3️⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        for factor in [2, 3, 5]:
            n = self.keepDividingWhenDivisible(n, factor)
        return n == 1

    def keepDividingWhenDivisible(self, dividend: int, divisor: int) -> int:
        while dividend % divisor == 0:
            dividend //= divisor
        return dividend

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        seen = set()
        n = min(n, 6)
        shift = max(0, 6 - n)
        for cand in range(16):
            bcount = bin(cand).count('1')
            if bcount % 2 == m % 2 and bcount <= m:
                lights = 0
                if ((cand >> 0) & 1) > 0: lights ^= 0b111111 >> shift
                if ((cand >> 1) & 1) > 0: lights ^= 0b010101 >> shift
                if ((cand >> 2) & 1) > 0: lights ^= 0b101010 >> shift
                if ((cand >> 3) & 1) > 0: lights ^= 0b100100 >> shift
                seen.add(lights)
        return len(seen)

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

Задача: 71. Simplify Path
Сложность: medium

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

В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов.

Упрощенный канонический путь должен соответствовать следующим правилам:

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

Пример:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

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

1️⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их.

2️⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст.

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

😎 Решение:

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for portion in path.split("/"):
            if portion == "..":
                if stack:
                    stack.pop()
            elif portion == "." or not portion:
                continue
            else:
                stack.append(portion)
        
        final_str = "/" + "/".join(stack)
        return final_str

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

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

Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.

Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

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

1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎 Решение:

class SnapshotArray:
    def __init__(self, length: int):
        self.snapId = 0
        self.historyRecords = [{0: 0} for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.historyRecords[index][self.snapId] = val

    def snap(self) -> int:
        self.snapId += 1
        return self.snapId - 1

    def get(self, index: int, snapId: int) -> int:
        record = self.historyRecords[index]
        while snapId >= 0:
            if snapId in record:
                return record[snapId]
            snapId -= 1
        return 0

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