Python | LeetCode

ЖК Символ. До 30.09: лоты от 18,5 млн/₽ со скидкой 12% ❤️Скидки 12% в готовом для жизни квартале у центра Москвы. Комфортная рассрочка от застройщика всего 180 тыс/₽ в месяц. 🎓На территории парк 10 га и 150+ открытых объектов инфраструктуры. Кафе, рестораны, медцентры, детский сад, школы, инженерный лицей при МГТУ им. Баумана. 🏠Стильные и просторные квартиры с уникальными видами. Высота потолков до 4,25 м, окна до 3,25 м, угловое остекление. ❤️Клуб резидентов для разных сценариев жизни: лаунж-зоны, фитнес-зал, кинотеатр, коворкинг, детская, репетиторская, террасы на крыше. ✨ Победы в престижных премиях: «Лучший ЖК-новостройка в РФ» (ТОП ЖК 2023), «Лучший реализованный проект» (конкурс Правительства Москвы 2019). Узнать больше Проектная декларация на сайте https://наш.дом.рф/. #реклама mrqz.click О рекламодателе

Задача: 1422. Maximum Score After Splitting a String Сложность: easy Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку). Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке. Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

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

class Solution:
    def maxScore(self, s: str) -> int:
        ones = s.count('1')
        zeros = ans = 0

        for i in range(len(s) - 1):
            if s[i] == '1':
                ones -= 1
            else:
                zeros += 1
            ans = max(ans, zeros + ones)
        
        return ans

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

Задача: 993. Cousins in Binary Tree Сложность: easy Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false. Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей. Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1. Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

👨‍💻 Алгоритм: 1⃣Поиск глубины и родителя для каждого узла: Используйте поиск в глубину (DFS) для обхода дерева. Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y. 2⃣Проверка условий на кузенов: Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей. 3⃣Возврат результата: Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false. 😎 Решение:

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

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        parent_x, parent_y = None, None
        depth_x, depth_y = -1, -1
        
        def dfs(node, parent, depth):
            nonlocal parent_x, parent_y, depth_x, depth_y
            if not node:
                return
            if node.val == x:
                parent_x, depth_x = parent, depth
            elif node.val == y:
                parent_y, depth_y = parent, depth
            else:
                dfs(node.left, node, depth + 1)
                dfs(node.right, node, depth + 1)
        
        dfs(root, None, 0)
        return depth_x == depth_y and parent_x != parent_y

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

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

Задача: 32. Longest Valid Parentheses Сложность: hard Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками. Пример:

Input: s = "(()"
Output: 2

👨‍💻 Алгоритм: 1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека. 2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной. 3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки. 😎 Решение:

def is_valid(s: str) -> bool:
    stack = []
    for char in s:
        if char == '(':
            stack.append('(')
        elif stack and stack[-1] == '(':
            stack.pop()
        else:
            return False
    return len(stack) == 0

def longest_valid_parentheses(s: str) -> int:
    maxlen = 0
    for i in range(len(s)):
        for j in range(i + 2, len(s) + 1, 2):
            substring = s[i:j]
            if is_valid(substring):
                maxlen = max(maxlen, j - i)
    return maxlen

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

Задача: 238. Product of Array Except Self Сложность: medium Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i]. Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число. Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления. Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм: 1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1]. 2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево. 3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его. 😎 Решение:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        L = [1] * length
        R = [1] * length
        answer = [1] * length

        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]

        for i in range(length - 2, -1, -1):
            R[i] = nums[i + 1] * R[i + 1]

        for i in range(length):
            answer[i] = L[i] * R[i]

        return answer

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

Вебинар: Как Python-разработчику получить оффер в бигтех Увидишь, где ошибаются даже сильные инженеры. Поймёшь, как нанимающие инженеры читают код. Получишь готовый фреймворк для разбора любого сервиса — применимый и на интервью, и в ежедневном code review. Узнаешь, какие soft skills критичны для роста в Senior+. Спикер: Хачатур Саркисян, Senior Python разработчик в Яндексе. Участие — бесплатно. Зарегистрироваться #реклама 16+ web.shortcut.education О рекламодателе

Задача: 953. Verifying an Alien Dictionary Сложность: hard В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке. Пример:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

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

def isAlienSorted(words, order):
    order_map = {char: i for i, char in enumerate(order)}
    
    def compare(word1, word2):
        for c1, c2 in zip(word1, word2):
            if order_map[c1] < order_map[c2]:
                return True
            elif order_map[c1] > order_map[c2]:
                return False
        return len(word1) <= len(word2)
    
    for i in range(len(words) - 1):
        if not compare(words[i], words[i + 1]):
            return False
    return True

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

Задача: 1424. Diagonal Traverse II Сложность: medium Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке. Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь с (0, 0) и список ответов ans. 2⃣Пока очередь не пуста: Извлеките (row, col) из очереди. Добавьте nums[row][col] в ans. Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь. Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь. 3⃣Верните ans. 😎 Решение:

from collections import deque

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        queue = deque([(0, 0)])
        ans = []
        
        while queue:
            row, col = queue.popleft()
            ans.append(nums[row][col])
            
            if col == 0 and row + 1 < len(nums):
                queue.append((row + 1, col))
                
            if col + 1 < len(nums[row]):
                queue.append((row, col + 1))
                
        return ans

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

Выигрывайте призы от Яндекс Образования Популярные блогеры и студенты ЯО делают что-то новое — и у них получается очень вдохновляюще! Общайтесь с любимыми блогерами и выигрывайте призы Узнать больше #реклама 16+ refer.id О рекламодателе

Задача: 201. Bitwise AND of Numbers Range Сложность: medium Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно. Пример:

Input: left = 5, right = 7
Output: 4

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

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        shift = 0
        while m < n:
            m = m >> 1
            n = n >> 1
            shift += 1
        return m << shift

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

Задача: 1470. Shuffle the Array Сложность: easy Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn]. Верните массив в форме [x1, y1, x2, y2, ..., xn, yn]. Пример:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

👨‍💻 Алгоритм: 1⃣Создайте массив result размером 2 * n. 2⃣Итеративно пройдите по массиву nums от 0 до n - 1: Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result. Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result. 3⃣Верните массив result. 😎 Решение:

class Solution:
    def shuffle(self, nums, n):
        result = [0] * (2 * n)
        for i in range(n):
            result[2 * i] = nums[i]
            result[2 * i + 1] = nums[n + i]
        return result

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

🚨60 минут Пожизненный PRO-доступ на easyoffer (подготовка к IT-собесам + поиск оффера) по цене одного года закрывается прямо сейчас. Один платёж — доступ навсегда. Последнее напоминание 👇 👉 https://easyoffer.ru/pro

⚠️ 3 часа до конца акции. Последний шанс забрать пожизненный PRO на easyoffer по цене одного года. Это полный доступ к подготовке к собесам и инструментам поиска работы (вопросы с реальных интервью, ответы сеньоров, автоотклики, тренажёры) — один раз и навсегда, вместо ежегодной оплаты. В полночь цена возвращается к обычной. 👉 https://easyoffer.ru/pro

Задача: 1423. Maximum Points You Can Obtain from Cards Сложность: medium Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints. За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт. Ваш результат - это сумма очков взятых карт. Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить. Пример:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

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

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        frontSetOfCards = [0] * (k + 1)
        rearSetOfCards = [0] * (k + 1)
        
        for i in range(k):
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i]
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]
        
        maxScore = 0
        for i in range(k + 1):
            currentScore = frontSetOfCards[i] + rearSetOfCards[k - i]
            maxScore = max(maxScore, currentScore)
        
        return maxScore

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

⏳ Ребята, сегодня заканчивается акция, о которой стоит знать, если вы в поиске работы или планируете сменить её в ближайший год. easyoffer — это платформа для подготовки к IT-собесам и поиска оффера. Внутри: – база реальных вопросов и live-coding задач с собесов (с частотой их встречаемости) – эталонные ответы от Senior-разработчиков – 1100+ записей настоящих интервью (Сбер, Яндекс, Авито, WB, OZON, МТС) – автоотклики на hh, генератор резюме под вакансию, тренажёры собеседований Сегодня пожизненный PRO-доступ продаётся по цене одного года — платишь один раз и пользуешься всем этим всю жизнь, включая будущие фичи. С завтрашнего дня — только обычная годовая подписка. 👉 https://easyoffer.ru/pro

Аренда VPS/VDS-сервера. Виртуальные выделенные серверы в дата-центрах уровня Tier III — 7 готовых конфигураций от 200 ₽/мес. Преимущества аренды: - Выделенные ресурсы без переплаты; - KVM-виртуализация; - Быстрые NVMe SSD; - Бесплатная защита от DDoS; - Управление через панель, API и Terraform; - Техподдержка 24/7. Запустите сервер за несколько минут! Попробовать #реклама 16+ selectel.ru О рекламодателе

🔍Тестовое собеседование на Middle Python с разработчиком из Авито завтра вечером Уже завтра вечером в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Python-разработчика. Как это будет: 📂 Даня, старший разработчик в Авито, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Даня будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Дане Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Python-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_py_bot Реклама. О рекламодателе.

Премьера сериала «Чудо» Провидица или мошенница? Ида Галич в остросоциальном детективе создателей «Нулевого пациента». Смотрите на Кинопоиске Смотреть #реклама 18+ hd.kinopoisk.ru О рекламодателе

Задача: 753. Cracking the Safe Сложность: medium Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно. После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода. Пример:

Input: n = 1, k = 2
Output: "10"

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

def crackSafe(n, k):
    seen = set()
    result = []

    def dfs(node):
        for x in range(k):
            neighbor = node + str(x)
            if neighbor not in seen:
                seen.add(neighbor)
                dfs(neighbor[1:])
                result.append(str(x))

    start_node = '0' * (n - 1)
    dfs(start_node)
    return start_node + ''.join(result)

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