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

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