Python | LeetCode

Задача: 999. Available Captures for Rook Сложность: easy Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья. Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

👨‍💻 Алгоритм: 1⃣Поиск ладьи: Найдите координаты белой ладьи "R" на шахматной доске. 2⃣Проверка направлений атаки: Проверьте все четыре направления (влево, вправо, вверх, вниз) от позиции ладьи. Перемещайтесь по каждому направлению до тех пор, пока не встретите другую фигуру или край доски. 3⃣Подсчет атакованных пешек: Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек. Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении. 😎 Решение:

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        def count_pawns(x, y, dx, dy):
            while 0 <= x < 8 and 0 <= y < 8:
                if board[x][y] == 'B':
                    break
                if board[x][y] == 'p':
                    return 1
                x, y = x + dx, y + dy
            return 0

        for i in range(8):
            for j in range(8):
                if board[i][j] == 'R':
                    return (count_pawns(i, j, -1, 0) + count_pawns(i, j, 1, 0) +
                            count_pawns(i, j, 0, -1) + count_pawns(i, j, 0, 1))
        return 0

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 995. Minimum Number of K Consecutive Bit Flips Сложность: hard Дан бинарный массив nums и целое число k. Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0. Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1. Подмассив - это непрерывная часть массива. Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip = 0
        flips = 0
        flip_queue = [0] * n
        
        for i in range(n):
            if i >= k:
                flip ^= flip_queue[i - k]
            if nums[i] == flip:
                if i + k > n:
                    return -1
                flips += 1
                flip ^= 1
                flip_queue[i] = 1
        
        return flips

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

Бесплатное льготное обучение: 3 месяца Мы ищем людей, которые хотят работать в IT-сфере из дома 💰 Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку: Узнать больше #реклама technolium.ru О рекламодателе

Задача: 190. Reverse Bits Сложность: easy Переверните биты заданного 32-битного беззнакового целого числа. Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

👨‍💻 Алгоритм: 1️⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа. 2️⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции. 3️⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений. 😎 Решение:

import functools
class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 24
        while n:
            ret += self.reverseByte(n & 0xFF) << power
            n = n >> 8
            power -= 8
        return ret
    @functools.lru_cache(maxsize=256)
    def reverseByte(self, byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023

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

⚡️ Python теперь в Telegram! Ребята сделали крутейший канал, где на простых картинках и понятном языке обучают Python, делятся полезными фишками и инструментами Подписывайтесь: @PythonPortal

Такого ещё не было - Битрикс24 со скидкой 30% на год - Плюс бонус 100 000 рублей на ИИ-помощника ✨Автоматизируйте задачи, не теряйте клиентов и экономьте деньги. Выгодно? — Да. Надо брать? — Однозначно. 🏃‍♂️Успей Акция действует до 30 апреля при покупке лицензии Битрикс24 на 12 месяцев, AI-помощник предоставляется за 1 ₽. Правила акции на сайте по ссылке: Узнать больше #реклама 16+ ai-sale.bitrix24.ru О рекламодателе

Задача: 171. Excel Sheet Column Number Сложность: easy Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца. Пример:

Input: columnTitle = "A"
Output: 1

👨‍💻 Алгоритм: 1️⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1). 2️⃣Инициализируйте переменную-аккумулятор result. 3️⃣Начиная справа налево, вычислите значение символа в зависимости от его позиции и добавьте его к result. 😎 Решение:

class Solution:
    def titleToNumber(self, s: str) -> int:
        result = 0

        alpha_map = {chr(i + 65): i + 1 for i in range(26)}

        n = len(s)
        for i in range(n):
            cur_char = s[n - 1 - i]
            result += alpha_map[cur_char] * (26**i)
        return result

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

Стать бэкендером в Яндексе за несколько дней 12–17 апреля устраиваем Week Offer Backend: за несколько дней можно пройти технические секции и попасть в Яндекс. Для этого нужно зарегистрироваться и решить несколько задач в Контесте. Ищем классных бэкенд-разработчиков с опытом работы от 3 лет на C++, Python, Java/Kotlin или Go, готовых работать в офисном или гибридном режиме в России. Вы сможете выбрать одну из команд: Яндекс Пэй, Яндекс ID, Яндекс Плюс, Яндекс Сплит, Яндекс Сейвы, Яндекс 360. Можно пообщаться с нанимающими менеджерами и выбрать самый интересный проект. Если всё пройдёт хорошо, сразу же получите офер. Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 969. Pancake Sorting Сложность: medium Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов. При одном перевороте блина мы выполняем следующие шаги: Выбираем целое число k, где 1 <= k <= arr.length. Переворачиваем подмассив arr[0...k-1] (индексация с 0). Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3. Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным. Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

👨‍💻 Алгоритм: 1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0 ] (в Python). 2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего. 3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте. 😎 Решение:

class Solution:
    def pancakeSort(self, A):
        ans = []

        for value_to_sort in range(len(A), 0, -1):
            index = self.find(A, value_to_sort)
            if index == value_to_sort - 1:
                continue
            if index != 0:
                ans.append(index + 1)
                self.flip(A, index + 1)
            ans.append(value_to_sort)
            self.flip(A, value_to_sort)

        return ans

    def flip(self, sublist, k):
        sublist[:k] = sublist[:k][::-1]

    def find(self, a, target):
        for i, num in enumerate(a):
            if num == target:
                return i
        return -1

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

