Skip to content

sweetsenpai/leetcode

BranchesTags

Repository files navigation

Python LeetCode codecov

🚀 LeetCode Solutions

📚 Коллекция решений задач с LeetCode на Python.
🔹 Решения разделены по темам.
🔹 Включают пояснения и альтернативные способы решения.
🔹 Все решения протестированы с помощью pytest.

🏆 Прогресс

Категория Решено Цель
Массивы & Хэш таблицы ✅ 5/5 🎯 5
Стэк & Очередь ✅ 3/3 🎯 3
Сортировка и указатели ✅ 5/5 🎯 5
Sliding Window ✅ 2/3 🎯 3
Всего ✅ 15/30 🎯 30

(Обновляется вручную)

📁 Структура репозитория

📌 Решенные задачи

📝 Two Sum Problem

📌 Задача:

Найти два числа, которые в сумме дают заданное число.

❌ Изначальное решение и его проблемы 😕

В первой версии решения я ухватил принцип:

target - элемент списка = второе требуемое число.

Я проходил по nums, создавая его копию, в которой заменял текущий элемент на None. Это нужно было, чтобы избежать дубликатов (например, nums=[3,4,2], target=6, иначе я получал бы [0,0]).
Далее я проверял, существует ли второе число в изменённом списке, а если да, то находил его индекс через index().

🔴 Проблема:

Поиск index() делает решение квадратичным O(n²), что плохо для больших nums, но код хотя бы работал! ✌️

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      for index, item in enumerate(nums):
          search_num = nums.copy()
          second_num = target - item
          search_num[index] = None
          if second_num in search_num:
              return [index, search_num.index(second_num)]
      return []

✅ Оптимизированное решение 💡

В улучшенной версии я использую словарь (dict) для хранения элементов nums, которые мы уже прошли. При каждом шаге вычитаем текущий num из target и проверяем, есть ли нужное число в dict. Если есть — задача решена!

🔹 Почему быстрее?

  • Поиск в dict выполняется за O(1).
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for index, num in enumerate(nums):
            diff = target - num
            if diff in num_map:
                return [num_map[diff], index]
            num_map[num] = index
        return []

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$

    • — мы проходим по списку nums один раз, для каждого элемента выполняя операцию поиска в словаре, что происходит за $O(1)$. Таким образом, общая временная сложность составит $O(n)$.

  • 🧠 По памяти: $O(n)$

    • — мы используем дополнительную память для хранения элементов в словаре num_map, что требует $O(n)$ памяти в худшем случае (когда все элементы уникальны).

📝 Contains Duplicate

📌 Задача:

Проверить список на наличие дубликатов.

✅ Решение

Задача оказалась очень легкой и решилась за минуту + минута на написание тестов. Просто конвертируем изначальный список в set() который хранит только уникальные значение и сравниваем его длинну с длинной входного списка, если одинаковые то дубликатов нет, а если разные значит они есть 🤷‍♂️.

class Solution2:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$

    • — создание множества с помощью set(nums) имеет сложность $O(n)$, из-за того что для каждого элемента в списке выполняется вставка в множество за $O(1)$.
    • — вычисление длинн с помощью len() выполняется за $O(n)$.

  • 🧠 По памяти: $O(n)$

    • — мы используем дополнительную память для хранения элементов в словаре num_map, что требует $O(n)$ памяти в худшем случае (когда все элементы уникальны).

📝 Valid Anagram

📌 Задача:

Проверить является ли одна строка анаграммой второй строки.

❌ Изначальные решения и их проблемы 😕

С начала задача мне показалась такой же простой как и предыдущая, и я использовал set() для сравнения двух строк и leetcode даже счел такое решение верным.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return set(s) == set(t) and len(s) == len(t)

И всё бы было хорошо, если бы я не решил проверить свое решение с помощью chatgpt который предложил мне проверить свое решение с такими входными параметрами: s = "aacc", t = "ccac". И мое изначальное решение дало не верный ответ. Проблема в том, что set не считает количество букв в слове, а лишь собирает уникальные значения из-за чего я получил не верный ответ.😢

✅ Мое решение

Вторым моим решением было использовать словари dict[буква]:частота появления в слове для каждого из слов и в конце их сравнивать. И это рабочее решение, но не оптимальное по времени из-за двух полных циклов проходящих по строкам.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dict_s = {item: s.count(item) for item in set(s)}
        dict_b = {item: t.count(item) for item in set(t)}
        return dict_b == dict_s

✅ Оптимизированное решение 💡

Окончательное решение похоже на мое, но вместо тупого создания двух списков предусматривает два досрочных ответа, что экономит время:

1. Сначала мы проверяем строки на длину, если длина разная, 
   то такие строки не могут быть анаграммами и мы выдаем ответ не вызвав ни одного цикла 
   
2. В ходе второго цикла мы проверяем есть ли буква в первом словаре, 
   и если ее нет или количество букв не совпадает, мы так же досрочно выходим из цикла.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1
        
        for char in t:
            if char not in count or count[char] == 0:
                return False
            count[char] -= 1
        
        return True

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$

    • — проход по обоим списка занимет $O(s+t)$, что в результате дает $O(n)$,
    • — count.get(char, 0) и if char not in count or count[char] == 0: выполняются за $O(1)$

  • 🧠 По памяти: $O(n)$

    • — мы используем дополнительную память для хранения count что в худшем случае дает нам $O(n)$.

📝 Group Anagrams

📌 Задача:

