Python | LeetCode

Задача: 272. Closest Binary Search Tree Value II Сложность: hard Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке. Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению. Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        arr = []
        self.dfs(root, arr)
        arr.sort(key=lambda x: abs(x - target))
        return arr[:k]
    
    def dfs(self, node: TreeNode, arr: List[int]):
        if not node:
            return
        arr.append(node.val)
        self.dfs(node.left, arr)
        self.dfs(node.right, arr)

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

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ mrqz.me О рекламодателе

Задача: 682. Baseball Game Сложность: medium Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись. Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих: Целое число x. Записать новый счет, равный x. '+'. Записать новый счет, который является суммой двух предыдущих очков. 'D'. Записать новый счет, который в два раза больше предыдущего очка. 'C'. Аннулировать предыдущее очко, удалив его из записи. Верните сумму всех очков в записи после применения всех операций. Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны. Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

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

class Solution:
    def calPoints(self, ops: List[str]) -> int:
        stack = []

        for op in ops:
            if op == "+":
                stack.append(stack[-1] + stack[-2])
            elif op == "C":
                stack.pop()
            elif op == "D":
                stack.append(2 * stack[-1])
            else:
                stack.append(int(op))
        
        return sum(stack)

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

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

Задача: 1220. Count Vowels Permutation Сложность: hard Дано целое число n, ваша задача состоит в том, чтобы посчитать, сколько строк длины n можно сформировать по следующим правилам: Каждый символ является строчной гласной буквой ('a', 'e', 'i', 'o', 'u') Каждая гласная 'a' может быть только перед 'e'. Каждая гласная 'e' может быть только перед 'a' или 'i'. Каждая гласная 'i' не может быть перед другой 'i'. Каждая гласная 'o' может быть только перед 'i' или 'u'. Каждая гласная 'u' может быть только перед 'a'. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

