Python | LeetCode

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

Задача: 1182. Shortest Distance to Target Color Сложность: medium Дан массив colors, содержащий три цвета: 1, 2 и 3. Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1. Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

👨‍💻 Алгоритм: 1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы. 2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка. 3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее. 😎 Решение:

from collections import defaultdict
import bisect

class Solution:
    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        queryResults = []
        hashmap = defaultdict(list)

        for i, color in enumerate(colors):
            hashmap[color].append(i)

        for target, color in queries:
            if color not in hashmap:
                queryResults.append(-1)
                continue

            indexList = hashmap[color]
            insert = bisect.bisect_left(indexList, target)

            if insert == 0:
                queryResults.append(indexList[0] - target)
            elif insert == len(indexList):
                queryResults.append(target - indexList[-1])
            else:
                leftNearest = target - indexList[insert - 1]
                rightNearest = indexList[insert] - target
                queryResults.append(min(leftNearest, rightNearest))

        return queryResults

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

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

Задача: 686. Repeated String Match Сложность: medium Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1. Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc". Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

👨‍💻 Алгоритм: 1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)). 2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1. 3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1. 😎 Решение:

class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:
        q = 1
        S = A
        while len(S) < len(B):
            S += A
            q += 1
        if B in S:
            return q
        if B in S + A:
            return q + 1
        return -1

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

Внимание ученики 1-9 класса и их родители! С 1 июня стартует бесплатная 3-х месячная программа по углубленному изучению школьных предметов с 1 по 4 класс, с 5 по 8 класс и с 9 по 11 класс от резидента Сколково. Программа предлагает подтянуть знания по основным предметам: — Математика: 83% учеников повышают оценку до 4 или 5 за 2 месяца — Подготовиться к контрольным и ВПР — Подготовка к ОГЭ и ЕГЭ без стресса — Русский язык: средний балл ВПР 87 при общешкольном показателе 65 — Английский: 72% учащихся переходят на уровень выше за 4 месяца Для участия достаточно заполнить заявку. Жмите "Записаться" Записаться #реклама 16+ mrqz.me О рекламодателе

Задача: 1332. Remove Palindromic Subsequences Сложность: easy Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s. Верните минимальное количество шагов, чтобы сделать данную строку пустой. Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной. Строка называется палиндромом, если она читается одинаково как вперед, так и назад. Пример:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

👨‍💻 Алгоритм: 1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг. 2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот). 3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом. 😎 Решение:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        if s == s[::-1]:
            return 1
        return 2

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

Задача: 1345. Jump Game IV Сложность: hard Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива. За один шаг вы можете прыгнуть с индекса i на индекс: - i + 1, где: i + 1 < arr.length. - i - 1, где: i - 1 >= 0. - j, где: arr[i] == arr[j] и i != j. Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива. Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени. Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

👨‍💻 Алгоритм: 1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов. 2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя. 3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь. 😎 Решение:

class Solution:
    def minJumps(self, arr):
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] not in graph:
                graph[arr[i]] = []
            graph[arr[i]].append(i)

        curs = [0]
        visited = {0}
        step = 0

        while curs:
            nex = []

            for node in curs:
                if node == n - 1:
                    return step

                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                graph[arr[node]] = []

                if node + 1 < n and node + 1 not in visited:
                    visited.add(node + 1)
                    nex.append(node + 1)
                if node - 1 >= 0 and node - 1 not in visited:
                    visited.add(node - 1)
                    nex.append(node - 1)

            curs = nex
            step += 1

        return -1

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

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

Задача: 395. Longest Substring with At Least K Repeating Characters Сложность: medium Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k. Если такой подстроки не существует, верните 0. Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

👨‍💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) == 0 or k > len(s):
            return 0
        n = len(s)
        result = 0
        
        for start in range(n):
            count_map = [0] * 26
            for end in range(start, n):
                count_map[ord(s[end]) - ord('a')] += 1
                if self.is_valid(count_map, k):
                    result = max(result, end - start + 1)
        
        return result
    
    def is_valid(self, count_map, k):
        count_letters = 0
        count_at_least_k = 0
        for count in count_map:
            if count > 0:
                count_letters += 1
            if count >= k:
                count_at_least_k += 1
        return count_letters == count_at_least_k

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 353. Design Snake Game Сложность: medium Разработайте игру "Змейка", которая играется на устройстве с экраном размером height x width. Поиграйте в игру онлайн, если вы не знакомы с ней. Змейка изначально находится в верхнем левом углу (0, 0) с длиной в 1 единицу. Вам дан массив food, где food[i] = (ri, ci) представляет собой строку и столбец позиции пищи, которую змейка может съесть. Когда змейка съедает кусочек пищи, ее длина и очки игры увеличиваются на 1. Каждый кусочек пищи появляется по очереди на экране, то есть второй кусочек пищи не появится, пока змейка не съест первый кусочек пищи. Когда кусочек пищи появляется на экране, гарантируется, что он не появится на блоке, занятом змейкой. Игра заканчивается, если змейка выходит за пределы экрана (врезается в стену) или если ее голова занимает пространство, которое занимает ее тело после движения (например, змейка длиной 4 не может врезаться в себя). Реализуйте класс SnakeGame: SnakeGame(int width, int height, int[][] food) Инициализирует объект с экраном размером height x width и позициями пищи. int move(String direction) Возвращает счет игры после применения одного движения змейки в направлении. Если игра окончена, верните -1. Пример:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

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