Найти все анаграммы во входном списке и сгруппировать их.

❌ Изначальное решение и его проблемы 😕

Изначальное решение работает, но имеет следующие недостатки:

  • Сложность алгоритма: O(n² * k), где:
    • n — количество строк,
    • k — средняя длина строки.
  • Использование .count(): Этот метод вызывается для каждого символа в каждой строке, что увеличивает время выполнения.
  • Удаление элементов из списка: Метод .remove() требует дополнительной памяти

Логика работы:

Изначально создаем unchecked_list котрый хранит в себе все непроверенные слова из первоначального списка. Далее идем по strs и проверяем не вышло ли так, что уже все слова проверенны, если да то идем на выход. Если ещё не всё проверенно, но текущего слова нет в списке слов на проверку, то мы просто переходим к следующей итерации. Если нам не повезло и ни одна из проверок не дала нам пропустить текущее слово, то сначала мы делаем из слова частотный словар item_dict. Убираем текущее слово из списка не провереных, чтобы оно нам больше не мешало. И переходим к ещё одному циклу в котором проверяем оставшиеся на проверку слова, делаем из них такой же частотный словарь sub_dict и сравниваем его с item_dict, если совпало то добавляем в списко анаграм и убираем это слово из слов на проверку. В конце записываем полученную группу в конечный список result_list и выдаем его.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        result_list = []
        unchecked_list = strs.copy()

        for item in strs:
            anagram_list = []
            anagram_list.append(item)

            if len(unchecked_list) == 0:
                break

            if item not in unchecked_list:
                continue

            item_dict = {letter: item.count(letter) for letter in set(item)}
            unchecked_list.remove(item)

            for sub_item in unchecked_list:
                sub_dict = {letter: sub_item.count(letter) for letter in set(sub_item)}

                if item_dict == sub_dict:
                    anagram_list.append(sub_item)
                    unchecked_list.remove(sub_item)

            result_list.append(anagram_list)
        return result_list

✅ Оптимизированное решение 💡

Тут все прекрасно и решение само по себе очень красивое, разберу его по строчно так как оно мне очень понравилось.

class Solution:
    def bettergroupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for word in strs:
            counts = [0] * 26  # все буквы английского алфавита
            for char in word:
                counts[ord(char) - ord("a")] +=1
            key = tuple(counts)
            groups[key].append(word)

        return list(groups.values())

Тут мы создаем словар с помощью defaultdict(list) который позволяет при обращении к ключу которого в словаре нет, не выдавать ошибку как классический dict, а присваевать такому ключу пустой список:

groups = defaultdict(list)

Далее мы итерируем по strs и для каждого слова создаем список на 26 элементов, где каждый элемент изначально равен нулю. Из условия задачи, мы знаем что на вход подаются только слова из букв в нижнем регистре английского алфавита которых 26. counts мы будем использовать для хранения частоты появления букв в обрабатываемом на этом шаге word.

for word in strs:
            counts = [0] * 26

Далее мы итерируем по всем буквам в текущем word и с помощью ord(char) - ord("a") увеличиваем на один изначально нулевой счетчик букв в слове. Делается это следующим образом ord() преобразует входящий символ в Unix формат, условно a становиться равной 100, b = 101 и так далее, ord(char) - ord("a") позволяет нам определить индекс элемента списка counts соответствующего текущей буквые которую мы обрабатваем. Выходит, что ord(a) - ord("a") = 100 - 100, что соответствует 0 элементу списка, ord(b) - ord("a") = 101 - 100 = 1 и так далее, таким орбазом мы формируем частотный список для текущего слова

for char in word:
                counts[ord(char) - ord("a")] +=1

Далее конвертируем наш список в tuple чтобы сделать его ключом словаря и по этому ключу записываем наше слово в словарь. Для анаграм counts будет одинаковым и соответственно они будут записаны по одному ключу в один список, так мы и сформируем списки анаграм.

key = tuple(counts)
groups[key].append(word)

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n \cdot k)$

    • — первый цикл проходит по всем строкам, давая $O(n)$.
    • — второй цикл проходит по символам каждой строки, давая $O(k)$, где $k$ — максимальная длина строки.
    • — преобразование в кортеж tuple(counts) выполняется за $O(1)$.

  • 🧠 По памяти: $O(n \cdot k)$

    • — для каждого слова создается массив длиной 26, что занимает $O(1)$ памяти.
    • — для хранения всех групп в groups требуется $O(n \cdot k)$ памяти.

📝 Top K Frequent Elements

📌 Задача:

Дан целочисленный массив nums и целое число k. Верните k наиболее часто встречающихся элементов. Ответ можно вернуть в любом порядке.

✅ Решение

Решение этой задачи основано на bucket sort, ниже разберу решение задачи построчно.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        result = []
        counts = defaultdict(int)
        freq = [[] for _ in range(len(nums) + 1)]
        for num in nums:
            counts[num] +=1
        for key, value in counts.items():
            freq[value].append(key)
        for i in range(len(freq) - 1, 0, -1):
            for num in freq[i]:
                result.append(num)
                if len(result) == k:
                    return result
        return result

На первом шаге мы инициализируем список result - в который будем складывать ответ, частотный словарь counts, и список freq.

freq - ключевая фигура в работе нашего кода и в bucket sort, длина списка len(nums) + 1 - почему именно такая длина? freq будет хранить в себе элементы nums таким образом, что индекс элемента будет соответствовать частоте появления этого элемента в nums.

Так как index = 0 соответсвует часто те появления элемента 0, то такие элементы просто не появяться в списке nums, Следовательно длина freq должен быть длинной равной len(nums) + 1, так как в крайнем случае все элементы в nums будут встречаться уникальное количество раз + 1 под нулевой индекс.

Если nums = [1,3,3,3,6,7,7], то freq будет выглядить следующем образом:

Индекс (частота появления в nums) 0 1 2 3
Элемент ноль всегда пустой [1,6] [7] [3]

Этот подход похож на инвертированный подход, который использовался в Group Anagram.

result = []
counts = defaultdict(int)
freq = [[] for _ in range(len(nums) + 1)]

Далее мы заполняем частотный словарь counts и после заполняем freq согласно логике описаной выше, index - частоса появления элемента, freq[index] - список с элементами с частотой появление равной index.

for num in nums:
  counts[num] +=1
for key, value in counts.items():
    freq[value].append(key)

На последнем шаге мы просто итерируем по freq с конца, так как нам нужно вывести элементы с наибольшей частотой появления, а такие элементы лежат ближе всего к концу списка. Итерируем пока длина списка result не будет соответствовать k и мы, следовательно, не получим ответ.

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$

    • Проход по списку nums для подсчета частоты каждого числа требует времени $O(n)$, где $(n)$ — длина списка nums.
    • Создание списка freq также займет $O(n)$, так как мы создаем его размером (len(nums) + 1).
    • Преобразование словаря counts в список freq и добавление элементов в нужные списки занимает $O(n)$ времени.
    • Последний цикл, который обходит список freq и добавляет элементы в результат, в худшем случае может пройти по всем элементам в списке freq, но на самом деле мы не будем обходить все $(n)$ элементов, а только $(k)$ самых частых элементов, так что этот цикл работает за $O(n)$.

  • 🧠 По памяти: $O(n)

    • Мы используем дополнительную память для хранения:
      • Словаря counts — $O(n)$ для хранения каждого уникального числа и его частоты.
      • Списка freq — $O(n)$ для хранения списков всех чисел, частота которых варьируется от 0 до $n$.
      • Итоговый результат result может содержать до $k$ элементов, что дает дополнительную память $O(k)$, но эта величина будет всегда меньше или равна $n$, так что можно сказать, что сложность по памяти всё равно $O(n)$.

📝 Valid Parentheses

📌 Задача:

На вход подается строка содержащая только символы ( ), { }, [ ]. Необходимо проверить строку на правильность закрытия скобок.

✅ Мое Решение

Мое решение отходит от классического решения этой задачи, но я всё равно им горжусь.

Основная суть моего решения заключается в том, что если у нас есть открывающая скобка, то валидная закрывающая может находиться только в двух местах строки:

  1. Сразу после открывающей скобки: (){}
  2. Зеркально в строке: ({[]})

И такой подход работает, хоть при проверках моего решения нейросети очень долго пытались меня убедить в обратном из-за того, что мой подход не следует логике вложенности и закрытия/открытия скобок, а просто проверяет фиксированный места в строке. Единственный кому удалось подорвать мою уверреность в себе это leetcode когда я попытался заsubmit-ить свое решение и мой код споткнулся на строке, где были только закрывающие скобки )}. На таких строках я не получал не верного решения, я получал IndexError🙃. В принципе, эту обшибку можно было бы решить слегка доработав мой код, но на тот момент я уже убил пару часов пытаясь разобраться почему нейросети убеждают меня в неправильности моего кода и прогнал несколько десятков предложенных ими проверок (ни в одной проверке не было строки только с закрывающими скобками🥲).

def isValid_my(s: str) -> bool:
    breckit_dict = defaultdict(lambda: None)
    breckit_dict["("] = ")"
    breckit_dict["["] = "]"
    breckit_dict["{"] = "}"
    lenth = len(s)
    if lenth % 2 !=0:
        return False
    s_list = list(s)
    if not breckit_dict[s_list[0]]:
        return False
    for index, letter in enumerate(s_list):
        if breckit_dict[letter]:
            opposite_brecket = breckit_dict[letter]
            if s_list[index+1]!= opposite_brecket and s_list[len(s) - 1 - index]!=opposite_brecket:
                return False

    return True

Быстро пробегусь по своему коду, так как вдаваться в подробности не вижу смысла.

  1. Создаем breckit_dict с помощью defaultdict(lambda: None) так, чтобы при запросе ключа которого нет в словаре нам возвращался None.
  2. Далее заполняем наш словарь парами, breckit_dict[открывающая скобка] = закрывающая скобка
  3. Проверяем длинну нашей входной строки, если длинна не четное число, то сразу идем на выход так как невозможно образовать пары в такой строке.
  4. Дальше была небольшая агония с попыткой обработать IndexError, где я проверял не является ли первая скобка в строке закрывающей чтобы сразу пойти на выход, но на это не стоит обращать внимание.
  5. Дальше всё просто, идем по строке проверяя каждый символ является ли он открывающей скобкой, если да то сразу проверяем строку на предмет закрывающей скобки сразу после текущего символа и зеркально в строке, если всё окей то идем дальше, в противном случае выдаем ошибку.

✅ Решение(общепризнаное)

Как не удивительно, но суть решения задачи по стэкам в использовании стека👍

Как всегда, разберем решение по строчно:

def isValid(self, s: str) -> bool:
      bracket_dict = {')': '(', '}': '{', ']': '['}
      stack = []

      for bracket in s:
          if bracket in bracket_dict:
              if not (stack and stack.pop() == bracket_dict[bracket]):
                  return False
          else:
              stack.append(bracket)
      return not stack

