[Условие] Leetcode #1. Two sum

Ссылка на задачу на Leetcode
Решение

У нас есть массив чисел nums и число target.
Нужно написать функцию, которая возвращает индексы двух чисел из массива nums, которые в сумме дают target. Нельзя использовать один и тот же элемент дважды.
Считаем, что у задачи всегда есть решение и оно только одно.

Отдельный пункт: постараться найти решение, у которого временная сложность меньше O(n^2).

Кейс #1: 
nums = [2,7,11,15]
target = 9
output = [0,1]

Кейс #2:
nums = [3,2,4]
target = 6
output: [1,2]

Кейс #3:
nums = [3,3]
target = 6
output = [0,1]

#easy #arrays #twopointers #hashtable

@leetcode_furrycat

[Решение] Leetcode #1. Two sum

Условие задачи

👉 Решение #1. Самое очевидное

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

Временная сложность - O(n^2), так как мы дважды перебираем массив.

👉 Решение #2. Хеш-таблица

Заводим хеш-таблицу hash.
Перебираем каждый элемент массива nums в цикле.
Вычитаем его из target - это искомая пара.
Смотрим, есть ли эта пара в hash. Если есть - решение найдено.
Если нет, записываем текущий элемент в хеш. Ключом является сам элемент, чтобы его было просто найти, а значением - его индекс в массиве.

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

👉 Решение #3. Два указателя

Сортируем массив, так чтобы числа в нем шли по порядку, например, от меньше к большему.
Устанавливаем один указать в начало массива (с меньшего числа) , а второй - в конец (с большего числа).
Складываем элементы под указателями. Если полученная сумма больше target, двигаем правый указатель влево (уменьшаем число под ним).
Если полученная сумма меньше target, двигаем левый указатель вправо (увеличиваем число под ним).

Временная сложноть - O(n * log n). Это сложность алгоритма сортировки. Сам поиск пары имеет сложность O(n).

Видео с разбором всех трех решений (англ.)

#easy #arrays #twopointers #hashtable

@leetcode_furrycat

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

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

#ретро

[Условие] Leetcode #2. Add two numbers

Ссылка на задачу на Leetcode
Решение

Есть два связных списка, каждый из которых представляет неотрицательное число. Цифры (разряды) при этом идут в обратном порядке.
Узел связного списка представлен классом ListNode с полями val и next.

Пример: число 307 будет выглядеть как [7, 0, 3] - соответственно каждое число - это объект ListNode.

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

Пример 1:
l1 = [2,4,3]
l2 = [5,6,4]
Output: [7,0,8] 
Объяснение: 342 + 465 = 807

Пример 2: 
l1 = [0]
l2 = [0]
Output: [0]

Пример 3:
l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]
output = [8,9,9,9,0,0,0,1]

Ограничения:
- ведущих нулей у чисел нет, но число вполне может быть равно нулю
- в каждом списке от 1 до 100 узлов
- каждый узел имеет значение от 0 до 9

#medium #linkedlists

@leetcode_furrycat

[Решение] Leetcode #2. Add two numbers

Условие задачи

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

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

Видео решения

#medium #linkedlists

@leetcode_furrycat

[Условие] Leetcode #3. Longest Substring Without Repeating Characters

Ссылка на задачу на Leetcode
Решение

На вход дается строка s. Нужно найти самую длинную подстроку без повторений.

Пример #1:
s = 'abcabcbb'
output: 3 // 'abc'

Пример #2:
s = 'bbbbb'
output: 1 // 'b'

Пример #3:
s = 'pwwkew'
output: 3 // 'wke'

Ограничения:
- длина строки до 5 * 10^4
- содержать может английские буквы, цифры, символы и пробелы

#medium #strings

@leetcode_furrycat

[Решение] Leetcode #3. Longest Substring Without Repeating Characters

Условие задачи

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

Пример для s = abcbac:

- считаем подстроку с нулевого символа (currentIndex = 0)
- перебираем символы по одному и заносим их в хеш вместе с индексами: { a: 0, b: 1, c: 2 }
- текущий индекс 3 - i = 3, символ b, видим, что он уже встречался на 1-й позиции. Значит, строка без повторений кончилась. Сохраняем ее длину (с нулевого символа до 3 невключительно: max = 3)
- обновляем индекс символа b в хеше: { a: 0, b: 3, c: 2 }
- начинаем новый отсчет со следующего за повторенным символа (currentIndex = 2)
- i = 4, символ a - сохраненный индекс 0, но это меньше, чем начало нашей текущей подстроки, так что можно считать, что символа a у нас еще не было.
- i = 5, символ c - сохраненный индекс 2 - это попадает в нашу строку, поэтому заканчиваем ее. Длина полученной подстроки равна 3 (со 2-го по 5 символ невключительно). Она не больше текущего max, так что можно не перезаписывать.

Итого, ответ 3.

Видео с разбором
Тут немного другая структура, но в целом похоже на мое решение. Кажется даже, что мое немного эффективнее, так как в нем нет доп. цикла для удаления ненужных символов.

#medium #strings

@leetcode_furrycat

[Условие] Leetcode #10. Regular Expression Matching

Ссылка на задачу на Leetcode
Решение

Нужно реализовать простейшее регулярное выражение. На вход получаем строку s и паттерн p. Задача - проверить, соответствует ли строка паттерну.
Проверяется полное совпадение строки - от начала и до конца.

Строка содержит только английские буквы в нижнем регистре.

Паттерн может содержать английские буквы в нижнем регистре, а также символы . и *.
При этом символ . означает "один любой символ".
А символ * относится к предыдущему символу и означает "0 или больше". То есть паттерн "a*" соответствует строкам "a", "aa", "aaaaaa", а также пустой строке "".

В паттерне может быть комбинация ".*", которая означает "0 и более любых символов".

Пример #1:

s = "aa", p = "a"
output: false (строка совпадает не полностью)

Пример #2:

s = "aa", p = "a*"
output: true

Пример #3:

s = "ab", p = ".*"
output: true

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

#hard #dp

@leetcode_furrycat

[Решение] Leetcode #10. Regular Expression Matching

Условие задачи

Решение получилось объемным, поэтому отдельно: https://telegra.ph/Leetcode-10-Regular-Expression-Matching-Reshenie-04-17

#hard #dp

@leetcode_furrycat

[Условие] Leetcode #4. Median of Two Sorted Arrays

Ссылка на задачу на Leetcode
Решение (часть 1 и часть 2)

Получаем два отсортированных массива: nums1 с длиной m и nums2 с длиной n. Возвращаем их медиану (серединное значение). Временная сложность должна быть O(log (m + n)).

Кейс #1:
nums1 = [1,3]
nums2 = [2]
Output: 2 
Объяснение: общий массив - [1,2,3], медиана - 2

Кейс #2:
nums1 = [1,2]
nums2 = [3,4]
Output: 2.5
Объяснение: общий массив - [1,2,3,4], медиана - (2+3)/2 = 2.5

#hard #arrays

@leetcode_furrycat

[Решение] Leetcode #4. Median of Two Sorted Arrays. Решение (Часть 1)

Условие задачи

Решение в лоб: слить отсортированные массивы в один. Но оно не соответствует заявленной сложности (будет O(n)), поэтому ищем другие пути.

Левая половина

Нам достаточно получить левую половину результирующего массива (до медианы).

если смерженный массив: [1,2,3,4,5]
то его левая половина: [1,2]

если смерженный массив: [1,2,3,4]
то его левая половина: [1,2]

У нас есть два массива, arr1 и arr2. Пусть arr1.length меньше или равна arr2.length, то есть arr1 короче. Будем называть смерженный массив mergedArr, а его левую половину mergedArrLeft.

Легко узнать, сколько элементов входят в mergedArrLeft. Находим общую длину двух массивов (`total`) и делим ее на 2 (`half`). Таким образом в mergedArrLeft входит half элементов.

если mergedArr: [1,2,3,4,5]
total = 5
half = Math.floor(total / 2) = 2
mergedArrLeft: [1,2]

mergedArr: [1,2,3,4]
total = 4
half = Math.floor(total / 2) = 2
mergedArrLeft: [1,2]

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

