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

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 #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 #53. Maximum Subarray

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

Получаем на вход массив целых чисел nums. Необходимо найти подмассив с самой большой суммой элементов. На выходе должна быть сумма элементов подмассива.

Подмассив - это непрерывная и непустая последовательность элементов. Сам массив тоже является своим подмассивом.

Кейс 1
nums = [-2,1,-3,4,-1,2,1,-5,4]
Ответ: 6
Объяснение: подмассив с самой большой суммой [4, -1, 2, 1]

Кейс 2
nums = [1]
Ответ: 1

Кейс 3
nums = [5,4,-1,7,8]
Ответ: 23
Объяснение: подмассив с самой большой суммой [5,4,-1,7,8]

Примечание: если получится найти решение со сложностью O(n), постарайтесь найти более "изящное" решение с использованием подхода "разделяй и властвуй".

#medium #arrays #dp #recursion #divideandconquer #prefixsum

@leetcode_furrycat

[Решение 2. ДП, мемоизация] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Если посмотреть на рекурсивное решение задачи https://yangx.top/leetcode_furrycat/29 повнимательнее, то можно заметить, что у нас много повторяющихся вычислений: сначала мы для нулевого элемента массива считаем все последующие комбинации (от 1 до конца, от 2 до конца, от 3 до конца). Потом для первого считаем практически то же самое (от 2 до конца, от 3 до конца и т.д.)

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

const nums = [5,4,-1,7,8]
const dp = {
    0: [23,18,15,15,8],
    1: [null, 18,14,15,8]
}

Ключи 0 и 1 - это значения параметра firstElementMustPick, а массивы чисел - это максимальные суммы для каждого элемента исходного массива. Рассчитываем их один раз, а потом просто переиспользуем.

#medium #arrays #dp

@leetcode_furrycat

[Решение 3.1. ДП, табуляция] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

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

Возьмем сначала самый маленький подмассив (состоящий из одного элемента) и посчитаем сумму для него - сохраним это значение.

Затем увеличим этот массив на один элемент. Новый элемент может:
1) входить в искомый подмассив вместе с предыдущим
2) входить в искомый подмассив самым первым (открывать его)
3) не входить в искомый подмассив

В dp[1][i] мы сохраним максимальный вариант из 1) и 2).
А в dp[0][i] - максимальный вариант из ранее сохраненного (`dp[0][i-1]`) и только что посчитанного (`dp[1][i]`).

В dp[1] мы будем хранить значения с учетом того, что элемент входит в подмассив, а в dp[0] - без учета, то есть просто максимально возможное значение.

Таким образом, в кеше в элементе с индексом i у нас будет находиться максимальная сумма для соответствующего элемента массива nums (точнее для подмассива [0, i]).

Пошаговый разбор:

const nums = [-2,1,-3,4,-1,2,1,-5,4]
const dp = {
    0: [-2],
    1: [-2]
}

i = 1
если i-й элемент входит в подмассив
- то он либо следует за предыдущим элементом (dp[1][0] + nums[1] = -2 + 1 = 1)
- либо начинает этот массив сам (nums[1] = 1)
находим максимум и добавляем в кеш

если i-й элемент не входит в подмассив
находим максимум между предыдущим значением в этом массиве (максимальная сумма для предыдущего элемента) dp[0][i - 1] = -2
и только что посчитанной максимальной суммой для текущего dp[1][i] = 1

dp = {
    0: [-2, 1],
    1: [-2, 1]
}

i = 2
dp[1][2] = Math.max(dp[1][1] + nums[2], nums[2]) = Math.max(1 + -3, -3) = -2
dp[0][2] = Math.max(dp[0][1], dp[1][2]) = Math.max(1, -3) = 1

Ответом всегда будет последнее значение в dp[0], так как там хранится максимально возможная сумма подмассива для последнего индекса.

#medium #arrays #dp

@leetcode_furrycat

[Решение 3.2. ДП, табуляция] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

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

- сумма, накопленная для предыдущего элемента, плюс текущий элемент
- или только текущий элемент (если предыдущая сумма отрицательна)

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

const dp = [...nums]

for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}

return Math.max.apply(null, dp);

#medium #arrays #dp

@leetcode_furrycat

🔼 Временная сложность алгоритмов, использующих приемы динамического программирования, - O(n), так как по массиву мы проходим только один раз, и используем при этом ранее вычисленные значения.


#medium #arrays #dp

@leetcode_furrycat

[Решение 3.3. ДП, алгоритм Кадане] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Мы можем пойти еще дальше и отказаться от массива dp. На самом деле на каждом шаге нам нужно лишь предыдущее значение, значит, и хранить можно только его.

На самом деле мы будем хранить два значения - локальную сумму (локальный максимум) и глобальный максимум. Локальная сумма непрерывна, мы всегда сравниваем предыдущее накопленное значение и его сумму с текущим элементом. В глобальный максимум будем заносить только самые большим величины - он заменит нам финальный поиск самого большого элемента в массиве dp:

function kadane(nums) {
    let currentMax = 0;
    let maxTillNow = - Infinity;

    for (let i = 0; i < nums.length; i++) {
        const el = nums[i];
        currentMax = Math.max(el, currentMax + el);
        maxTillNow = Math.max(maxTillNow, currentMax)
    }

    return maxTillNow;
}

Временная сложность у этого алгоритма тоже равна O(n), зато пространственная всего O(1).

#medium #arrays #dp

@leetcode_furrycat

[Решение] Leetcode #53. Maximum Subarray

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

Итого у нас получилось больше 5 способов решить одну и ту же задачку.

0 - Brute force
1 - Простая рекурсия
2 - Рекурсия с мемоизацией вычислений
3 - Табуляция, оптимизированная табуляция
4 - Алгоритм Кадане
5 - Разделяй и властвуй + оптимизация с предварительным расчетом

#medium #arrays #dp #divideandconquer #recursion #prefixsum

@leetcode_furrycat