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

1 - Two sum
2 - Add two numbers
3 - Longest Substring Without Repeating Characters
4 - Median of Two Sorted Arrays
5 - Longest Palindromic Substring
10 - Regular Expression Matching
11 - Container With Most Water
15 - 3Sum
33 - Search in Rotated Sorted Array
53 - Maximum Subarray
121 - Best Time to Buy and Sell Stock
152 - Maximum Product Subarray
153 - Find Minimum in Rotated Sorted Array
217 - Contains Duplicate
238 - Product of Array Except Self

По сложности

#easy
#medium
#hard

По темам и методам решения

#strings
#arrays
#linkedlists
#dp
#divideandconquer
#twopointers
#hashtable
#prefixsum

#ретро

Blind 75. Arrays

Небольшое ретро по задачкам из раздела Массивы:

1 - Two sum (easy)
11 - Container With Most Water (medium)
15 - 3Sum (medium)
33 - Search in Rotated Sorted Array (medium)
53 - Maximum Subarray (medium)
121 - Best Time to Buy and Sell Stock (easy)
152 - Maximum Product Subarray (medium)
153 - Find Minimum in Rotated Sorted Array (medium)
217 - Contains Duplicate (ease)
238 - Product of Array Except Self (medium)

Какие подходы к решению использовались:

👉 Два указателя (#twopointers)

Используется, когда "второй" элемент всегда идет после "текущего". Часто используется для отбора последовательно идущих элементов, которые в комбинации соответствуют определенному условию.

- два/три элемента, составляющие определенную сумму (Two sum, 3Sum)
- две линии, составляющие прямоугольник наибольшей площади (Container With Most Water)
- две даты, между которыми акция росла больше всего (Best Time to Buy and Sell Stock)

👉 Хеш-таблица (#hashtable)

Используется для быстрого доступа к элементам массива (элементы массива становятся ключами хеш-таблицы).

- Быстро найти второе слагаемое для известной суммы и первого слагаемого (Two sum)
- Найти дубликаты ( Contains Duplicate)

👉 Разделяй и властвуй (#divideandconquer)

Используется с отсортированными массивами, когда есть возможность определить, в какой части массива находится нужное значение. Часто используется для поиска (бинарный поиск) элемента (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array). Но может использоваться и в более сложном виде, например, для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Рекурсия (#recursion)

Используется, когда мы можем по какому-либо принципу сократить исходные данные (например, уменьшить массив) и выполнить для уменьшенных данных те же самые действия. Требуется обработка крайнего случая, когда дальнейшее сокращение данных невозможно (пустой массив). Возможны проблемы с переполнением стека.

Например, мы использовали рекурсию для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Динамическое программирование (#dp)

У динамического программирования есть несколько разновидностей: мемоизация и табуляция. Сюда же можно включить вычисление префиксных сумм (#prefixsum). Подвидом ДП является алгоритм Кадане.
Суть метода в том, что мы используем результаты предыдущих вычислений.
Динамическое программирование часто используется в задачах с массивами для нахождения подмассива с заданными свойствами, например, с максимальной суммой (Maximum Subarray, Maximum Product Subarray)
Также с его помощью (префиксные суммы) мы вычисляли произведение всех элементов массива кроме текущего (Product of Array Except Self).

👉 Set

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

#arrays #ретро

@leetcode_furrycat