Сделаем предположение, что в mergedArrLeft входит половина массива arr1 (более короткого массива). Почему половина? Ну, нужно же с чего-то начинать, а начинаем мы обычно с принципа "разделяй и властвуй".

Внимание: нет гарантии, что это предположение окажется верным. Мы будем его корректировать по мере необходимости.

Итак, берем половину arr1, считаем, сколько это элементов. Вычитаем это число из half, чтобы понять, сколько элементов нужно взять из второго массива, чтобы составить mergedArrayLeft.

arr1 = [1,2,3,4,5]
arr2 = [1,2,3,4,5,6,7,8]

total = 5 + 8 = 13
half = Math.floor(13 / 2) = 6

arr1MedianIndex = Math.floor(5 / 2) = 2
arr1Elements = [1,2,3] // с 0го по 2й элемент включительно

arr2ElementsCount = 3 // 6 - 3
arr2Elements = [1,2,3]

Проверка

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

То есть мы берем из arr1 элементы [1,2,3]. В нем остаются [4,5]. А из arr2 мы берем элементы [1,2,3].

arr1 = [1,2,3,4,5]
arr1Elements = [1,2,3] // входит в arrMergedLeft
arr1Rest = [4,5]

arr2 = [1,2,3,4,5,6,7,8]
arr2Elements = [1,2,3] // входит в arrMergedLeft
arr2Rest = [4,5,6,7,8]

Последний элемент из arr1Elements не может быть больше первого элемента из arr2Rest и наоборот.

