Python | LeetCode

Вебинар — увеличение прибыли для строительных компаний! Покажем на реальных кейсах, как убрать кассовые разрывы и увеличить прибыль с проекта на 300 000 ₽ Вы узнаете на встрече, как: - Исключить ошибки в сметах и ускорить расчеты - Закрывать кассовые разрывы и навести порядок в финансах - Перейти от excel таблиц к удобному инструменту для всей команды - Экономить до 15-20% на закупках - Контролировать стройку и бюджет в реальном времени Узнать больше #реклама 16+ gectaro.com О рекламодателе

Задача: 278. First Bad Version Сложность: easy Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими. Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими. Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API. Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

👨‍💻 Алгоритм: 1⃣Инициализация границ поиска: Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n. 2⃣Бинарный поиск: Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid). Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1. 3⃣Возврат результата: Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии. 😎 Решение:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

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

В Битрикс24 теперь можно сделать сайт за 30 секунд Серьёзно. Пишешь, что нужно, и AI сам всё собирает: тексты, картинки, оформление. ✨Никакой магии, просто умный помощник. Попробуйте — закайфуете от скорости! Попробовать #реклама 16+ sites-24.bitrix24.ru О рекламодателе

Задача: 1434. Number of Ways to Wear Different Hats to Each Other Сложность: hard Дано n человек и 40 видов шляп, пронумерованных от 1 до 40. Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком. Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга. Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7. Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

👨‍💻 Алгоритм: 1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей. 2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп. 3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп. 😎 Решение:

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        MOD = 1000000007
        n = len(hats)
        hatsToPeople = {}
        for i, hatList in enumerate(hats):
            for hat in hatList:
                if hat not in hatsToPeople:
                    hatsToPeople[hat] = []
                hatsToPeople[hat].append(i)
                
        done = (1 << n) - 1
        memo = [[-1] * done for _ in range(41)]

        def dp(hat, mask):
            if mask == done:
                return 1
            if hat > 40:
                return 0
            if memo[hat][mask] != -1:
                return memo[hat][mask]
            
            ans = dp(hat + 1, mask)
            if hat in hatsToPeople:
                for person in hatsToPeople[hat]:
                    if (mask & (1 << person)) == 0:
                        ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD
            
            memo[hat][mask] = ans
            return ans

        return dp(1, 0)

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

Задача: 1522. Diameter of N-Ary Tree Сложность: medium Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева. Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень. (Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.) Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

👨‍💻 Алгоритм: 1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один. 2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева. 3⃣Существует два подхода для выбора двух наибольших высот: — Первый способ заключается в хранении высот всех дочерних узлов в массиве, последующей сортировке массива и выборе двух наибольших элементов. — Второй способ использует две переменные, которые отслеживают текущие два наибольших значения. Во время итерации по всем высотам эти переменные обновляются соответствующим образом. 😎 Решение:

class Solution:
    def __init__(self):
        self.diameter = 0

    def height(self, node):
        if not node.children:
            return 0

        maxHeight1, maxHeight2 = 0, 0
        for child in node.children:
            parentHeight = self.height(child) + 1
            if parentHeight > maxHeight1:
                maxHeight2 = maxHeight1
                maxHeight1 = parentHeight
            elif parentHeight > maxHeight2:
                maxHeight2 = parentHeight
            distance = maxHeight1 + maxHeight2
            self.diameter = max(self.diameter, distance)
        return maxHeight1

    def diameter(self, root):
        self.diameter = 0
        self.height(root)
        return self.diameter

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

Задача: 443. String Compression Сложность: medium Дан массив символов chars, сжать его, используя следующий алгоритм: Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars: Если длина группы равна 1, добавьте символ к строке s. В противном случае добавьте символ, а за ним длину группы. Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars. После того как вы закончите модификацию входного массива, верните новую длину массива. Вы должны написать алгоритм, который использует только постоянное дополнительное пространство. Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

👨‍💻 Алгоритм: 1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0. 2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе. 3⃣Верните res. 😎 Решение:

