Уже достаточно знаний, чтобы начать решать простые задачи на leetcode.

Но если вы хотите отправлять свои решения на тестирование на самом leetcode, то стоит дать немного вводной информации.

Во первых, зарегистрируйтесь на leetcode.com.
Во вторых, мы ещё не проходили функции, но пока можно разобраться без этих знаний.
Например возьмем первую задачу https://leetcode.com/problems/two-sum/
Слева описание задания с парой примеров, а справа поле, где мы будем писать свое решение.
В нашем случае надо выбрать язык программирования python3 или другой, если будете решать на чем-то другом.

#ps_leetcode

Теперь можно разобрать первую задачу:
1. Two Sum (легкая)
leetcode.com/problems/two-sum

Вы получаете список целых чисел nums и число target.
Надо вернуть список из 2-х индексов чисел из списка, которые в сумме дают target.
Такая комбинация встречается 1 раз.
Вернуть числа можно в любом порядке

Пример 1:Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Пример 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Пример 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

3-ий вопрос:
Что может быть ключом в словаре?
Ответить можно, что ключом может быть неизменяемый тип.

Почему?
Дело в том, что если у нас будет 2 ключа - списки, тогда теоретически мы сможем их изменить до одинакового состояния и у нас в словаре получится 2 одинаковых ключа, таким образом когда мы попытаемся по ключу достать значение, словарь не будет знать, что нам вернуть.

Может ли кортеж или другой контейнерный тип быть ключом в словаре?
Ответ тут будет и да и нет.

Если у нас будет кортеж, в котором будут только неизменяемые переменные, например:
(1, "my_str", (1, 2)) - то, все ок, он может быть ключом.
Но если у нас будет кортеж, в котором будет хоть один изменяемый тип, то он уже не сможет быть ключом в словаре, например:
(1, "my_str", [1, 2]) - содержит список, и не может быть ключом.

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

все вопросы
#ps_question

Сегодня разберем вторую задачу из порядка 300, которые необходимо решить)
2. Сontains duplicate (легкая)
leetcode.com/problems/contains-duplicate

Дан список чисел nums, если все числа в списке уникальны, то надо вернуть False, а если хоть одно число повторяется, то надо вернуть True.

Пример 1:
Input: nums = [1,2,3,1]
Output: true

Пример 2:
Input: nums = [1,2,3,4]
Output: false

Пример 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

4-ий вопрос:
В чем разница между списком и словарем?
Список в python это массив данных, словарь, это ключ-значение. Можно провести аналогию, что в словаре это ключ-значение, а список - это индекс-значение. Разница в сложности вставки элемента в список/словарь, удаления и поиска.

Сложность поиска элемента в списке - O(n), в словаре O(1). Но тут надо уточнить, что если мы хотим получить элемент из списка по индексу, то сложность будет O(1), т.к. в памяти компьютера элементы списка находятся подряд и python знает на сколько надо сделать сдвиг, чтобы попасть на нужный элемент.
Чтобы найти элемент в списке в худшем случае мы пройдемся по всему списку, размером n, значит сложность будет О(n).
Но чтобы найти ключ в словаре и получить по нему значение, надо ключ пропустить через хэш функцию, которая вернет что-то похожее на индекс таблички, где хранятся значения и уже по этому индексу мы получим значение, которое привязано к ключу. Сложность всего этого О(1).

Чтобы вставить элемент в список, т.к. в памяти значения идут подряд, надо вставить элемент и все остальные сдвинуть на 1. Получается, что если мы вставим значение в начало списка, то надо будет сделать n операций, чтобы подвинуть все элементы. Сложность О(n). Сложность ставки в словарь - О(1), то есть просто пропускаем ключ через хэш функцию и устанавливаем значение в нужную ячейку.

Про удаление из списка уже можно догадаться, что в словаре пропускаем через хэш ф-ию ключ и удаляем ненужный элемент, сложность О(1). А в списке, если мы удалим элемент в начале списка, то все элементы надо будет сдвинуть, чтобы убрать пробел, сложность О(n).

Как правило так подробно рассказывать не нужно, но знать надо, обычно достаточно сказать, что у списка сложность О(n), а словаря О(1)

все вопросы
#ps_question

Как видно знание хэш таблиц жизненно необходимо, чтобы продержаться на собеседовании первые 5 минут).
Поэтому про них будет отдельный пост и тут мы уже затронули сложность алгоритмов, про них тоже в ближайшее время сделаю отдельный пост. Тема сложности алгоритмов на самом деле простая, если мы её будем разбирать с точки зрения собеседований и литкод задач.

Воскресная задачка.
3. Valid Anagram (легкая)
leetcode.com/problems/valid-anagram
Имеется 2 строки s и t, вернуть True, если t является анаграммой s и False в противном случае.

Анаграмма - это слово или фраза образованная путем перестановки букв другого слова или фразы обычно с использованием всех исходных букв ровно 1 раз.

Пример 1:
Input: s = "anagram", t = "nagaram"
Output: true

Пример 2:
Input: s = "rat", t = "car"
Output: false

def isAnagram(s, t):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Мы уже начали заходить в тупик, т.к. измерение сложности алгоритмов сопровождает программиста повсюду (при работе). Поэтому пришло время разобрать, что это такое, чтобы комфортно двигаться дальше.
Сложность алгоритмов (О большое)

Воскресная задачка.
4. Top K Frequent Elements (средняя)
leetcode.com/problems/top-k-frequent-elements
Имеется список чисел nums, необходимо вернуть k наиболее часто встречающихся элементов. Порядок не важен.

Пример 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Пример 2:
Input: nums = [1], k = 1
Output: [1]

def topKFrequent(nums, k):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Методы для работы со списками.
Подумайте, какая может быть сложность у каждого метода и напишите, у каких методов сложность О(1) или может быть О(1) при определенных условиях.

Оглавление
#ps_base

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

Оглавление
#ps_base

Чтобы подготовиться к завтрашней задаче, надо разобраться, что такое стек.

Стек
Подумайте, как можно реализовать стек из того, что мы уже знаем? Можно конечно написать свой класс и реализовать все эти методы, а информацию как-то хранить внутри. Но классы ещё не проходили, как без них реализовать?
Ещё учтите, что все операции со стеком должны производиться за О(1).

Воскресная задачка.
5. Valid Parentheses (легкая)
leetcode.com/problems/valid-parentheses
Получаем строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, валидна ли эта строка.
Эта строка валидна, если:
- Открытые скобки должны быть закрыты однотипными строками
- Открытые скобки должны быть закрыты в правильном порядке
- Каждой закрывающей скобке соответствует открытая скобка того же типа

Пример 1:
Input: s = "()"
Output: true

Пример 2:
Input: s = "()[]{}"
Output: true

Пример 3:
Input: s = "(]"
Output: false

def isValid(s):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Чтобы закрепить, как реализовать стек в python, самым простым способом, приведу табличку с эквивалентными методами. Также добавлю её в основной пост про стек.
Стек

Добиваем работу со списками. Альтернативные способы работы со списками

Оглавление
#ps_base