#1493 Longest Subarray of 1's After Deleting One Element
Потренироваться можно тут: leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description/
Код решения: pastebin.com/q968F2vC
Так же закинул код в комментарий к посту ⬇️

#53 Maximum Subarray

💡 Почему работает алгоритм Кадейна?

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

Если твой накопленный баланс уже ушёл в минус, нет смысла тащить этот минус дальше. Любая будущая прибыль станет только больше, если начать считать её с сегодняшнего дня.

Поэтому на каждом шаге мы принимаем простое решение:
- либо продолжаем считать текущую сумму;
- либо забываем старые убытки и начинаем новый отсчёт с текущего элемента.

Именно поэтому переход выглядит так:

cur = max(nums[i], cur + nums[i]);

Потренироваться можно тут: leetcode.com/problems/maximum-subarray/
Код решения: pastebin.com/AgQPq8nL
Так же закинул код в комментарий к посту ⬇️

#153 Find Minimum in Rotated Sorted Array
Потренироваться можно тут: leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
Код решения: pastebin.com/H7Uv5Z2H
Так же закинул код в комментарий к посту ⬇️

Выложил видос с разбором этой задачки на Bucket Sort ⬆️

Meeting rooms

В задачах на интервалы очень часто требуется подсчитать МАКСИМАЛЬНОЕ количество пересекающихся интервалов.

И эта техника позволяет это сделать, советую запомнить.

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

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

Потренироваться можно тут: www.interviewbit.com/problems/meeting-rooms/
Код решения: pastebin.com/hzLQ43S9
Так же закинул код в комментарий к посту ⬇️

#217 Contains Duplicate
Потренироваться можно тут: leetcode.com/problems/contains-duplicate/
Код решения: pastebin.com/TtLwWnxk
Так же закинул код в комментарий к посту ⬇️

#268 Missing Number
Потренироваться можно тут: leetcode.com/problems/missing-number/description/
Код решения: pastebin.com/QxMTtAxM
Так же закинул код в комментарий к посту ⬇️

#263 Ugly Number
Потренироваться можно тут: leetcode.com/problems/ugly-number/description/
Код решения: pastebin.com/s2ggCtTt
Так же закинул код в комментарий к посту ⬇️

#40 Combination Sum II

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

Мы постепенно собираем текущую комбинацию cur. На каждом шаге решаем: взять очередное число или нет. Если сумма стала равна target — сохраняем ответ. Если уже превысили target — дальше идти нет смысла, откатываемся назад (pop_back()) и пробуем другой вариант.

Почему сначала сортируем массив?
Сортировка очень часто встречается в backtracking, потому что одинаковые элементы оказываются рядом. Благодаря этому их легко пропустить и не получить одинаковые комбинации.

Самая важная строка:

if (j > start && candidates[j] == candidates[j - 1]) {
    continue;
}

Почему именно j > start?

Потому что мы пропускаем дубликаты только на одном уровне рекурсии. Если на этом уровне уже начали ветку с первым 1, то начинать такую же ветку со второго 1 бессмысленно — получится абсолютно такой же набор комбинаций.

Но на следующем уровне рекурсии второй 1 использовать можно. Именно поэтому условие сравнивается со start, а не просто с 0. Благодаря этому комбинация [1,1,6] появится один раз, а не исчезнет совсем и не продублируется.

Потренироваться можно тут: leetcode.com/problems/combination-sum-ii/description/
Код решения: pastebin.com/EYN7gjfW
Так же закинул код в комментарий к посту ⬇️

#69 Sqrt(x)

Поиск квадратного корня с помощью бинарного поиска. Отличная задача, чтобы понять, как бинарный поиск можно использовать для поиска ответа

Потренироваться можно тут: leetcode.com/problems/sqrtx/
Код решения: pastebin.com/jzYaC82Y
Так же закинул код в комментарий к посту ⬇️

#507 Perfect Number
Потренироваться можно тут: leetcode.com/problems/perfect-number/
Код решения 🤡: pastebin.com/yf6ek9eU
Код решения: pastebin.com/WRavmJJF
Так же закинул код в комментарий к посту ⬇️

#22 Generate Parentheses
Потренироваться можно тут: leetcode.com/problems/generate-parentheses/description/
Код решения: pastebin.com/mYepPBWi
Так же закинул код в комментарий к посту ⬇️

#228 Summary Ranges
Потренироваться можно тут: leetcode.com/problems/summary-ranges/description/
Код решения: pastebin.com/bMFKNzbw
Так же закинул код в комментарий к посту ⬇️

#3950 Exactly One Consecutive Set Bits Pair
Потренироваться можно тут: leetcode.com/problems/exactly-one-consecutive-set-bits-pair/description/
Код решения: pastebin.com/vDFu4ude
Так же закинул код в комментарий к посту ⬇️

#767 Reorganize String
Потренироваться можно тут: leetcode.com/problems/reorganize-string/
Код решения: pastebin.com/1LY3eiRm
Так же закинул код в комментарий к посту ⬇️

#55 Jump Game
Потренироваться можно тут: leetcode.com/problems/jump-game/description/
Код решения: pastebin.com/4d0kz7Cq
Так же закинул код в комментарий к посту ⬇️

#560 Subarray Sum Equals K
Потренироваться можно тут: leetcode.com/problems/subarray-sum-equals-k/description/
Код решения: pastebin.com/EsnCcVFE
Так же закинул код в комментарий к посту ⬇️

#204 Count Primes
Потренироваться можно тут: leetcode.com/problems/count-primes/description/
Код решения: pastebin.com/VWzz0qUH
Так же закинул код в комментарий к посту ⬇️

#XII Integer to Roman
Потренироваться можно тут: leetcode.com/problems/integer-to-roman/
Код решения: pastebin.com/dNNZpZWT
Так же закинул код в комментарий к посту ⬇️

#1446 Consecutive Characters
Потренироваться можно тут: leetcode.com/problems/consecutive-characters/description/
Код решения: pastebin.com/8eXSGM2m
Так же закинул код в комментарий к посту ⬇️

#206 Reverse Linked List
Потренироваться можно тут: leetcode.com/problems/reverse-linked-list/
Код решения: pastebin.com/9vvFtW5v
Так же закинул код в комментарий к посту ⬇️