class Solution:
    def compress(self, chars: List[str]) -> int:
        i = 0
        res = 0
        while i < len(chars):
            group_length = 1
            while (i + group_length < len(chars) and chars[i + group_length] == chars[i]):
                group_length += 1
            chars[res] = chars[i]
            res += 1
            if group_length > 1:
                str_repr = str(group_length)
                chars[res:res+len(str_repr)] = list(str_repr)
                res += len(str_repr)
            i += group_length
        return res

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

Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:

class Solution:
    def depthFirstSearch(self, n: int, k: int, rootVal: int) -> int:
        if n == 1:
            return rootVal
        totalNodes = 2 ** (n - 1)
        if k > totalNodes / 2:
            nextRootVal = 1 if rootVal == 0 else 0
            return self.depthFirstSearch(n - 1, k - (totalNodes / 2), nextRootVal)
        else:
            nextRootVal = 0 if rootVal == 0 else 1
            return self.depthFirstSearch(n - 1, k, nextRootVal)

    def kthGrammar(self, n: int, k: int) -> int:
        return self.depthFirstSearch(n, k, 0)

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60 Сложность: medium Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0. Пример:

Input: time = [30,20,150,100,40]
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализация и вычисление остатков: Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями. 2⃣Подсчет пар: Пройдитесь по каждой песне в списке и для каждого элемента: Вычислите остаток от деления времени песни на 60. Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0). Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0). Обновите массив остатков, увеличивая количество песен с текущим остатком на 1. 3⃣Возврат результата: Верните общее количество пар. 😎 Решение:

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        remainders = [0] * 60
        count = 0
        
        for t in time:
            if t % 60 == 0:
                count += remainders[0]
            else:
                count += remainders[60 - t % 60]
            remainders[t % 60] += 1
        
        return count

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

Задача: 931. Minimum Falling Path Sum Сложность: medium Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1). Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

👨‍💻 Алгоритм: 1⃣Использовать динамическое программирование для хранения минимальных сумм падающих путей для каждой позиции. 2⃣Инициализировать dp массив копией первой строки исходной матрицы. Пройти по каждой строке, обновляя dp массив на основе значений из предыдущей строки. 3⃣Вернуть минимальное значение в последней строке dp массива. 😎 Решение:

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]
    
    for i in range(1, n):
        new_dp = [0] * n
        for j in range(n):
            new_dp[j] = matrix[i][j] + min(dp[j], dp[j-1] if j > 0 else float('inf'), dp[j+1] if j < n - 1 else float('inf'))
        dp = new_dp
    
    return min(dp)

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

Новая фича на easyoffer – Автоотлики Вы автоматически откликаетесь на подходящие вам вакансии. Попробуйте её бесплатно и начните получать больше предложений о работе. 🚀 Запуск занимаем всего 3 минуты, а экономит очень много времени 🛡 Это безопасно: easyoffer официально одобрен HeadHunter и прошел его модерацию. 🥷🏻 Автоотклик незаметен для рекртера. Автоотклик ничем не отличается от обычного отклика, который вы делаете вручную Рекрутеры давно используют автоматизацию для поиска кандидатов. Так почему вы должны откликаться вручную? 💡Совет – Добавьте шаблон сопроводительного письма, чтобы откликаться на большее количество вакансий (на некоторые вакансии нельзя откликнуться без сопроводительного) Попробовать бесплатно → https://easyoffer.ru/autoapply

Задача: 482. License Key Formatting Сложность: easy Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k. Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные. Верните переформатированный лицензионный ключ. Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

👨‍💻 Алгоритм: 1⃣Инициализация Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата. 2⃣Итерация по входной строке в обратном порядке Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count. 3⃣Завершение Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её. 😎 Решение:

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        count = 0
        ans = []

        for char in reversed(s):
            if char != '-':
                ans.append(char.upper())
                count += 1
                if count == k:
                    ans.append('-')
                    count = 0
        
        if ans and ans[-1] == '-':
            ans.pop()

        return ''.join(reversed(ans))

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

Задача: 1000. Minimum Cost to Merge Stones Сложность: hard Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1. Пример:

Input: stones = [3,2,4,1], k = 2
Output: 20

