✅ РЕШАЕМ 200 задач на LeetCode

Сначала выкладывается задача с подсказкой, затем решение с основной идеей

Цель — наработать базу алгоритмических задач для прохождения собеседований в крупные компании:
FAANG, Yandex, Sber, Ozon, VK и другие

Старт 1 июля

Задача уровня 🟢 Easy
1. Two sum

Подсказка: используйте HashMap для решения за O(n)

1/200
#easy
#leetcode1

Стартуем марафон с классической и самой первой задачи на LeetCode
Тем не менее, ее всё ещё спрашивают на собеседованиях, а позже мы разберем усложненную версию этой задачи, которую была на реальном собеседовании в Yandex

Задача уровня 🟢 Easy
217. Contains Duplicate

Подсказка: используйте HashSet для решения за O(n)

2/200
#easy
#leetcode217

✅ Решение задачи 1

Time: O(n)
Space: O(n)

📝 Идея
Проходимся по массиву, проверяя за O(1) есть ли в map нужный ключ (taget - nums[i]), при этом пока не найдем нужную пару, сохраняем в map (значение массива - индекс)

#solution1

✅ Решение задачи 217

Time: O(n)
Space: O(n)

📝 Идея
Проходимся по массиву, проверяя за O(1) содержится ли в set данный элемент, при этом сохраняем этот элемент для дальнейших проверок

#solution217

Задача уровня 🟢 Easy
242. Valid Anagram

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

Подсказка: строки s и t состоят только из строчных букв, как можно использовать массив решения задачи?

3/200
#easy
#leetcode242

Задача уровня 🟡 Medium
49. Group Anagrams

Пример:

Input: ["eat","tea","tan","ate","nat","bat"]

Output: 
[["bat"], ["nat","tan"], ["ate","eat","tea"]]

Подсказка: что подойдет в качестве ключа в HashMap?

4/200
#medium
#leetcode49

✅ Решение задачи 242

Time: O(n)
Space: O(1)

📝 Идея
Используя код символа строки (с - 'a') получаем значение индекса массива и увеличиваем на единицу для строки S, для строки T уменьшаем на единицу
В итоге если массив весь в нулях - значит количество букв в обоих строках одинаково

#solution242

✅ Решение задачи 49

Time: O(n*klog(k))
Space: O(n)

📝 Идея
Для решения используем HashMap, в качестве пары ключ-значение используем отсортированную строку и ArrayList
Если раньше не встречалось данное отсортированное слово - просто создаем новый ArrayList, далее все строки складываем к своим ключам

#solution49

🟡 Medium
347. Top K Frequent Elements

Пример:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Подсказка: что если сгруппировать значения по частоте появления?

5/200
#medium
#leetcode347

🟡 Medium
238. Product of Array Except Self

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Подсказка: как можно использовать префиксные и суффиксные произведения?

6/200
#medium
#leetcode238