Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium

Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.

Пример:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

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

2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:

Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).
Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.

3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.

😎 Решение:

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        answer = 0
        while a != 0 or b != 0 or c != 0:
            if (c & 1) == 1:
                if (a & 1) == 0 and (b & 1) == 0:
                    answer += 1
            else:
                answer += (a & 1) + (b & 1)
            a >>= 1
            b >>= 1
            c >>= 1
        return answer

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

Задача: 75. Sort Colors
Сложность: medium

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

Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.

Вы должны решить эту задачу без использования функции сортировки библиотеки.

Пример:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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

1️⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0.

2️⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2.

3️⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0.
Пока curr <= p2:
Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо.
Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево.
Если nums[curr] = 1: сдвинуть указатель curr вправо.

😎 Решение:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = curr = 0
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

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

Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

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

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎 Решение:

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        adj = defaultdict(list)
        for a, b in pairs:
            adj[a].append(b)
            adj[b].append(a)
        
        visited = [False] * len(s)
        s = list(s)
        
        def dfs(node, indices, chars):
            visited[node] = True
            indices.append(node)
            chars.append(s[node])
            for neighbor in adj[node]:
                if not visited[neighbor]:
                    dfs(neighbor, indices, chars)
        
        for i in range(len(s)):
            if not visited[i]:
                indices = []
                chars = []
                dfs(i, indices, chars)
                indices.sort()
                chars.sort()
                for index, char in zip(indices, chars):
                    s[index] = char
        
        return ''.join(s)

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

Задача: 401. Binary Watch
Сложность: easy

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

1⃣Генерация всех возможных комбинаций:
Переберите все возможные значения для часов и минут.
Используйте битовые операции для подсчета количества единиц в бинарном представлении числа.

2⃣Проверка количества горящих светодиодов:
Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов.

3⃣Форматирование результата:
Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎 Решение:

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        results = []
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    results.append(f"{h}:{m:02d}")
        return results

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

Задача: 678. Valid Parenthesis String
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution:
    def checkValidString(self, s: str) -> bool:
        memo = [[-1] * len(s) for _ in range(len(s))]
        return self.isValidString(0, 0, s, memo)

    def isValidString(self, index: int, openCount: int, s: str, memo: list) -> bool:
        if index == len(s):
            return openCount == 0

        if memo[index][openCount] != -1:
            return memo[index][openCount] == 1

        isValid = False

        if s[index] == '*':
            isValid = self.isValidString(index + 1, openCount + 1, s, memo)
            if openCount > 0:
                isValid = isValid or self.isValidString(index + 1, openCount - 1, s, memo)
            isValid = isValid or self.isValidString(index + 1, openCount, s, memo)
        elif s[index] == '(':
            isValid = self.isValidString(index + 1, openCount + 1, s, memo)
        elif openCount > 0:
            isValid = self.isValidString(index + 1, openCount - 1, s, memo)

        memo[index][openCount] = 1 if isValid else 0
        return isValid

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