Python | LeetCode

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 542. 01 Matrix Сложность: medium Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки. Расстояние между двумя соседними ячейками равно 1. Пример:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

👨‍💻 Алгоритм: 1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen. 2⃣Выполните BFS: Пока очередь не пуста, извлекайте текущие row, col, steps из очереди. Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen. 3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix. 😎 Решение:

from collections import deque

class Solution:
    def __init__(self):
        self.m = 0
        self.n = 0
        self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    def updateMatrix(self, mat):
        self.m = len(mat)
        self.n = len(mat[0])
        matrix = [[0] * self.n for _ in range(self.m)]
        seen = [[False] * self.n for _ in range(self.m)]
        queue = deque()

        for row in range(self.m):
            for col in range(self.n):
                matrix[row][col] = mat[row][col]
                if matrix[row][col] == 0:
                    queue.append((row, col, 0))
                    seen[row][col] = True
        
        while queue:
            row, col, steps = queue.popleft()
            
            for dr, dc in self.directions:
                nextRow, nextCol = row + dr, col + dc
                if self.valid(nextRow, nextCol) and not seen[nextRow][nextCol]:
                    seen[nextRow][nextCol] = True
                    queue.append((nextRow, nextCol, steps + 1))
                    matrix[nextRow][nextCol] = steps + 1
        
        return matrix
    
    def valid(self, row, col):
        return 0 <= row < self.m and 0 <= col < self.n

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

Бесплатный курс по дизайну: веб, графический и UX/UI Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma! Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰 Этот курс для тебя, если ты: ✅ мечтаешь о новой профессии в digital, но не знаешь, с чего начать; ✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества; ✅ полный новичок и хочешь систему, а не хаос; ✅ хочешь начать зарабатывать удалённо. Зарегистрироваться #реклама 16+ ydaev.ru О рекламодателе

Задача: 655. Print Binary Tree Сложность: medium Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]). Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res. Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

👨‍💻 Алгоритм: 1⃣Найдите высоту дерева и определите размер матрицы (m x n). 2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла. 3⃣Верните заполненную матрицу. 😎 Решение:

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

def findHeight(root):
    if not root:
        return -1
    return 1 + max(findHeight(root.left), findHeight(root.right))

def fill(res, root, r, c, height):
    if not root:
        return
    res[r][c] = str(root.val)
    if root.left:
        fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height)
    if root.right:
        fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height)

def printTree(root):
    height = findHeight(root)
    m = height + 1
    n = (1 << (height + 1)) - 1
    res = [["" for _ in range(n)] for _ in range(m)]
    fill(res, root, 0, (n - 1) // 2, height)
    return res

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

Задача: 1464. Maximum Product of Two Elements in an Array Сложность: easy Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1). Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

👨‍💻 Алгоритм: 1⃣Инициализируйте biggest = 0 и secondBiggest = 0. 2⃣Итерируйте по каждому элементу массива nums: Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент. Иначе обновите secondBiggest, если текущий элемент больше secondBiggest. 3⃣Верните (biggest - 1) * (secondBiggest - 1). 😎 Решение:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        biggest = 0
        secondBiggest = 0
        for num in nums:
            if num > biggest:
                secondBiggest = biggest
                biggest = num
            elif num > secondBiggest:
                secondBiggest = num
        return (biggest - 1) * (secondBiggest - 1)

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

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе

Задача: 967. Numbers With Same Consecutive Differences Сложность: medium Даны два целых числа n и k, верните массив всех целых чисел длины n, где разница между каждыми двумя последовательными цифрами равна k. Вы можете вернуть ответ в любом порядке. Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются. Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        if N == 1:
            return list(range(10))
        
        queue = list(range(1, 10))
        for _ in range(N - 1):
            next_queue = []
            for num in queue:
                tail_digit = num % 10
                next_digits = {tail_digit + K, tail_digit - K}
                for next_digit in next_digits:
                    if 0 <= next_digit < 10:
                        next_queue.append(num * 10 + next_digit)
            queue = next_queue
        
        return queue

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

