Python | LeetCode

Главный навык на ближайшие годы — ВАЙБ-КОДИНГ ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную. Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы. Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg

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

80% системных аналитиков заваливают собеседования из-за глупых ошибок Самый простой способ подготовиться к собеседованию — это послушать, как его проходят другие. В канале System | Собеседования собрали базу реальных технических интервью, чтобы вы могли учиться на чужих ошибках, а не на своих. Что внутри: 💘 Разборы живых записей — от проектирования API до работы с БД 💘 Ключевые вопросы лидов из бигтеха 💘 Анализ ответов — где кандидат «поплыл» и как нужно было ответить правильно Подписывайтесь, чтобы получить доступ к базе живых разборов и увереннее чувствовать себя на собесах.

Задача: 245. Shortest Word Distance II Сложность: medium Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке. Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке. Пример:

    
        Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1{}
    

👨‍💻 Алгоритм: 1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3️⃣Верните значение переменной shortestDistance. 😎 Решение:

    
        from bisect import bisect_right

class Solution:
    def shortestWordDistance(self, wordsDict, word1, word2):
        indices1 = [i for i, word in enumerate(wordsDict) if word == word1]
        indices2 = [i for i, word in enumerate(wordsDict) if word == word2]
        
        shortestDistance = float('inf')
        for index in indices1:
            x = bisect_right(indices2, index)
            if x < len(indices2):
                shortestDistance = min(shortestDistance, indices2[x] - index)
            if x > 0 and indices2[x - 1] != index:
                shortestDistance = min(shortestDistance, index - indices2[x - 1])
        return shortestDistance{}
    

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

Задача: 1267. Count Servers that Communicate Сложность: medium На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение. Пример:

    
        Input: grid = [[1,0],[0,1]]
Output: 0{}
    

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

    
        def countServers(grid):
    rows = [0] * len(grid)
    cols = [0] * len(grid[0])

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                rows[i] += 1
                cols[j] += 1

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1 and (rows[i] > 1 or cols[j] > 1):
                count += 1

    return count{}
    

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

Задача: 760. Find Anagram Mappings Сложность: easy Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a. Пример:

    
        Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]{}
    

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

    
        def anagramMapping(nums1, nums2):
    index_map = {}
    for i, num in enumerate(nums2):
        if num in index_map:
            index_map[num].append(i)
        else:
            index_map[num] = [i]
    
    mapping = []
    for num in nums1:
        mapping.append(index_ma{}
    

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

Задача: №45. Jump Game II Сложность: medium Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0]. Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i. Возвращает минимальное количество переходов для достижения nums[n - 1]. Пример:

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

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

    
        class Solution:
    def jump(self, nums):
        jumps = 0
        farthest = 0
        current_end = 0
        
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                jumps += 1
                current_end = farthest
        
        return jumps{}
    

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

Задача: 930. Binary Subarrays With Sum Сложность: medium Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива. Пример:

    
        Input: nums = [1,0,1,0,1], goal = 2
Output: 4{}
    

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

    
        def numSubarraysWithSum(nums, goal):
    prefix_sum_count = {0: 1}
    current_sum = 0
    count = 0
    
    for num in nums:
        current_sum += num
        if current_sum - goal in prefix_sum_count:
            count += prefix_sum_count[current_sum - goal]
        if current_sum in prefix_sum_count:
            prefix_sum_count[current_sum] += 1
        else:
            prefix_sum_count[current_sum] = 1
    
    return count{}
    

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

Задача: 1155. Number of Dice Rolls With Target Sum Сложность: medium У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k. Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

    
        Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.{}
    

👨‍💻 Алгоритм: 1⃣Начните с: Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент. Сумма чисел на предыдущих кубиках currSum равна 0. Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию. 2⃣Базовые случаи: Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target. 3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum. 😎 Решение:

    
        class Solution:
    MOD = 10**9 + 7
    
    def waysToTarget(self, memo, diceIndex, n, currSum, target, k):
        if diceIndex == n:
            return int(currSum == target)
        
        if memo[diceIndex][currSum] != -1:
            return memo[diceIndex][currSum]
        
        ways = 0
        for i in range(1, min(k, target - currSum) + 1):
            ways = (ways + self.waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % self.MOD
        
        memo[diceIndex][currSum] = ways
        return ways
    
    def numRollsToTarget(self, n, k, target):
        memo = [[-1] * (target + 1) for _ in range(n + 1)]
        return self.waysToTarget(memo, 0, n, 0, target, k){}
    

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

Задача: 838. Push Dominoes Сложность: medium Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо. Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа. Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил. В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино. Вам дано строковое представление начального состояния домино: dominoes[i] = 'L', если i-е домино толкнули влево, dominoes[i] = 'R', если i-е домино толкнули вправо, и dominoes[i] = '.', если i-е домино не было толкнуто. Верните строку, представляющую конечное состояние. Пример:

    
        Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."{}
    

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

    
        class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        N = len(dominoes)
        indexes = [-1]
        symbols = ['L']
        
        for i in range(N):
            if dominoes[i] != '.':
                indexes.append(i)
                symbols.append(dominoes[i])
                
        indexes.append(N)
        symbols.append('R')
        
        ans = list(dominoes)
        for idx in range(len(indexes) - 1):
            i, j = indexes[idx], indexes[idx + 1]
            x, y = symbols[idx], symbols[idx + 1]
            if x == y:
                for k in range(i + 1, j):
                    ans[k] = x
            elif x == 'R' and y == 'L':
                for k in range(i + 1, j):
                    if k - i == j - k:
                        ans[k] = '.'
                    elif k - i < j - k:
                        ans[k] = 'R'
                    else:
                        ans[k] = 'L'
                        
        return ''.join(ans){}
    

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