И так, в начале мы создаем словарь breckit_dict[закрывающая скобка] = открывающая скобка. Так же создаем пустой стэк который в python будет просто списком.

bracket_dict = {')': '(', '}': '{', ']': '['}
stack = []

Далее итерируем по строке проверяя не является ли текущий символ закрывающей скобкой.

for bracket in s:
        if bracket in bracket_dict:

Чтобы лучше понять решение, сначала разберем случай когда нам попалась открывающая скобка. В такой ситуации мы просто записываем нашу скобку в стэк и идем дальше. То-есть для входной строки ({[]}) первый три шага будут выглядить так:

Шаг 0 1 2 3
stack [] ["("] ["(","{"] ["(","{","[",] 
else:
    stack.append(bracket)

Зафиксировали момент, что спустя три итерации наш стэк выглядит следующим образом stack = ["(","{","["]. На 4 шаге начинается всё самое интересное, текущем элементом становиться ] и она удовлетворяет условию if bracket in bracket_dict:. Теперь мы проверяем две вещи:

  1. Есть у нас что-то в стэке?
  2. Если мы сделаем stack.pop() - который удалит и вернет последний элемент нашего stack, то полученный элемент будет равен bracket_dict[текущий элемент]?

Если оба условия выполняются, то мы спокойно идем дальше, если нет, то возвращаем False.

if not (stack and stack.pop() == bracket_dict[bracket]):
    return False

В конце мы проверяем как там дела у нашего стэка, если строка пришла корректная, то согласно условиям вложенности скобок, мы отpop-или наш стэк так что он стал пустым и возвращаем True, а если что-то ещё осталось то возвращаем False.

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$

    • — Цикл по строке s займет $O(n)$, где $n$ — длина строки.
    • — Все операции с элементами стека и словаря выполняются за $O(1)$, включая проверку в словаре и операцию pop().

  • 🧠 По памяти: $O(n)$

    • — Словарь bracket_dict занимает $O(1)$ памяти, так как его размер не зависит от длины строки.
    • — Стек stack может в худшем случае хранить все открывающие скобки, что даст сложность по памяти $O(n)$.

📝 Min Stack

📌 Задача:

Разработайте стек, который поддерживает следующие операции с константной сложностью O(1):

MinStack() — инициализирует объект стека.
void push(int val) — добавляет элемент val в стек.
void pop() — удаляет верхний элемент из стека.
int top() — возвращает верхний элемент стека.
int getMin() — возвращает минимальный элемент в стеке.

Реализация должна обеспечивать O(1) время выполнения для каждой операции. Если по началу условие про O(1) пугает, то потом осознаешь, что это просто подсказка, так как тебе сразу говорят какие элементы тебе доступны.

За O(1) работает получение значения из словаря по ключу и получения элемента списка по индексу, и так как задачи у нас по стэкам, то выбор очевиден.

✅ Решение

Основная сложность этой задачи заключается в работе с минимальным элементом стэка, так как весь остальной функционал реализовать легко, а вот что делать с минимальным элементом и что делать если при вызове pop() удаленный элемент оказался минимальным?

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.min_stack:
            val = min(val, self.min_stack[-1])
        self.min_stack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Построчно разбирать код не вижу смысла, так как это у нас класс, то разберем его по методам которые нам интересны🔪.

И так __init__ - основная идея в этом методе это инициализировать два стэка(списка):

  1. self.stack = [] - стэк куда мы просто будем просто добавлять новые элементы.
  2. self.min_stack = [] - стэк в котором мы будем хранить иссторию минимальных элементов.
class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

Теперь перейдем к самому главному методу push, главный потому-что в его работе и заключается вся "магия" решения.

Получая новый элемент val на запись в наш стэк мы записываем его в основной стэк без каких-либо ухещрений,

А вот с min_stack немного повозимся, для начала проверяем, а существует ли min_stack вообще, если нет, то просто записываем val в наш стэк минимальных значений так как единственный элемент стэка у нас всегда будет и минимальным и максимальным элементом.

Если min_stack у нас существует, то мы сначала сравниваем val с последним элементом стэка, так как последний элемент стэка является минимальным на данный момент.

Если val < self.min_stack[-1], то мы просто записываем val в конец min_stack и val становиться новым минимальным элементом списка.

Если val > self.min_stack[-1], то мы записываем в конец min_stack ещё раз последний элемент min_stack тем самым отображая, что минимальный элемент не изменился.

Нарисуем табличку, чтобы лучше понять о чем идет речь:

Допустим на вход будем подовать поочередно следующий элементы: [1,2,0,1,-3]

stack [] [1] [1,2] [1,2,0] [1,2,0,1] [1,2,0,1,-3]
min_stack [] [1] [1,1] [1,1,0] [1,1,0,0] [1,1,0,0,-3]

Теперь вызовем три раза подряд pop() и getMin(), чтобы посмотреть что будет происходить.

pop() stack min_stack getMin()
0 [1,2,0,1,-3] [1,1,0,0,-3] -3
1 [1,2,0,1] [1,1,0,0] 0
2 [1,2,0] [1,1,0] 0
3 [1,2] [1,1] 1 
def push(self, val: int) -> None:
    self.stack.append(val)
    if self.min_stack:
        val = min(val, self.min_stack[-1])
    self.min_stack.append(val)

С методами pop(), top() и getMin() всё довольно просто и понятно.

  1. pop() - просто удаляем последний элемент у обоих стэков.
  2. top() - возвращаем последний элемент stack так как запись новых элементов идет в конец.
  3. getMin() - возвращаем последний элемент min_stack - он и есть минимальный на данный момент.
def pop(self) -> None:
    self.stack.pop()
    self.min_stack.pop()

def top(self) -> int:
    return self.stack[-1]

def getMin(self) -> int:
    return self.min_stack[-1]

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(1)$

    • — для выполнения условий задачи мы использовали только вставку в конец append() и удаление с конца списка pop() обе эти операции выполняются за $O(1)$.
    • — Все операции с элементами стека и словаря выполняются за $O(1)$, включая проверку в словаре и операцию pop().

  • 🧠 По памяти: $O(n)$

    • — из дополнительной памяти мы использовали список min_stack длинна которого равна stack

📝 Evaluate Reverse Polish notation

📌 Задача:

Дан массив строк tokens, представляющий арифметическое выражение в обратной польской нотации (Reverse Polish Notation, RPN).

Необходимо вычислить значение выражения и вернуть его в виде целого числа.

🔹 Примечания:

Допустимые операторы: '+', '-', '*', '/'.
Операнды могут быть как целыми числами, так и результатами других выражений.
Деление двух целых чисел округляется к нулю (отбрасываются дробные части).
Деления на ноль не будет.
Входные данные всегда представляют корректное выражение в обратной польской нотации.
Все результаты промежуточных вычислений и итоговый ответ помещаются в 32-битное целое число.

✅ Решение

Очень горжусь тем, что смог сам решить задачу уровня Medium, так ещё и хорошим способом🥳!

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operator_dict = {'+': lambda x, y: x + y,
                         '-': lambda x, y: y - x,
                         '*': lambda x, y: x * y,
                         '/': lambda x, y: int(y / x)}
        operand_list = []
        for token in tokens:
            if token in operator_dict:
                result = operator_dict[token](operand_list.pop(), operand_list.pop())
                operand_list.append(result)
            else:
                operand_list.append(int(token))
        return operand_list[0]

Разберем код детально, как обычно.

На первом шаге мы создаем словарь operator_dict, ключ - это один из математических операторов из условия задачи +, -, *, /, а значением будет lambda функция соответствующая ключу. На мой взгляд это самая тяжелая часть этой задачи, так как использование словаря сразу пришло мне в голову, а вот как связать ключи с реальными математическими действиями нет. На самом деле есть большое часло вариаций, как решить задачу с операторами, есть решения через if else, через встроенную библиотеку операторов и ещё несколько подходов которые я не запомнил.

operator_dict =         {'+': lambda x, y: x + y,
                         '-': lambda x, y: y - x,
                         '*': lambda x, y: x * y,
                         '/': lambda x, y: int(y / x)}

Можно немного задержать внимание на этой строчке:

'/': lambda x, y: int(y / x)

Тут я использовал int() для того, чтобы соблюсти условия задачи и правильно округлить результат деления. Понимаю, что решение через int() выглядит странным, но я пробовал и через round() и через //, но leetcode не принимал такое решения из-за того, что округление делалось не так как он задумывал🤨.

Спустя время я разобрался, что дело в том как python округляет отрицательные числа, округление идет в сторону -∞, а нам надо к нулю, int срабатывает потому-что просто, отбрасывает дробную часть🫡.

Дальше, как обычно, бывает в задачах по стэка, мы создаем стэк operand_list и итерируем по входному списку tokens, проверяя является ли текущий эелемент ключом operator_dict или это цифра.

Если нам попалась цифра, то мы просто записываем её в наш стэк, не забыв конвертировать в int и идем дальше.

Если мы наткнулись на оператор, то вызываем соответствующую функцию из нашего словаря operator_dict и используем в качестве аргумента два последних элемента списка полученых через pop() - что избавляет нас от запроса этих элементов по индексу и гарантирует, что мы использованые аргументы из списка удалим. Результат работы записываем в конец нашего стэка.

На выходе просто выводим первый элемент стэка так как к концу работы функции у нас должен был остаться один элемент в стэке являющийся ответом.

operand_list = []
for token in tokens:
    if token in operator_dict:
        result = operator_dict[token](operand_list.pop(), operand_list.pop())
        operand_list.append(result)
    else:
        operand_list.append(int(token))
return operand_list[0]

Задача мне показалась слишком легкой для среднего уровня, если честно, даже не вижу смысла разбирать ее с помощью табличек.

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$
    • — итерация по списку tokens займет $O(n)$, отсальные операции (pop(), append()) константы $O(1)$.
  • 🧠 По памяти: $O(n)$
    • — из дополнительной памяти мы использовали operator_dict длинна которого не зависит от tokens и займет $O(1)$
    • — список operand_list используется для хранения операндов, и в худшем случае его длина будет $O(n)$ (когда все токены являются операндами и еще не было выполнено ни одной операции). В итоге память, используемая для хранения операндов, составляет $O(n)$.

📝 Merge Sorted Array

📌 Задача:

Даны два целочисленных массива nums1 и nums2, отсортированные в неубывающем порядке, а также два числа m и n, обозначающие количество элементов в nums1 и nums2 соответственно.

Необходимо объединить nums1 и nums2 в один массив, отсортированный в неубывающем порядке.