Задача: 498. Diagonal Traverse Сложность: medium Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке. Пример:

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

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

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
        
        N, M = len(mat), len(mat[0])
        result = []
        
        for d in range(N + M - 1):
            intermediate = []
            r = 0 if d < M else d - M + 1
            c = d if d < M else M - 1
            
            while r < N and c > -1:
                intermediate.append(mat[r][c])
                r += 1
                c -= 1
            
            if d % 2 == 0:
                result.extend(intermediate[::-1])
            else:
                result.extend(intermediate)
        
        return result

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

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

Задача: 220. Contains Duplicate III Сложность: hard Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff. Найдите пару индексов (i, j) таких, что: i != j, abs(i - j) <= indexDiff, abs(nums[i] - nums[j]) <= valueDiff. Верните true, если такая пара существует, или false в противном случае. Пример:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

👨‍💻 Алгоритм: 1️⃣Инициализация и вычисление корзин: Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w. 2️⃣Итерация и проверка корзин: Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна. 3️⃣Завершение: Если ни одна пара "почти дубликатов" не найдена, вернуть false. 😎 Решение:

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if t < 0: return False
        buckets = {}
        w = t + 1

        for i in range(len(nums)):
            bucket = nums[i] // w if nums[i] >= 0 else (nums[i] + 1) // w - 1
            if bucket in buckets: return True
            if bucket - 1 in buckets and abs(nums[i] - buckets[bucket - 1]) < w: return True
            if bucket + 1 in buckets and abs(nums[i] - buckets[bucket + 1]) < w: return True
            buckets[bucket] = nums[i]
            if i >= k:
                del buckets[nums[i - k] // w if nums[i - k] >= 0 else (nums[i - k] + 1) // w - 1]
        return False

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

Задача: 649. Dota2 Senate Сложность: medium В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire". Пример:

Input: senate = "RD"
Output: "Radiant"

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

from collections import deque

def predictPartyVictory(senate):
    radiant = deque()
    dire = deque()
    
    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)
    
    while radiant and dire:
        r = radiant.popleft()
        d = dire.popleft()
        if r < d:
            radiant.append(r + len(senate))
        else:
            dire.append(d + len(senate))
    
    return "Radiant" if radiant else "Dire"

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

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

Задача: 631. Design Excel Sum Formula Сложность: hard Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти. Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

class Excel:

    def __init__(self, height: int, width: str):
        self.mat = [[0] * (ord(width) - ord('A') + 1) for _ in range(height)]
        self.formulas = {}

    def set(self, row: int, column: str, val: int) -> None:
        self.mat[row - 1][ord(column) - ord('A')] = val
        self.formulas.pop((row, column), None)

    def get(self, row: int, column: str) -> int:
        if (row, column) in self.formulas:
            return self._evaluate_formula(row, column)
        return self.mat[row - 1][ord(column) - ord('A')]

    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        self.formulas[(row, column)] = numbers
        return self._evaluate_formula(row, column)

    def _evaluate_formula(self, row: int, column: str) -> int:
        total = 0
        for number in self.formulas[(row, column)]:
            if ':' in number:
                start, end = number.split(':')
                start_row, start_col = int(start[1:]), start[0]
                end_row, end_col = int(end[1:]), end[0]
                for r in range(start_row, end_row + 1):
                    for c in range(ord(start_col), ord(end_col) + 1):
                        total += self.get(r, chr(c))
            else:
                r, c = int(number[1:]), number[0]
                total += self.get(r, c)
        return total

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

Задача: 69. Sqrt(x) Сложность: easy Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным. Вы не должны использовать встроенные функции или операторы для возведения в степень. Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python. Пример:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

👨‍💻 Алгоритм: 1️⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2. 2️⃣Пока left ≤ right: Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x: Если num × num > x, переместите правую границу right = pivot − 1. В противном случае, если num × num < x, переместите левую границу left = pivot + 1. В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его. 3️⃣Верните right. 😎 Решение:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left, right = 2, x // 2

        while left <= right:
            pivot = left + (right - left) // 2
            num = pivot * pivot
            if num > x:
                right = pivot - 1
            elif num < x:
                left = pivot + 1
            else:
                return pivot

        return right

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

Задача: 723. Candy Crush Сложность: medium Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску. Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