Ошибки в защите данных: как СУБД Jatoba избегает их? Дата: 17 апреля (четверг) Время: 12:00 - 13:30 МСК Не пропустите вебинар «Кластерные решения для больших объемов данных: отечественный опыт» Эксперты УЦСБ и «Газинформсервис» расскажут, как избежать ошибок в настройке СУБД, повысить доступность данных и защитить их от утечек, даже при пиковых нагрузках. 1. Как Jatoba обеспечивает высокую доступность данных при максимальных нагрузках? 2. Почему стоит выбрать отечественную СУБД для хранения и защиты данных? 3. Реальные примеры успешных внедрений в крупных компаниях. 4. Демонстрация интерфейса и отказоустойчивости Jatoba DB в действии! Бонус: фирменный мерч от «Газинформсервис» за самый интересный вопрос! Зарегистрироваться #реклама 16+ sec.ussc.ru О рекламодателе

Задача: 974. Subarray Sums Divisible by K Сложность: medium Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1. 2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений. 3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k. 😎 Решение:

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefixMod = 0
        result = 0
        modGroups = [0] * k
        modGroups[0] = 1

        for num in nums:
            prefixMod = (prefixMod + num % k + k) % k
            result += modGroups[prefixMod]
            modGroups[prefixMod] += 1

        return result

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

На обучение в IT-компанию на удаленку требуются стажеры! ⚡ Для тестирования программ и приложений. (Можно без опыта, всему научим) С нас обучение, с вас — пару свободных часов в день. Наша цель — предоставить IT-компаниям качественных специалистов в сфере тестирования приложений и программ. 👌 Вы подходите, если любите работать и зарабатывать! Можно совмещать с основной работой или декретным отпуском. Сперва проведу бесплатный вводный урок, на котором расскажу: — об основах тестирования; — о поиске клиентов; — как пройти стажировку и устроиться в топовую IT-компанию. ✅ Что будет требоваться от вас: — проверять программы или приложения; — находить в них ошибки; — зарабатывать. 💰 За свою работу можно зарабатывать от 70 000 рублей. 👍 Для регистрации жмите кнопку "Зарегистрироваться" Зарегистрироваться #реклама 16+ site.purrweb-academy.ru О рекламодателе

Задача: 834. Sum of Distances in Tree Сложность: hard Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами. Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве. Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами. Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        import collections
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        ans = [0] * N
        count = [1] * N

        def dfs(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    dfs(neighbor, node)
                    count[node] += count[neighbor]
                    ans[node] += ans[neighbor] + count[neighbor]

        def dfs2(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    ans[neighbor] = ans[node] - count[neighbor] + N - count[neighbor]
                    dfs2(neighbor, node)

        dfs()
        dfs2()

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

Ты уже начал изучать IT, но чувствуешь, что сам не вывезешь? Нужно больше практики, системности и поддержки? 🔥Приходи на бесплатный интенсив "Первые шаги в Python: начни свой путь в IT" 🔥 8, 9 и 10 апреля | Онлайн За 3 дня ты: ✅ поймёшь, как устроена профессия backend-разработчика; ✅ изучишь основы Python и напишешь свою первую программу прямо в Google Colab; ✅ разберёшься, какие шаги реально приведут тебя в IT; ✅ получишь поддержку и ответы на свои вопросы от опытного наставника. Интенсив проведёт Сергей Смелков — backend-разработчик с 5-летним опытом, преподаватель и ментор, который помогает новичкам уверенно войти в профессию. Сергей объясняет сложные темы простым языком, помогает не запутаться в старте и уже на первых шагах почувствовать себя уверенно. Если хочешь перестать блуждать в потёмках и получить чёткое направление — начни с этих трёх дней. ❗️Это бесплатно, понятно и под силу каждому. 🎯Регистрируйся сейчас — старт 8 апреля👇 https://salebot.site/md/smelkov_stutyit

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: №21. Merge Two Sorted Lists Сложность: easy Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка. Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]  

👨‍💻 Алгоритм: 1️⃣Создать фиктивный узел для упрощения слияния. 2️⃣Использовать указатель для поочередного добавления наименьшего элемента из двух списков. 3️⃣Добавить оставшиеся элементы и вернуть заголовок объединенного списка. 😎 Решение:

class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        
        cur.next = l1 or l2
        return dummy.next

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1244. Design A Leaderboard Сложность: medium Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста. Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

👨‍💻 Алгоритм: 1⃣addScore(playerId, score): Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение. Если игрок не существует, добавляем его с заданным счетом. 2⃣top(K): Сортируем игроков по их счету в порядке убывания. Возвращаем сумму очков K лучших игроков. 3⃣reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

from collections import defaultdict

class Leaderboard:

    def __init__(self):
        self.scores = defaultdict(int)

    def addScore(self, playerId, score):
        self.scores[playerId] += score

    def top(self, K):
        return sum(sorted(self.scores.values(), reverse=True)[:K])

    def reset(self, playerId):
        self.scores[playerId] = 0

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

Крупнейший университет искусственного интеллекта Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе