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

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

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

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

1⃣Инициализируйте переменные для отслеживания текущего основания и максимальной длины горного массива.

2⃣Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива.

3⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.

😎 Решение:

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        base = 0

        while base < n:
            end = base
            if end + 1 < n and arr[end] < arr[end + 1]:
                while end + 1 < n and arr[end] < arr[end + 1]:
                    end += 1
                if end + 1 < n and arr[end] > arr[end + 1]:
                    while end + 1 < n and arr[end] > arr[end + 1]:
                        end += 1
                    ans = max(ans, end - base + 1)
            base = max(end, base + 1)

        return ans

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке.

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        to_delete_set = set(to_delete)
        forest = []

        def process_node(node):
            if not node:
                return None

            node.left = process_node(node.left)
            node.right = process_node(node.right)

            if node.val in to_delete_set:
                if node.left:
                    forest.append(node.left)
                if node.right:
                    forest.append(node.right)
                return None
            return node

        root = process_node(root)
        if root:
            forest.append(root)

        return forest

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

Задача: 991. Broken Calculator
Сложность: medium

Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:

Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.

Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.

2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.

3⃣Возврат результата:
Возвращайте суммарное количество выполненных операций.

😎 Решение:

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        operations = 0
        
        while target > startValue:
            operations += 1
            if target % 2 == 0:
                target //= 2
            else:
                target += 1
                
        return operations + (startValue - target)

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

Задача: 263. Ugly Number
Сложность: easy

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.

Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3️⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        for factor in [2, 3, 5]:
            n = self.keepDividingWhenDivisible(n, factor)
        return n == 1

    def keepDividingWhenDivisible(self, dividend: int, divisor: int) -> int:
        while dividend % divisor == 0:
            dividend //= divisor
        return dividend

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        seen = set()
        n = min(n, 6)
        shift = max(0, 6 - n)
        for cand in range(16):
            bcount = bin(cand).count('1')
            if bcount % 2 == m % 2 and bcount <= m:
                lights = 0
                if ((cand >> 0) & 1) > 0: lights ^= 0b111111 >> shift
                if ((cand >> 1) & 1) > 0: lights ^= 0b010101 >> shift
                if ((cand >> 2) & 1) > 0: lights ^= 0b101010 >> shift
                if ((cand >> 3) & 1) > 0: lights ^= 0b100100 >> shift
                seen.add(lights)
        return len(seen)

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

Задача: 71. Simplify Path
Сложность: medium

Дан абсолютный путь для файловой системы в стиле Unix, который начинается с символа '/'. Преобразуйте этот путь в его упрощенный канонический путь.

В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов.

Упрощенный канонический путь должен соответствовать следующим правилам:

Он должен начинаться с одного слэша '/'.
Каталоги в пути должны быть разделены только одним слэшем '/'.
Он не должен заканчиваться слэшем '/', если только это не корневой каталог.
Он должен исключать любые одинарные или двойные точки, используемые для обозначения текущих или родительских каталогов.
Верните новый путь.

Пример:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

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

1️⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их.

2️⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст.

3️⃣Наконец, если обрабатываемый нами в данный момент компонент не является одним из специальных символов, мы просто добавляем его в наш стек, так как это законное имя каталога. Как только все компоненты обработаны, нам просто нужно соединить все имена каталогов в нашем стеке, используя '/' в качестве разделителя, и мы получим самый короткий путь, который приведет нас в тот же каталог, что и предоставленный на входе.

😎 Решение:

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for portion in path.split("/"):
            if portion == "..":
                if stack:
                    stack.pop()
            elif portion == "." or not portion:
                continue
            else:
                stack.append(portion)
        
        final_str = "/" + "/".join(stack)
        return final_str

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

Задача: 1146. Snapshot Array
Сложность: medium

Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.

Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

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

1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎 Решение:

class SnapshotArray:
    def __init__(self, length: int):
        self.snapId = 0
        self.historyRecords = [{0: 0} for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.historyRecords[index][self.snapId] = val

    def snap(self) -> int:
        self.snapId += 1
        return self.snapId - 1

    def get(self, index: int, snapId: int) -> int:
        record = self.historyRecords[index]
        while snapId >= 0:
            if snapId in record:
                return record[snapId]
            snapId -= 1
        return 0

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

Задача: 761. Special Binary String
Сложность: hard

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

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

1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

def makeLargestSpecial(s):
    count = i = 0
    substrs = []
    for j, char in enumerate(s):
        count += 1 if char == '1' else -1
        if count == 0:
            substrs.append('1' + makeLargestSpecial(s[i + 1:j]) + '0')
            i = j + 1

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

Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium

Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.

Если общего элемента нет, верните -1.

Пример:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

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

1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.

2⃣Итерация по строкам матрицы:
Для каждой строки:
- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.
- если достигли конца строки, возвращайте -1.
- если значение равно текущему максимуму, увеличивайте счетчик.
- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.

3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.

😎 Решение:

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        pos = [0] * n
        cur_max = 0
        cnt = 0
        
        while True:
            for i in range(n):
                while pos[i] < m and mat[i][pos[i]] < cur_max:
                    pos[i] += 1
                if pos[i] >= m:
                    return -1
                if mat[i][pos[i]] != cur_max:
                    cnt = 1
                    cur_max = mat[i][pos[i]]
                else:
                    cnt += 1
                    if cnt == n:
                        return cur_max

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

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

Задача: 646. Maximum Length of Pair Chain
Сложность: medium

Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример:

Input: nums = [1,2,2,4]
Output: [2,3]

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

1⃣Отсортируйте пары по второму элементу каждой пары (righti).

2⃣Используйте динамическое программирование или жадный алгоритм, чтобы построить цепочку максимальной длин

3⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки.

😎 Решение:

def findLongestChain(pairs):
    pairs.sort(key=lambda x: x[1])
    current_end = float('-inf')
    count = 0
    for pair in pairs:
        if current_end < pair[0]:
            current_end = pair[1]
            count += 1
    return count

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

Задача: 224. Basic Calculator
Сложность: hard

Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.

Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

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

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

class Solution:
    def evaluate_expr(self, stack):
        if not stack or type(stack[-1]) == str:
            stack.append(0)
            
        res = stack.pop()

        while stack and stack[-1] != ')':
            sign = stack.pop()
            if sign == '+':
                res += stack.pop()
            else:
                res -= stack.pop()
        return res       

    def calculate(self, s: str) -> int:
        stack = []
        n, operand = 0, 0

        for i in range(len(s) - 1, -1, -1):
            ch = s[i]

            if ch.isdigit():
                operand = (10**n * int(ch)) + operand
                n += 1

            elif ch != " ":
                if n:
                    stack.append(operand)
                    n, operand = 0, 0

                if ch == '(':         
                    res = self.evaluate_expr(stack)
                    stack.pop()        

                    stack.append(res)

                else:
                    stack.append(ch)

        if n:
            stack.append(operand)

        return self.evaluate_expr(stack)

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

Задача: 1017. Convert to Base -2
Сложность: medium

Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".

Пример:

Input: n = 2
Output: "110"

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

1⃣Инициализация переменных:
Создайте пустую строку для хранения двоичного представления числа.
Используйте цикл для вычисления каждой цифры числа в базе -2.

2⃣Вычисление цифр:
В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2.
Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1.
Добавляйте остаток в начало строки.

3⃣Возврат результата:
Верните строку, представляющую число в базе -2. Если строка пустая, верните "0".

😎 Решение:

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        res = ""
        while n != 0:
            n, remainder = divmod(n, -2)
            if remainder < 0:
                remainder += 2
                n += 1
            res = str(remainder) + res
        return res

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

Задача: 604. Design Compressed String Iterator
Сложность: easy

Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.

Реализуйте класс StringIterator:

- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.

Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

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

1⃣Предварительная обработка
Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

2⃣Операция next()
Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

3⃣Операция hasNext()
Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎 Решение:

class StringIterator:
    def __init__(self, s: str):
        self.res = []
        self.ptr = 0
        i = 0
        while i < len(s):
            ch = s[i]
            i += 1
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            self.res.extend([ch] * num)

    def next(self) -> str:
        if not self.hasNext():
            return ' '
        char = self.res[self.ptr]
        self.ptr += 1
        return char

    def hasNext(self) -> bool:
        return self.ptr < len(self.res)

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

Задача: 290. Word Pattern
Сложность: easy

Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону.

Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s.

Пример:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

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

1⃣Разделение строки на слова:
Разделите строку s на отдельные слова.
Если количество слов не равно длине шаблона, возвращаем false.

2⃣Создание отображений:
Создайте два словаря: один для отображения букв шаблона на слова, другой для слов на буквы шаблона.

3⃣Проверка биекции:
Пройдите по каждому символу шаблона и соответствующему слову.
Если символ уже в словаре и не соответствует текущему слову или слово уже в словаре и не соответствует текущему символу, возвращаем false.
Иначе добавляем символ и слово в словари и продолжаем проверку. Если все проверки пройдены, возвращаем true.

😎 Решение:

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        map_char = {}
        map_word = {}
        words = s.split()

        if len(words) != len(pattern):
            return False

        for c, w in zip(pattern, words):
            if c not in map_char:
                if w in map_word:
                    return False
                else:
                    map_char[c] = w
                    map_word[w] = c
            else:
                if map_char[c] != w:
                    return False

        return True

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