Python | LeetCode

Задача: 422. Valid Word Square Сложность: easy Дан массив строк words, верните true, если он образует правильный квадрат слов. Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns). Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

👨‍💻 Алгоритм: 1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом. 2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false. 3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false. 😎 Решение:

class Solution:
    def validWordSquare(self, words: list[str]) -> bool:
        cols = 0
        rows = len(words)
        newWords = []
        
        for word in words:
            cols = max(cols, len(word))

        if cols != len(words[0]) or rows != cols:
            return False

        for col in range(cols):
            newWord = ""
            for row in range(rows):
                if col < len(words[row]):
                    newWord += words[row][col]
            newWords.append(newWord)

        return words == newWords

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 172. Factorial Trailing Zeroes Сложность: medium Дано целое число n, верните количество конечных нулей в n!. Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Пример:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

👨‍💻 Алгоритм: 1️⃣Вычислите факториал n: Инициализируйте переменную nFactorial значением 1. Для каждого i от 2 до n включительно умножайте nFactorial на i. 2️⃣Подсчитайте количество конечных нулей в nFactorial: Инициализируйте переменную zeroCount значением 0. Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1. 3️⃣Верните значение zeroCount как количество конечных нулей в n!. 😎 Решение:

class Solution:
    def trailingZeroes(self, n: int) -> int:

        n_factorial = 1
        for i in range(2, n + 1):
            n_factorial *= i

        zero_count = 0
        while n_factorial % 10 == 0:
            zero_count += 1
            n_factorial //= 10

        return zero_count

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves Сложность: medium Вам дан массив целых чисел nums. За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение. Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов. Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        numsSize = len(nums)
        
        if numsSize <= 4:
            return 0
        
        nums.sort()
        
        minDiff = float('inf')
        
        for left in range(4):
            right = numsSize - 4 + left
            minDiff = min(minDiff, nums[right] - nums[left])
        
        return minDiff

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

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

Задача: 345. Reverse Vowels of a String Сложность: easy Дана строка s, переверните только все гласные в строке и верните её. Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры. Пример:

Input: s = "hello"
Output: "holle"

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

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set("aeiouAEIOU")
        s = list(s)
        left, right = 0, len(s) - 1
        
        while left < right:
            if s[left] not in vowels:
                left += 1
            elif s[right] not in vowels:
                right -= 1
            else:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
                
        return ''.join(s)

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

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

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