Функция не должна возвращать отсортированный массив, вместо этого результат должен быть сохранён внутри массива nums1. Для этого nums1 имеет длину m + n, где первые m элементов содержат значения, подлежащие объединению, а последние n элементов равны 0 и должны быть проигнорированы. Массив nums2 имеет длину n.

✅ Решение

Весьма смешанные чувства по поводу этой задачи.

Во-первых, эта задача совсем не показалась на уровень Easy, скорее Medium. Возможно, дело в том, что тут используется одна из базовых сортировок, но если ты её забыл, то прийти к решению не очень легко.

Во-вторых, я ознакомился где-то с 4-5 разными подходами и все они мне не показались в достаточной мере питоновскими, не хватает им красоты и элегантности.

В ходе поиска решения которое больше бы удовлетворило меня, я решил посмотреть как решают эту задачу на C++. И решение на C++ показалось мне чуть более элегантным, чем класическое решение на python, так что я отказался от распространеннго решения на python и адоптировал С-ишное.

Вот самое распространеное решение от питонистов:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, k = m - 1, n - 1, m + n - 1  

        while i >= 0 and j >= 0:  
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1  

        
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

А вот решение C++ которое я адаптировал на python:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1 = m -1
        p2 = n - 1
        i = m + n - 1
        while p2 >= 0:
            if p1 >=0 and nums1[p1] > nums2[p2]:
                nums1[i] = nums1[p1]
                i -= 1
                p1 -= 1
            else:
                nums1[i] = nums2[p2]
                i -= 1
                p2 -= 1

Скорость и затраты по памяти одни и те же, но симпатичнее же💅!

Теперь разберем решение!

Сначала разберем логику, а затем перейдем к коду. И так, представим что на вход нам подается nums1 = [1, 2, 4, 0, 0, 0] и m = 3, nums2 = [2,5,6] и n=3. Пока забудем про m и n, так как для понимания логики они не нужны.

Мы будем итерировать с конца nums2 с указателем p2 и с конца значимых элементов nums1 с указателем p1 (нули мы не учитываем, по условию задачи).

num1 1 2 4 0 0 0
p1 🔼
p2 🔽
num2 2 5 6

На первом шаге мы сравниваем последний (максимальный) элемент nums1 и последний (максимальный) элемент nums2, 6 > 4 и мы просто записываем максимальный элемент nums2 в конец nums1.

num1 1 2 4 0 0 6
p1 🔼
p2 🔽
num2 2 5 ✅

На втором шаге мы сравниваем последний (максимальный) элемент nums1 и последний (максимальный) элемент nums2, 5 > 4 и мы просто записываем максимальный элемент nums2 в конец nums1.

num1 1 2 4 0 5 6
p1 🔼
p2 🔽
num2 2 ✅ ✅

На третьем шаге мы сравниваем последний (максимальный) элемент nums1 и последний (максимальный) элемент nums2, и тут оказывается что 2 < 4. В таком случае мы двигаем 4 вправо и сравниваем 2 со следующим элементом nums1.

num1 1 2 0 4 5 6
p1 🔼
p2 🔽
num2 2 ✅ ✅

На последнем шаге 2=2 поэтому просто записываем 2 из nums2 в последнее свободное местов в nums1.

num1 1 2 2 4 5 6
p1 🔼
p2 🔽
num2 ✅ ✅ ✅

Вот мы и слили два отсортированных списка😎!

Теперь пройдемся по коду. Напомню как он у нас выглядит:

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1 = m -1
        p2 = n - 1
        i = m + n - 1
        while p2 >= 0:
            if p1 >=0 and nums1[p1] > nums2[p2]:
                nums1[i] = nums1[p1]
                i -= 1
                p1 -= 1
            else:
                nums1[i] = nums2[p2]
                i -= 1
                p2 -= 1

В начале мы инициализируем три указателя.

  1. p1 - указатель для значимых числе в nums1
  2. p2 - указатель для чисел в nums2
  3. i - указатель на конец nums1.
p1 = m -1
p2 = n - 1
i = m + n - 1

Далее объявляем цикл, который будет работать, пока мы не разпихаем все числа из nums2 в nums1.

while p2 >= 0:

В нутри цикла мы проверяем не дошли ли мы до конца nums1, и сравниваем максимальные числа двух списков.

if p1 >=0 and nums1[p1] > nums2[p2]:

Если последний элемент nums1 оказывается больше последнего элемента nums2, то мы сдвигаем текущий элемент nums1 в конец, обновляем указатели i и p1, чтобы перейти к следующему элементу nums1.

nums1[i] = nums1[p1]
i -= 1
p1 -= 1

В противном случае мы записываем максимальный элемент из nums2 в крайнее свободное место в nums1, и перемещаем указатели i и p2, чтобы перейти к следующему числу nums2.

else:
    nums1[i] = nums2[p2]
    i -= 1
    p2 -= 1

Звучит запутанно и не очень похоже на подход который я опысывал с помощью табличек, но на самом деле это тот же подход, просто как во многих задачах тут сначала идут от обратного, проверяя что крайний элемент nums2 меньше крайнего элемента nums1.

📝 Remove Duplicates from Sorted Array

📌 Задача:

Дан целочисленный массив nums, отсортированный в неубывающем порядке. Необходимо удалить дубликаты на месте, так чтобы каждый уникальный элемент встречался только один раз. При этом относительный порядок элементов должен сохраняться. Затем вернуть количество уникальных элементов в nums.

Обозначим количество уникальных элементов как k. Чтобы решение было принято, необходимо выполнить следующие условия:

Изменить массив nums так, чтобы первые k элементов содержали уникальные элементы в том же порядке, в котором они изначально встречались в nums.

Остальные элементы массива не имеют значения, как и его итоговый размер.

Вернуть k.

✅ Решение

Указатели это моя боль, каждая задача дается тяжело, а разбор писать ещё тяжелее😬.

Думаю я откажусь от разбора самого кода в задачах по этой теме (в этот раз точно), так как код не сложный, а вот про логику я такого сказать не могу🧐.

И так решение.

Прдеставим что на вход подается nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4].

Для решения задач с указателями нам понадобиться указатель и даже два🤓.

  • pointer_1 - который будет просто идти по списку
  • pointer_2 - будет сохранять позицию доступную для записи уникального элемента.

pointer_2 будет стартовать не сначала списка (индекс=0), а с индекса 1, так как в отсортированно массиве первый элемент по умолчанию будет уникальным.

  • Шаг 1

В начале перенесем наш pointer_1 на элемент с индексом 1, это нужно чтобы мы могли сравнивать текущий и предидущий элемент и сделать вывод об их уникальности или не уникальности (напомню, массив у нас отсортированый).

На первом шаге мы сравниваем nums[pointer_1 - 1] == nums[pointer_1], что равно nums[0] == nums[1], что равно 0=0, pointer_2 - мы в самом начале поставили в позицию 1 и пока не трогаем. Элементы nums[pointer_1 - 1] и nums[pointer_1] действительно равны, так что мы пока ничего не делаем и идем дальше.

nums 0 0 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 2

На втором шаге мы уже сравниваем nums[1] и nums[2], то есть сравниваем 0 и 1.

nums 0 0 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼

Эти элементы оказываются не равны и тут начинается самое интересное. Мы записывае в индекс на который указывает pointer_2 новый уникальный элемент:

nums 0 1 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼

Смещаем pointer_2 на один.

nums 0 1 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼

Следующие несколько шагов ничего интересного не происходи и мы просто идем по списку.

  • Шаг 3
nums 0 1 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 4
nums 0 1 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 5

На шаге 5 мы опять сталкиваемся с новым элементом и проделываем всё то же самое, что делали на шаге два.

nums 0 1 1 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  1. Записываем уникальный элемент на место в списке куда указывает pointer_2
  2. Сдвигаем pointer_2 на один шаг.
nums 0 1 2 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 6

На шаге 6 ничего интересного не происходит

nums 0 1 2 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 7

На этом шаге нам вновь встречается уникальный элемент:

nums 0 1 2 1 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼

И мы делаем уже хорошо знакомые действия:

  1. Записываем уникальный элемент на место в списке куда указывает pointer_2
  2. Сдвигаем pointer_2 на один шаг.
nums 0 1 2 3 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 8

На этом шаге ничего интересного.

nums 0 1 2 3 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Шаг 9

Новый, а главное последний элемент🥳!!!

nums 0 1 2 3 1 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼
  • Записываем
  • Сдвигаем
nums 0 1 2 3 4 2 2 3 3 4
p1 🔼
p1-1 🔼
p2 🔼

И вот мы прошли по нашему nums, пора дать ответ. Колличество уникальных элементов будет соответствовать индексу в котором окзался pointer_2, в нашем случае это 5 индекс, что соответствует правельному ответу!

Так же нас попросили изменить nums так чтобы в начале шли уникальные элементы в отсортированном порядке, а в конце может валяться мусор который остался.

И вот как выглядит наш nums после всех манипуляций:

[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]

Как видите всё как нужно!🤯

А вот и наш код:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        k = 1
        for index in range(1, len(nums)):
            if nums[index] != nums[index-1]:
                nums[k] = nums[index]
                k += 1

        return k

Как-то так.

📝 Move Zeroes

📌 Задача:

Дан целочисленный массив nums. Переместите все нули в конец массива, сохранив относительный порядок ненулевых элементов.

Обратите внимание, что необходимо выполнить операцию на месте (in-place), не создавая копию массива.

✅ Решение

Как и во многих алгоретмических задачах решение кроется в правильном прочтении условия.

Тут решение находится довольно быстро, если смотреть на задачу не с точки перемещения нулей в конец массива, а с перемещения ненулевых чисел в начало. Для решения задачи нам потребуются два указателя, кто бы мог подумать 🤷‍♂️.

Создаем два указателя:

  • slow - указывает на место куда нужно вставить следуеще ненулевое число. Изначально находится в начале массива.
  • fast - итерирует по массиву.

Представим что на вход у нас поступил такой массив nums = [0, 1, 0, 3, 12].

  • Шаг 1

На первом шаге мы сначала проверяем является ли числом отличным от нуля число на которое указывает указатель fast.

nums 0 1 0 3 12
fast 🔼
slow 🔼

В данном случае число действительно является нулем и нам тут делать нечего, идем дальше.

  • Шаг 2

Опять проверяем число на которое указывает fast и в этот раз это не ноль!

nums 0 1 0 3 12
fast 🔼
slow 🔼

В таком случае, мы просто меняем местами число на которое указывает fast с числом на которое указывает slow и сдвигаем slow на 1.

nums 1 0 0 3 12
fast 🔼
slow 🔼

Такая картина у нас получается, идем дальше.

  • Шаг 3

fast указывает на 0, так что просто идем дальше.

nums 1 0 0 3 12
fast 🔼
slow 🔼
  • Шаг 4

