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

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