Решение алгоритмов с LeetCode

Всем привет!

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

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

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

Возможные обновления

Возможно, обновления в репозитории будут появляться не очень часто. Это связано с тем, что мои текущие навыки в решении алгоритмов ещё требуют улучшения. Также основная работа и занятость отнимают значительную часть времени, поэтому прогресс может идти медленнее, чем хотелось бы. Но я буду стараться регулярно решать задачи и делиться ими здесь.

Как использовать

• Откройте файлы с кодом, чтобы увидеть мои решения задач с LeetCode.
• В директории result/ также находятся скриншоты успешных решений.

Оставайтесь на связи и следите за обновлениями!

Пример задачи: Two Sum

Пример задачи: Palindrome Number

Задача может быть сложно читаемая, так как я пытался оптимизировать скорость выполнения с 60ms до 46ms хотя бы
Изначально решение было более читаемым

Пример задачи: Roman to Integer

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

Пример задачи: Longest Common Prefix

Я особенно горжусь решением этой задачи, потому что оно выполняется за минимальное время, хотя по памяти не выигрывает. Однажды, поздно ночью, лежа в кровати, я задумался о том, чем руководствуюсь, когда мысленно решаю задачу без использования кода. Я проанализировал свои логические шаги и понял, как именно нахожу решение, просто глядя на данные. Сначала я мысленно определяю количество строк в списке. Затем беру символ из первой строки и поочередно сравниваю его с символами на тех же позициях в остальных строках. Если символ совпадает во всех строках, я запоминаю его и перехожу к следующему символу. Если хотя бы в одной строке символ не совпадает, то нет смысла продолжать проверку, и я отбрасываю его. После этого остается лишь вывести те символы, которые я запомнил. В данном случае счётчиком выступает переменная count, которая соответствует длине списка. Этот процесс можно назвать ментальной моделью решения задачи, где я сознательно выстраиваю в голове последовательность шагов, основанных на логике и наблюдениях, чтобы прийти к правильному решению.

Пример задачи: Valid Parentheses

Данная задача мне далась достаточно сложно, т.к я не понимал примерной хотя бы логики решения. Но я помнил, что раньше в этой задаче я использовал стек, но всё равно мне это не помогло сейчас, в итоге я решил просто почитать статьи (без готового кода) и после прочтения первых пары строк я понял принцип, сейчас я его опишу: Я создал словарь где ключами были закрывающие скобки, а значения открывающие. Дальше создал стек. После этого в цикле начал проходить и если данный символ находился в значениях моего словаря, значит скобка открывающая и я помещал её в стек и через continue шел дальше по строке, как только я встречал скобку которой нет в значениях словаря - значит она закрывающая, и если стек не пустой я проверял совпадает ли значение ключа закрывающей скобки со значением которое я возвращал через метод "pop", если да, то снова через continue я шел дальше по строке, если не совпадали - значит нарушена структура скобок и возвращаем False. Ну и в самом конце, после цикла я проверял стек, если он пустой return True else False

Пример задачи: Merge Two Sorted Lists

Долго меня не было на литкоде, сегодня появилось время и решил сразу же зайти порешать задачки. Тут пришлось обратиться за помощью, так как я не понимал, что именно тут нужно сделать. Оказывается ListNode не является итерируемым, а вместо этого он содержит значение (val) и ссылку на следующий узел (next). Мне это объяснили на примере поездов с вагончиками, что-то вроде отложилось в голове, но всё равно с нуля без помощи я так быстро это не решу

Пример задачи: Remove Duplicates from Sorted Array

Сначала долго не мог понять, что не так в моём решении, когда я просто убрал дубликаты из списка. Оказывается нужно убирать дубликаты изменяя сразу имеющийся список, не создавая новый. Буду честен с идеей возможной реализации мне дали совет: "Использовать курсоры, чтобы работать с индексами". Поэтому суть моего решения оказалась таковой:

• Я создал курсор 'j', который отвечает за последний уникальный элемент в списке, изначально его значение равно 0, так как первый элемент в списке всегда уникален.
• Дальше в цикле через 'range' я проходился по списку 'nums', начало цикла было с первого индекса, так как нулевой уже определён.
• В теле цикла реализована проверка, если значение 'nums[j] == nums[j]', то делать ничего не нужно и мы пропускаем эту итерацию при помощи 'continue'
• Если значения не равны, значит мы поймали уникальное число (в данном случае). Мы инкрементируем значение 'j'
• После инкрементации мы выполняем замену чисел по индеку nums[j] = nums[i].
• Тем самым если наше значение j=1 мы обращаемся по этому индексу к nums и присваиваем ему значение nums[i]

Пример задачи: Remove Element

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

• Создал курсор k - указывающий кол-во так же уникальных элементов, так же в будущем он нам пригодится, чтобы уникальные значения сохранять в начале списка.
• В цикле проходимся по длине массива по индексам, если значение уникально, то записываем его в начало списка, благодаря нашему курсору и инкрементируем его.
• Потом можно сделать вывод по срезу, чтобы получить все значения, кроме таргета nums = nums[:k] ( но я решил это опустить, так как все тесты прошли на литкоде)

Пример задачи: Find the Index of the First Occurrence in a String

Туу объяснения не нужны, я так думаю))

Пример задачи: Search Insert Position

Пример задачи: Length of Last Word

В этой задаче я использовал два подхода: Первый:

• Убрал лишние пробелы

• Засплитил строку по пробелам, чтобы сформировать список

• Нашел длину последнего индекса в списке

• Второй:

• Так же убрал лишние пробелы

• Отказался от сплита, чтобы разгрузить код

• Т.к мы знаем, что работаем только с последним словом, запускаем цикл по перевёрнутой строке, с помощью метода reversed

• Если встречаем пробел - цикл останавливается

• Иначе через счётчик count считаем какая длинна строки