На этом шаге fast нашел ненулевое число.

nums 1 0 0 3 12
fast 🔼
slow 🔼

Меняем местами числа fast и slow и сдвигаем slow.

nums 1 3 0 0 12
fast 🔼
slow 🔼
  • Шаг 5

Опять ненулевое число от fast и последнее в массиве. Делаем всё те же действия, что и на предыдущем шаге.

nums 1 3 12 0 0
fast 🔼
slow 🔼

Вот и всё, задача решена 😎!

Дам несколько комментариев по поводу кода, так как там есть один момент который не удалось затронуть в разборе.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        for fast in range(len(nums)):
            if nums[fast]:
                if not nums[slow]:
                    nums[slow], nums[fast] = nums[fast], 0
                slow += 1
        return

Момент на который я хотел обратить внимание вот тут:

if not nums[slow]:
    nums[slow], nums[fast] = nums[fast], 0
slow += 1

Перед тем как поменять местами nums[fast] и nums[slow], мы проверяем чтобы slow указывал на ноль, что логично. Но в независимости от того, совершили мы перестоновку или нет, мы всё равно сдвигаем slow. Это делается для того, чтобы не поменять местами два не нулевых числа, что сломало бы последовательность и дало бы неверный ответ.

На этом можно закончить с этой задачей.

📝 Valid Palindrome

📌 Задача:

Фраза считается палиндромом, если после приведения всех букв к нижнему регистру и удаления всех неалфавитно-цифровых символов она читается одинаково слева направо и справа налево. Алфавитно-цифровыми считаются буквы и цифры.

Дана строка s. Необходимо вернуть true, если она является палиндромом, и false в противном случае.

✅ Решение

Не вижу смысла вдаваться в детали этой задачи, мы просто инициализируем два указателя:

  • left - идет сначала массива в его конец
  • right - идет с конца в начало

На каждом шаге сравниваем символы на которые ссылаются указатели и так идем до середины строки, если по пути символы вдруг не совпали, то выдаем False, если прошли и всё окей, то возвращаем True.

С кодом тут тоже ничего интересного:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(filter(str.isalnum, s)).lower()

        for left in range(len(s)//2):
            if s[left] != s[len(s) - 1 - left]:
                return False
        return True

Строчка с перобразованием строки в коде пожалуй самая интересная и на мой взгляд это самое сложное, что есть в этой задаче.

s = ''.join(filter(str.isalnum, s)).lower()

Есть варианты через re.sub() и я сам инначально такой подход использовал s = re.sub(r'[^a-zA-Z0-9]', '', s).lower(), но позже отказался так как через фильтр быстрее. Видел вариант, где человек отказался от гениратора и вообще не преобразовывал строку, разве что lower() использовал, и реализовал логику isalnum() с помощью ord(), но такие подходы уже для совсем интузиастов на мой взгляд.

Изначально я явно инициализировал указатель right и двигал его в теле цикла, позже отказался от этого просто, чтобы использовать меньше памяти.

s[left] != s[len(s) - 1 - left]

Больше ничего интересного про эту задачу рассказть не могу🫤.

📝 Container With Most Water

📌 Задача:

Вам дан целочисленный массив height длины n. Нарисованы n вертикальных линий таким образом, что концы i-й линии находятся в точках (i, 0) и (i, height[i]).

Найдите такие две линии, которые вместе с осью X образуют контейнер, способный удержать наибольшее количество воды.

Верните максимальный объём воды, который может вместить такой контейнер.

Обратите внимание: контейнер нельзя наклонять.

✅ Решение

Опять инициализируем два указателя идущих на встречу друг-другу, так же создаем переменную max_area которая будет хранить максимальную площадь на текущем шаге.

def maxArea(self, height: List[int]) -> int:
    max_area = 0
    left = 0
    right = len(height) - 1

На каждом шаге мы расчитываем площадь контейнера и сравниваем ее с max_area. Если площадь оказывается больше значения переменной, то присваеваем переменной новое значение.

current_area = self.area_formula(left, right, height)
max_area = max(max_area, current_area)

Далее сдвигаем тот указатель, который указывает на меньшую высоту. Выбираем именно меньший указатель, так как по его высоте мы расчитываем площадь контейнера. Все что будет выше просто выльется из нашего контейнера из-за меньшей стенки.

if height[left] < height[right]:
    left += 1
else:
    right -= 1

В конце просто отдаем max_area. Ниже представлен весь код.

class Solution:
    @staticmethod
    def area_formula(x: int, y: int, l: List[int]) -> int:
        return min(l[x], l[y]) * (y - x)

    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        left = 0
        right = len(height) - 1

        while left < right:
            current_area = self.area_formula(left, right, height)
            max_area = max(max_area, current_area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

Я вынес формулу расчета площади в отдельную функцию, чтобы не загромождать код.

Работа цикла идет до тех пор, пока у нас не пересекуться два указателя.

⏳ Сложность 🧠

  • ⏳ Временная сложность: $O(n)$
    • — итерация по списку займет $O(n * 0,5)$ - так как мы идем до половины списка с двух концов, но константой пренебригаем, так что $O(n)$
    • отсальные операции константы $O(1)$.
  • 🧠 По памяти: $O(1)$
    • — из дополнительной памяти мы использовали max_area, left, right длинна которых не зависит от height и займет $O(1)$

About

Коллекция решений задач с LeetCode на Python.

Resources

Readme
Activity

Stars

4 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

1 tags

Packages

 
 
 

Contributors

Languages