Если все верно, то мы легко можем найти последний элемент mergedArrLeft (самое большое значение из arr1Elements и arr2Elements`) и следующий за ним элемент (самое маленькое значение из `arr1Rest и arr2Rest`). Если `total - четное, нам нужно будет найти их среднее арифметическое, если нечетное, то следующий элемент и является медианой.

На данный момент сложность алгоритма константная - O(1), так как мы выполняем только арифметические операции.

#hard #arrays

@leetcode_furrycat

Leetcode #4. Median of Two Sorted Arrays. Решение (Часть 2)

Корректировка

Если проверка не прошла - мы неправильно определили состав mergedArrLeft. Значит, нужно сдвинуть arr1Elements. Куда именно, зависит от того, какая конкретно проверка не прошла. Если arr1Elements оказался больше, чем надо, то его нужно уменьшить. И соответственно, наоборот.

Посмотрим на примере:

arr1 = [1,2,3,4]
arr2 = [1,2,3,4,5,6,7,8]

total = 4 + 8 = 12
half = Math.floor(12 / 2) = 6

arr1MedianIndex = Math.floor(4 / 2) = 2
arr1Elements = [1,2] 
arr1Rest = [3,4]

arr2ElementsCount = 3 // 6 - 2
arr2Elements = [1,2,3,4]
arr2Rest = [5,6,7,8]

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

Те элементы, что уже взяты ([1,2]) мы отбросим, так как они точно входят в arrMergedLeft. Возьмем оставшиеся - и повторим с ними все то же самое: разделим пополам, и предположим, что первая половина входит в arrMergedLeft.

Таким образом, arr1Elements увеличится, придется все пересчитать.

arr1Elements = [1,2,3]
arr1Rest = [4]

arr2ElementsCount = 3
arr2Elements = [1,2,3]
arr2Rest = [4,5,6,7,8]

Теперь проверка проходит.

Код

В разборе для наглядности использовалось количество элементов в частях массивов. Разумеется, в коде удобнее и проще использовать индексы. То есть мы не будем вычислять arr2ElementsCount, а вычислим, элементы до какого индекса входят в arrayMergedLeft.

Также мы будем использовать указатели left и right для обозначения той части массива arr1, с которой мы сейчас работаем. Изначально они будут стоять по краям массива (`0` и `arr1.length - 1`). Если проверка не пройдет, мы будем их сдвигать (либо один, либо другой).

Сложность

В неудачном случае (если проверка не проходит), мы делим массив arr1 надвое - "разделяй и властвуй", следовательно сложность алгоритма составляет O(log(n)).

Решение (видео, англ.)

#hard #arrays

@leetcode_furrycat

[Условие] Leetcode #5. Longest Palindromic Substring

Ссылка на задачу на Leetcode
Решение

На вход получаем строку s, необходимо найти самую длинную подстроку, которая является палиндромом (читается в обе стороны одинаково).

Ограничения:

- длина строки s = [1, 1000]
- строка s состоит только из английских букв и цифр

#medium #strings

@leetcode_furrycat

[Решение] Leetcode #5. Longest Palindromic Substring

Условие задачи

Проходимся в цикле по всем символам строки. Для каждого символа (`currentIndex`) определяем палиндромную строку с этим символом в центре - то есть начинаем с этого символа и пытаемся наращивать подстроку в обе стороны до тех пор, пока она остается палиндромом.

Для набираемой подстроки нужно хранить индекс начала (`left`) и конца (`right`). Изначально left = currentIndex, right = currentIndex.

Начинать следует с последовательности одинаковых символов любой длины - это ядро палиндрома. То проверяем правые от currentIndex символы, если они одинаковые, раздвигаем, отодвигаем right.

Когда одинаковые символы закончились, пробуем расширять подстроку по одному символу в обе стороны сразу. Если слева и справа от нее находятся одинаковые символы, значит, она продолжает оставаться палиндромом, можно сдвинуть left и right.

Потом просто находим самый длинный палиндром из полученных.

#medium #strings

@leetcode_furrycat

Подборки задач с LeetCode

Blind 75: 75 самых популярных задачек, которые часто встречаются на собеседованиях. Удобно разделены по темам: Массивы, Бинарные операции, Динамическое программирование, Графы, Интервалы, Связные списки, Матрицы, Строки, Деревья и Кучи.

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

Grind 75: улучшенная версия Blind 75. Это фактически план обучения, разбитый понедельно. Сложность задачек постепенно увеличивается.

#подборки

@leetcode_furrycat

[Условие] Leetcode #121. Best Time to Buy and Sell Stock

Ссылка на задачу на Leetcode
Решение

У нас есть некоторая акция, цена которой каждый день меняется. Эти цены занесены в массив prices. Необходимо определить самую выгодную комбинацию дней для покупки и продажи этой акции. Разумеется, нельзя продать раньше, чем купишь. Функция должна вернуть размер максимальной прибыли.

Кейс 1:
prices: [7, 1, 5, 3, 6, 4]
ответ: 5
объяснение: выгоднее всего купить акцию во второй день (цена = 1) и продать в пятый (цена = 6)

Кейс 2:
prices: [7,6,5,4,3,1]
ответ: 0
объяснение: с этой акции в этот период нельзя получить прибыль

Ограничения:

prices.length = [1, 10^5]
prices[i] = [0, 10^4]

#easy #arrays #twopointers

@leetcode_furrycat

[Решение] Leetcode #121. Best Time to Buy and Sell Stock

Условие задачи

Используем подход с двумя указателями (`left` и `right`). Изначально устанавливаем их на первый и второй день.

Если цена между этими днями упала, то этот период нам не нужен. Можем сдвинуть указатели - left встает на место right, а right сразу же за ним.

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

Повторяем эту операцию в цикле, пока right не достигнет конца массива.

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

#easy #arrays #twopointers

@leetcode_furrycat

[Условие] Leetcode #217. Contains Duplicate

Ссылка на задачу на Leetcode
Решение

Получаем на вход массив целых чисел nums. Нужно вернуть true, если хоть одно значение встречается два раза (или больше).

Кейс 1
nums = [1,2,3,1]
output: true

Кейс 2
numbs = [1,2,3,4]
output: false

#easy #arrays #hashtable

@leetcode_furrycat

[Решение] Leetcode #217. Contains Duplicate

Условие задачи

Задачка выглядит несложной. В голову приходят два способа решения.

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

2 - с использованием Set.
Создаем из нашего массива Set (без дублирующихся элементов) и сравниваем их размеры.

Оба алгоритма имеют сложность O(n).

#easy #arrays #hashtable

@leetcode_furrycat