Задача: 1482. Minimum Number of Days to Make m Bouquets
Сложность: medium

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1.

Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.

3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.

😎 Решение:

class Solution:
    def getNumOfBouquets(self, bloomDay, mid, k):
        numOfBouquets = 0
        count = 0
        for day in bloomDay:
            if day <= mid:
                count += 1
            else:
                count = 0
            if count == k:
                numOfBouquets += 1
                count = 0
        return numOfBouquets

    def minDays(self, bloomDay, m, k):
        if len(bloomDay) < m * k:
            return -1
        start, end = 0, max(bloomDay)
        minDays = -1
        while start <= end:
            mid = (start + end) // 2
            if self.getNumOfBouquets(bloomDay, mid, k) >= m:
                minDays = mid
                end = mid - 1
            else:
                start = mid + 1
        return minDays

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

Задача: №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]  

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

1️⃣Используем рекурсию (DFS) для генерации всех возможных комбинаций.

2️⃣Добавляем открывающую скобку, если их количество меньше n.

3️⃣Добавляем закрывающую скобку, если их количество меньше, чем открывающих.

😎 Решение:

class Solution:
    def generateParenthesis(self, n: int):
        def dfs(left, right, s):
            if len(s) == n * 2:
                res.append(s)
                return
            
            if left < n:
                dfs(left + 1, right, s + '(')
            if right < left:
                dfs(left, right + 1, s + ')')

        res = []
        dfs(0, 0, '')
        return res

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