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

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://t.iss.one/leetcode_furrycat/28

Если посмотреть на рекурсивное решение задачи https://t.iss.one/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://t.iss.one/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://t.iss.one/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://t.iss.one/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

[Условие] Leetcode #152. Maximum Product Subarray

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

Условие похоже на предыдущую задачу:

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

Кейс 1
nums = [2,3,-2,4]
Ответ: 6
Объяснение: [2,3]

Кейс 2
nums = [-2,0,-1]
Ответ: 0
Объяснение: 2 получиться не может, так как [-2,-1] это не подмассив, все остальные варианты дают 0 или отрицательное число

#medium #arrays #dp #prefixsum

@leetcode_furrycat

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

Условие задачи: https://t.iss.one/leetcode_furrycat/39

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

Для задачи с наибольшей суммой его суть заключалась в том, что мы проходили по массиву слева направо и вычисляем наибольшую возможную сумму для ТЕКУЩЕГО элемента (от начала массива до текущего элемента). А затем просто брали максимальное из полученных значений.

Но с произведением все немного по-другому. Здесь у нас есть нули, которые любой подмассив сведут к нулю, а также отрицательные числа, которые по одиночке радикальном уменьшают общее произведение, но парами очень даже увеличивают. То есть здесь мы не можем сказать, что максимально возможное произведение для 2-го элемента - это именно то, что нам нужно, чтобы получить максимальное произведение для 3-го элемента.

Пример:

const nums = [-2, 3, -4]

для n=1: maxTillNow = -2
для n=2: maxTillNow = Math.max(3, -6) = 3
для n=3: maxTillNow = Math.max(3, -12) = 3

Очевидно, что этот алгоритм неправильный, и чтобы получить максимум для третьего элемента, нам следует взять -6 на предыдущем шаге.

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

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

А чтобы избежать разнообразных эксцессов с отрицательными числами, пройдем по массиву два раза - слева направо и справа налево:

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

function maxProduct(nums) {
    let currentProduction = 1;
    let maxTillNow = -Infinity;

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

    currentProduction = 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const el = nums[i];
        currentProduction *= el;
        maxTillNow = Math.max(maxTillNow, currentProduction);
        if (currentProduction === 0) {
            currentProduction = 1;
        }    
    }

    return maxTillNow;
}

Временная сложность: O(N) - мы делаем два прохода по массиву, но коэффициент отбрасывается

#medium #arrays #dp #prefixsum

@leetcode_furrycat