👨‍💻 Алгоритм: 1⃣Проверка на возможность объединения: Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1. 2⃣Инициализация и динамическое программирование: Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней. Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве. 3⃣Заполнение таблицы dp: Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование. Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения. 😎 Решение:

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        dp = [[0] * n for _ in range(n)]
        for m in range(k, n + 1):
            for i in range(n - m + 1):
                j = i + m - 1
                dp[i][j] = min(dp[i][t] + dp[t + 1][j] for t in range(i, j, k - 1))
                if (j - i) % (k - 1) == 0:
                    dp[i][j] += prefix[j + 1] - prefix[i]

        return dp[0][n - 1]

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

Задача: 1165. Single-Row Keyboard Сложность: easy Есть специальная клавиатура, на которой все клавиши расположены в один ряд. Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|. Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем. Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

👨‍💻 Алгоритм: 1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0. 2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c. 3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова. 😎 Решение:

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        key_indices = [-1] * 26
        for i, c in enumerate(keyboard):
            key_indices[ord(c) - ord('a')] = i
        
        prev = 0
        result = 0
        
        for c in word:
            index = key_indices[ord(c) - ord('a')]
            result += abs(prev - index)
            prev = index
        
        return result

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

Задача: 924. Minimize Malware Spread Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО. Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

👨‍💻 Алгоритм: 1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial. 2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом. 😎 Решение:

def minMalwareSpread(graph, initial):
    def dfs(node, infected):
        for neighbor in range(len(graph)):
            if graph[node][neighbor] == 1 and neighbor not in infected:
                infected.add(neighbor)
                dfs(neighbor, infected)

    n = len(graph)
    initial_set = set(initial)
    initial.sort()
    min_infected = float('inf')
    best_node = initial[0]
    
    for node in initial:
        infected = set(initial_set)
        infected.remove(node)
        for i in initial_set:
            if i != node:
                dfs(i, infected)
        if len(infected) < min_infected:
            min_infected = len(infected)
            best_node = node
    
    return best_node

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

Задача: 617. Merge Two Binary Trees Сложность: medium Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев. Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

👨‍💻 Алгоритм: 1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null. 2⃣Если оба узла не пустые, создаем новый узел, значение которого равно сумме значений двух узлов. Рекурсивно объединяем левые и правые поддеревья. 3⃣Возвращаем новый узел, который является корнем объединенного дерева. 😎 Решение:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    
    mergedNode = TreeNode(root1.val + root2.val)
    mergedNode.left = mergeTrees(root1.left, root2.left)
    mergedNode.right = mergeTrees(root1.right, root2.right)
    
    return mergedNode

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

Изиоффер переходит в публичное бета-тестирование! 🎉 Что нового: 🟢Анализ IT собеседований на основе 4500+ реальных интервью 🟢Вопросы из собеседований с вероятностью встречи 🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов 🟢Пример лучшего ответа 🟢Задачи из собеседований 🟢Тестовые задания 🟢Примеры собеседований 🟢Фильтрация всего контента по грейдам, компаниям 🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек 🟢Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро) 🟢Автоотклики на HeadHunter 🟢Закрытое сообщество easyoffer 💎 Акция в честь открытия для первых 500 покупателей: 🚀 Скидка 50% на PRO тариф на 1 год 🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 1406. Stone Game III Сложность: hard Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue. Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду. Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0. Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты. Предположим, что Алиса и Боб играют оптимально. Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом. Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0. 2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре. 3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья. 😎 Решение:

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            dp[i] = stoneValue[i] - dp[i + 1]
            if i + 2 <= n:
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
            if i + 3 <= n:
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
        if dp[0] > 0:
            return "Alice"
        elif dp[0] < 0:
            return "Bob"
        else:
            return "Tie"

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 1161. Maximum Level Sum of a Binary Tree Сложность: medium Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее. Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна. Пример:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

👨‍💻 Алгоритм: 1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень. 2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1. 3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans. 😎 Решение:

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        maxSum = float('-inf')
        ans = 0
        level = 0
        q = deque([root])
        
        while q:
            level += 1
            sumAtCurrentLevel = 0
            for _ in range(len(q)):
                node = q.popleft()
                sumAtCurrentLevel += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            if maxSum < sumAtCurrentLevel:
                maxSum = sumAtCurrentLevel
                ans = level
        
        return ans

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!