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

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

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

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