class SnakeGame:
    def __init__(self, width, height, food):
        self.width = width
        self.height = height
        self.food = food
        self.score = 0
        self.snake = [(0, 0)]
        self.snake_set = set([(0, 0)])
        self.food_index = 0

    def move(self, direction):
        head = self.snake[0]
        new_head = list(head)

        if direction == "U":
            new_head[0] -= 1
        elif direction == "D":
            new_head[0] += 1
        elif direction == "L":
            new_head[1] -= 1
        elif direction == "R":
            new_head[1] += 1

        new_head = tuple(new_head)

        if new_head[0] < 0 or new_head[0] >= self.height or new_head[1] < 0 or new_head[1] >= self.width:
            return -1

        if new_head in self.snake_set and new_head != self.snake[-1]:
            return -1

        if self.food_index < len(self.food) and new_head == tuple(self.food[self.food_index]):
            self.food_index += 1
        else:
            tail = self.snake.pop()
            self.snake_set.remove(tail)

        self.snake.insert(0, new_head)
        self.snake_set.add(new_head)

        return len(self.snake) - 1

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

Получите IT профессию с официальным ДОКУМЕНТОМ! Не просто курсы – а полноценное образование с дипломом о профессиональной переподготовке или удостоверением о повышении квалификации, внесенным в Росреестр! Выбирайте направление: -Web-разработчик -Инженер MikroTik -Специалист по AI и машинному обучению -Сетевой инженер -Linux-администратор -Python-программист -DevOps-инженер -Администратор Windows Server -Специалист по слаботочным сетям (СКС) Ваши гарантии: ✅Законный документ о квалификации ✅Право на ведение профдеятельности ✅Весомое преимущество при трудоустройстве ✅Поддержка ментора ✅Дистанционное обучение Инвестируйте в будущее – получите не только знания, но и официальную профессию! Перейти на сайт #реклама 16+ dms-it.ru О рекламодателе

Задача: №16. 3Sum Closest Сложность: medium Учитывая целочисленный массив nums длины n и целочисленную target, найдите три целых числа в nums, сумма которых наиболее близка к target. Возвращает сумму этих трех чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение. Пример:

Input: nums = [-1,2,1,-4], target = 1  
Output: 2  

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

class Solution:  
    def threeSumClosest(self, num, target):  
        num.sort()  
        result = num[0] + num[1] + num[2]  
        for i in range(len(num) - 2):  
            j, k = i + 1, len(num) - 1  
            while j < k:  
                sum = num[i] + num[j] + num[k]  
                if sum == target:  
                    return sum  

                if abs(sum - target) < abs(result - target):  
                    result = sum  

                if sum < target:  
                    j += 1  
                else:  
                    k -= 1  

        return result

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

Как самостоятельно читать анализы и выявлять заболевания Научитесь разбирать общий анализ крови с развернутой лейкоцитарной формулой. Это бесплатно. На открытом уроке вы: ✅научитесь разбирать общий анализ крови с развернутой лейкоцитарной формулой; ✅узнаете о каких дефицитах может рассказать этот недорогой анализ; ✅научитесь составлять план работы с этим анализом без лекарств; ✅ узнаете, как стать нутрициологом, где искать клиентов и как зарабатывать от 100 000 рублей, не выходя из дома При регистрации вы получите подарок - конспект урока. После урока по этому конспекту вы сможете самостоятельно разобрать свой общий анализ крови. Чтобы зарегистрироваться на урок - переходите по ссылке. ⚡Урок бесплатный, поэтому количество мест ограничено. Зарегистрироваться #реклама 16+ pro-telo1.com О рекламодателе

Задача: 319. Bulb Switcher Сложность: medium Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку. На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку. Верните количество лампочек, которые будут включены после n раундов. Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(n ** 0.5)

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

Регистрируйтесь на Yandex Neuro Scale В этом году у конференции новое имя и фокус: главной темой становятся нейротехнологии. Мы покажем, как бизнес уже применяет сервисы и как создавать собственных AI-агентов с помощью инструментов нашей платформы. ✨Ждём вас на главной конференции Yandex Cloud!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 905. Sort Array By Parity Сложность: easy Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию. Пример:

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

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

def sortArrayByParity(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 != 0]
    return evens + odds

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

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

Задача: 541. Reverse String II Сложность: easy Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки. Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть. Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

👨‍💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        a = list(s)
        for start in range(0, len(a), 2 * k):
            i, j = start, min(start + k - 1, len(a) - 1)
            while i < j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1
        return ''.join(a)

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

Не платите больше. Зафиксируйте цену сегодня Сколько клиентов вы уже упустили? Каждая просроченная заявка – это деньги вашим конкурентам. amoCRM помогает закрывать сделки, пока другие теряют лиды. Мы не делаем универсальных решений для всех. Только то, что работает в продажах. И одно из лучших решений, которое вы можете принять сейчас – это зафиксировать текущую цену. С 01 сентября amoCRM станет дороже. Но если подключитесь до этой даты, мы зафиксируем текущую цену для вас — и сейчас, и при продлении. ✨ Переходите по ссылке и успейте зафиксировать свою выгоду! Узнать больше #реклама 16+ amocrm.ru О рекламодателе