def candyCrush(board):
    m, n = len(board), len(board[0])
    stable = False

    while not stable:
        stable = True
        crush = [[False] * n for _ in range(m)]

        for i in range(m):
            for j in range(n - 2):
                if abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]) != 0:
                    stable = False
                    crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = True

        for i in range(m - 2):
            for j in range(n):
                if abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]) != 0:
                    stable = False
                    crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = True

        for i in range(m):
            for j in range(n):
                if crush[i][j]:
                    board[i][j] = 0

        for j in range(n):
            idx = m - 1
            for i in range(m - 1, -1, -1):
                if board[i][j] != 0:
                    board[idx][j] = board[i][j]
                    idx -= 1
            for i in range(idx, -1, -1):
                board[i][j] = 0

    return board

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

Продвижение в Telegram с помощью Яндекс Директа ⚡Запустите продвижение в телеграм-каналах и привлекайте целевую аудиторию 📱 Таргетинг по тематикам, регионам и каналам в Telegram Попробовать #реклама yandex.ru О рекламодателе

Задача: 358. Rearrange String k Distance Apart Сложность: hard Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "". Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

from collections import defaultdict

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        freqs = defaultdict(int)
        max_freq = 0
        
        for char in s:
            freqs[char] += 1
            max_freq = max(max_freq, freqs[char])
        
        most_chars = {char for char, freq in freqs.items() if freq == max_freq}
        second_chars = {char for char, freq in freqs.items() if freq == max_freq - 1}
        
        segments = [list() for _ in range(max_freq)]
        
        for i in range(max_freq):
            for char in most_chars:
                segments[i].append(char)
            if i < max_freq - 1:
                for char in second_chars:
                    segments[i].append(char)
        
        segment_id = 0
        
        for char, freq in freqs.items():
            if char in most_chars or char in second_chars:
                continue
            for _ in range(freq):
                segments[segment_id].append(char)
                segment_id = (segment_id + 1) % (max_freq - 1)
        
        for i in range(max_freq - 1):
            if len(segments[i]) < k:
                return ""
        
        return "".join("".join(segment) for segment in segments)

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away Сложность: easy Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false. Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

👨‍💻 Алгоритм: 1⃣Инициализировать счетчик нулей значением k для учета первого появления единицы. 2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0. 3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true. 😎 Решение:

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        count = k
        for num in nums:
            if num == 1:
                if count < k:
                    return False
                count = 0
            else:
                count += 1
        return True

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

Задача: 535. Encode and Decode TinyURL Сложность: medium Спроектируйте класс для кодирования URL и декодирования короткого URL. Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL. Реализуйте класс Solution: Solution() Инициализирует объект системы. String encode(String longUrl) Возвращает короткий URL для данного longUrl. String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом. Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

import random
import string

class Codec:
    def __init__(self):
        self.alphabet = string.ascii_letters + string.digits
        self.map = {}
        self.key = self.get_rand()

    def get_rand(self):
        return ''.join(random.choice(self.alphabet) for _ in range(6))

    def encode(self, longUrl: str) -> str:
        while self.key in self.map:
            self.key = self.get_rand()
        self.map[self.key] = longUrl
        return "http://tinyurl.com/" + self.key

    def decode(self, shortUrl: str) -> str:
        key = shortUrl.replace("http://tinyurl.com/", "")
        return self.map.get(key, "")

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

Бесплатный тест драйв профессии дизайнер с наставником Сделай 6 кейсов с нуля и получи готовое портфолио в формате Reels для привлечения первых клиентов 🎓 Освоишь Figma и протестируешь 3 направления: графический, веб и UX/UI дизайн 📊 Создашь 6 кейсов: сайт, карточку МП, баннеры и презентации 💰Узнаешь, почему digital-дизайнерам платят до 250 000 ₽ И получишь пошаговую стратегию выхода на cтабильный доход: Без поиска клиентов 24/7, без бирж фриланса, без продаж и без копеечных заказов на 300 ₽ Формат как на стажировке: Живые уроки, всё в Telegram, личные видео-разборы от дизайнеров ✨ Розыгрыш AirPods для всех, кто дойдет до конца Попробовать #реклама 16+ study.logomachine.ru О рекламодателе