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

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 #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

[Решение 4.1. Разделяй и властвуй] Leetcode #53. Maximum Subarray

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

Стратегия "Разделяй и властвуй" предполагает деление исходного массива на несколько частей. Мы будем делить на три (левую L, правую R и центральный элемент `mid`). Тогда наш искомый подмассив с максимальной суммой может лежать:

- полностью в левой части L (от 0 до `mid-1`)
- полностью в правой части R (от mid+1 до `n.length-1`)
- либо включает в себя обязательно центральный элемент mid и возможно части L и R, которые находятся рядом с mid

Для L и R мы запустим рекурсивное вычисление. Для третьего случая посчитаем максимальную сумму. Потом сравним три значения и вернем максимальное.

function getMaxSubArraySum(nums, left, right) {
    left = left ?? 0; // начало анализируемого подмассива
    right = right ?? nums.length - 1; // конец анализируемого подмассива

    if (left > right) return -Infinity;

    const mid = Math.floor((left + right) / 2); // середина анализируемого подмассива

    // рекурсивно считаем для левой и правой частей
    const maxLeftSubArraySum = getMaxSubArraySum(nums, left, mid - 1);
    const maxRightSubArraySum = getMaxSubArraySum(nums, mid + 1, right);

    // находим подмассив с максимальной суммой, 
    // который содержит элемент mid 

    let leftMaxSum = 0;
    let rightMaxSum = 0;

    // для L идем с конца, так как подмассив должен быть рядом с mid
    // считаем непрерывную сумму элементов и отбираем максимальную

    for (let i = mid - 1, currentLeftSum = 0; i >= left; i--) {
        currentLeftSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, currentLeftSum);
    }

    // то же для R 

    for (let i = mid + 1, currentRightSum = 0; i <= right; i++) {
        currentRightSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, currentRightSum);
    }

    const maxCenterSubArraySum = leftMaxSum + nums[mid] + rightMaxSum;

    return Math.max(maxLeftSubArraySum, maxRightSubArraySum, maxCenterSubArraySum)
}

Временная сложность этого решения - ожидаемо O (n * log n). Мы делаем log n разделений и для каждого считаем maxCenterSubArraySum, что требует перебора массива (n).

Пространственная сложность: O (log n) - так как у нас рекурсия.

#medium #arrays #divideandconquer #recursion

@leetcode_furrycat

[Решение 4.2. Оптимизация Разделяй и властвуй] Leetcode #53. Maximum Subarray

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

И наконец, мы можем еще сократить время выполнения алгоритма, заранее посчитав префиксные и суффиксные суммы.

const prefixes = [...nums]
const suffixes = [...nums] 

for (i = 1; i < nums.length; i++) {
  const previousSum = prefixes[i - 1];
  prefixes[i] += Math.max(0, previousSum);
}

for (i = nums.length - 2; i >= 0; i--) {
  const previousSum = suffixes[i + 1];
  suffixes[i] += Math.max(0, previousSum;
}

Теперь рассчитать maxCenterSubArraySum намного проще:

const maxCenterSubArraySum = prefixes[mid] + suffixes[mid+1]

Временная сложность: O(n)
Пространственная сложность: O(n)

#medium #arrays #divideandconquer #prefixsum

@leetcode_furrycat

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

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

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

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

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

@leetcode_furrycat

[Условие] Leetcode #153. Find Minimum in Rotated Sorted Array

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

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

Слишком просто, да?) Да, загвоздка в том, что массив у нас rotated ("прокручен" что ли) несколько раз.

Например, если у нас есть массив [0,1,2,3,4] и мы его один раз "прокрутим", получится [4,0,1,2,3]. Если еще один раз прокрутим, будет [3,4,0,1,2].

Так вот наш массив прокручен от 1 до n раз. И мы должны найти в нем минимальный элемент. И сделать это нужно алгоритмом с временной сложностью не более, чем O(log n).

Кейс 1
nums = [3,4,5,1,2]
ответ: 1
объяснение: оригинальный отсортированный массив [1,2,3,4,5] прокручен 3 раза

#medium #arrays #divideandconquer

@leetcode_furrycat

[Решение] Leetcode #153. Find Minimum in Rotated Sorted Array

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

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

Берем исходный массив и находим его середину. Теперь нужно выяснить, в какой части массива (левой или правой) нужно продолжить поиск.

Тут может быть две ситуации:

- центральный элемент меньше первого элемента массива
например, [4,5,1,2,3] или [5,1,2,3,4]
тогда либо центральный элемент искомый, либо мы продолжаем поиск в левой части массива

- центральный элемент больше первого элемента массива
например, [1,2,3,4,5] или [3,4,5,1,2]
тогда либо первый элемент искомый, либо мы продолжаем поиск в правой части массива

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

function findMin(nums: number[]): number {
  let start = 0;
  let end = nums.length - 1;
  let min = Infinity;

  while(start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (nums[start] <= nums[mid]) {
      min = Math.min(min, nums[start]);
      start = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      end = mid - 1;
    }
  }

  return min;
}

#medium #arrays #divideandconquer

@leetcode_furrycat

[Условие]. Leetcode #33. Search in Rotated Sorted Array

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

Тут мы снова имеем дело с rotated массивами (можно посмотреть в предыдущей задачке подробнее). На этот раз нам нужно искать конкретный элемент в таком "прокрученном" массиве. Нужно вернуть либо индекс искомого элемента, либо -1, если элемента в массиве нет.

Кейс 1
nums = [4,5,6,7,0,1,2], target = 0
ответ: 4

Кейс 2
nums = [4,5,6,7,0,1,2], target = 3
ответ: -1

Необходимо решить задачку за O(log n).

#medium #arrays #divideandconquer

@leetcode_furrycat

[Решение] Leetcode #33. Search in Rotated Sorted Array

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

Решение довольно простое. Как и в предыдущем примере мы берем массив, находим средний элемент и делим массив пополам. Проверив ряд простых условий, определяем, в какой половине продолжать поиск.

Основная сложность здесь - учесть все возможные ситуации.

function search(nums: number[], target: number): number {
    let start = 0 
    let end = nums.length - 1
    
    while(start <= end) {
        const mid = Math.floor((start + end) / 2)

        if (nums[mid] === target) return mid

        if (nums[start] <= nums[mid]) {
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1 
            } else {
                start = mid + 1
            }
        } else {
            if (target > nums[mid] && target <= nums[end]) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }

    return -1
}

#medium #arrays #divideandconquer

@leetcode_furrycat

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