👨‍💻 Алгоритм: 1⃣Инициализация массивов и начальных условий: Инициализируйте пять одномерных массивов размером n для хранения количества строк, оканчивающихся на каждую гласную. Установите первый элемент в каждом массиве равным 1, так как для строк длиной 1 существует только одна возможная строка для каждой гласной. 2⃣Заполнение массивов в соответствии с правилами: Проходите по длине строки от 1 до n. Обновляйте значения массивов, следуя правилам для каждой гласной, учитывая предыдущие значения. 3⃣Суммирование и возврат результата: Возьмите сумму последних элементов всех пяти массивов. Верните результат по модулю 10^9 + 7. 😎 Решение:

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 1000000007
        a = [0] * n
        e = [0] * n
        i = [0] * n
        o = [0] * n
        u = [0] * n
        
        a[0] = e[0] = i[0] = o[0] = u[0] = 1
        
        for k in range(1, n):
            a[k] = (e[k - 1] + i[k - 1] + u[k - 1]) % MOD
            e[k] = (a[k - 1] + i[k - 1]) % MOD
            i[k] = (e[k - 1] + o[k - 1]) % MOD
            o[k] = i[k - 1] % MOD
            u[k] = (i[k - 1] + o[k - 1]) % MOD
        
        return (a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD

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

Курс «Бизнес-аналитик» - поможем с трудоустройством! Освойте высокооплачиваемую IT-профессию с нуля за 7 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python, BPMN, UML, EPC, IDEF. Преимущества обучения в Академии Eduson: 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 22 реальных бизнес-кейса 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Получить консультацию #реклама 16+ eduson.academy О рекламодателе

Задача: 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

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

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

Задача: 1255. Maximum Score Words Formed by Letters Сложность: medium Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно. Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

from collections import Counter
from itertools import combinations

def maxScoreWords(words, letters, score):
    def word_score(word):
        return sum(score[ord(ch) - ord('a')] for ch in word)
    
    def can_form_word(word, letter_count):
        word_count = Counter(word)
        for ch in word_count:
            if word_count[ch] > letter_count[ch]:
                return False
        return True

    max_score = 0
    letter_count = Counter(letters)

    for r in range(1, len(words) + 1):
        for combo in combinations(words, r):
            combo_score = 0
            used_letters = Counter()
            valid_combo = True
            for word in combo:
                word_count = Counter(word)
                if can_form_word(word, letter_count - used_letters):
                    combo_score += word_score(word)
                    used_letters += word_count
                else:
                    valid_combo = False
                    break
            if valid_combo:
                max_score = max(max_score, combo_score)

    return max_score

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

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

Задача: 138. Copy List with Random Pointer Сложность: medium Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null. Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке. Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y. Верните голову скопированного связного списка. Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где: val: целое число, представляющее Node.val random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел. Вашему коду будет дана только голова оригинального связного списка. Пример:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

👨‍💻 Алгоритм: 1️⃣Инициализация и начало обхода: Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов. 2️⃣Проверка и клонирование узлов: Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary. Если клонированная копия существует, используйте ссылку на этот клонированный узел. Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон. 3️⃣Рекурсивные вызовы для обработки связей: Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next. Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next. 😎 Решение:

class Solution:
    def __init__(self):
        self.visitedHash = {}

    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if head == None:
            return None

        if head in self.visitedHash:
            return self.visitedHash[head]

        node = Node(head.val, None, None)
        self.visitedHash[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)

        return node

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

Привет ребят! Мне в последнее время пишет очень много начинающих предпринимателей оценить их бизнес со стороны. Я как человек с 10 годами опыта в создании стартапов, как успеших так и абсолютно убыточных могу дать свою оценку. Я продавал свой бизнес в прибыль, и я также в убыток продовал несколько своих проектов. Готов с вами обсудить ваши идеи, но только сейчас, пока я пьян и на веселе. Напишите @kivaiko и мы созвонимся, чтобы я трезво оценивал ваши шансы и дал экспертные рекомендации.

Получи грант на обучение в Центральном университете Центральный университет выдает гранты на 4 года обучения в бакалавриате. Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант. Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1014. Best Sightseeing Pair Сложность: easy Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей. Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        max_score = 0
        max_i_plus_value = values[0]
        
        for j in range(1, len(values)):
            max_score = max(max_score, max_i_plus_value + values[j] - j)
            max_i_plus_value = max(max_i_plus_value, values[j] + j)
        
        return max_score

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

PostgreSQL как сервис: что это и как применяется? Сервис PostgreSQL от РТК-ЦОД позволяет быстро развернуть, эксплуатировать и масштабировать базу данных в облаке. Процесс установки и настройки полностью автоматизирован. Как наши клиенты используют PostgreSQL? — Работают в 1С — Управляют платежными системами — Ведут финансовый учет — Собирают геоданные — Работают с данными со сложной структурой — Анализируют большие массивы данных ✅30 дней бесплатно: тестируйте наш сервис с полным доступом ко всем возможностям. Оставьте заявку на www.cloud.rt.ru Узнать больше #реклама 16+ cloud.rt.ru О рекламодателе

Задача: 744. Find Smallest Letter Greater Than Target Сложность: easy Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

def nextGreatestLetter(letters, target):
    left, right = 0, len(letters) - 1
    while left <= right:
        mid = (left + right) // 2
        if letters[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return letters[left % len(letters)]

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

Курсы JAVA-разработки Гарантия ЗП от 120 000р в договоре Jаvа — это язык, на котором строятся банковские системы, мобильные приложения, крупные веб-сервисы и многое другое, а спрос на Jаvа-разработчиков стабильно высок. Благодаря кроссплатформенности и надежности, ты сможешь работать в любой сфере IТ — от финансов до Коммерческой отрасли.📊💰 Почему это работает?✨ - Минимальные вложения. - Тысячи человек уже в IТ. Наши выпускники работают в крутых компаниях: от стартапов до международных корпораций. - Наши менторы — это опытные разработчики, которые ежедневно работают в IТ и готовы делиться актуальными знаниями. P.S. Если всё ещё сомневаешься и думаешь что будет сложно — просто попробуй.😊 Мы берем на себя все риски: ты оплачиваешь основную стоимость обучения только после успешного трудоустройства — это закреплено в договоре. Подать заявку #реклама 16+ kata.academy О рекламодателе

Задача: 153. Find Minimum in Rotated Sorted Array Сложность: Medium Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать: [4,5,6,7,0,1,2], если он был повернут 4 раза. [0,1,2,4,5,6,7], если он был повернут 7 раз. Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива. Вы должны написать алгоритм, который работает за время O(log n). Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

👨‍💻 Алгоритм: 1️⃣Нахождение середины массива: Определите элемент, находящийся посередине массива. 2️⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины. 3️⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом. 😎 Решение:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        left = 0

        right = len(nums) - 1

        if nums[right] > nums[0]:
            return nums[0]
        while right >= left:
            
            mid = left + (right - left) // 2
            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            if nums[mid - 1] > nums[mid]:
                return nums[mid]
            if nums[mid] > nums[0]:
                left = mid + 1
            else:
                right = mid - 1

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

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 442. Find All Duplicates in an Array Сложность: medium Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды. Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство. Пример:

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

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

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[j] == nums[i]:
                    ans.append(nums[i])
                    break
        
        return ans

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