Coding interview scrapbook

Источник: https://leetcode.com/problems/shortest-palindrome/   в гугл таблицах от 23.01.2020 Дана строка s. Вы можете конвертировать s в палиндром, если добавите необходимые символы в начало строки. Вернуть самый короткий палиндром, который можно построить при помощи описанной трансформации. Пример 1: Дано: s = "aacecaaa" Результат: " a aacecaaa" Пояснение : добавили символ а в начале строки. Пример 2: Input: s = "abcd" Output: " dcb abcd" Пояснение : добавили символы dcb в начале строки. Ограничения: 0 <= s.length <= 5 * 10 4 s состоит из маленьких латинских букв английского алфавита . Идея решения Если представить, что строка s=AB, где А - это палиндром, то тогда нам нужно добавить развернуют строку B в начало s, чтобы получить результат. То есть результат = B'AB, где B' - это развернутая строка. Как найти А? Надо склеить строку с её частями по-другому: построим q=A'B'BA. Но поскольку А - палиндром, то есть А=А', ...

Источник: https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/ 1218.   Longest Arithmetic Subsequence of Given Difference Дан массив целых чисел и целое число, представляющее собой искомую разность. Вернуть наидленнейшую подпоследовательность в массиве такую, что разница между соседними элементами подпоследовательности равна искомой разности. Подпоследовательность - это последовательность, которая может быть получена из исходного массива путем удаления из него нескольких (или 0) элементов, без изменения порядка в оставшихся элементах.   Пример 1: Дано: arr = [1,2,3,4], difference = 1 Результат: 4 Пояснение: Наидлиннейшая подпоследовательность = [1,2,3,4]. В ней каждая пара соседних элементов отличается на значение difference. Пример 2: Дано: arr = [1,3,5,7], difference = 1 Результат: 1 Пояснение: Любой элемент массива является подпоследовательностью длины 1. Пример 3: Дано: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Результат: 4 Пояснение: ...

Источник: https://leetcode.com/problems/valid-parentheses/ Дана строка s , состояшая из символов '(' ,   ')' ,   '{' ,   '}' ,   '[' и ']' . Определеить валидна ли последовательность скобок. Последовательность сокбок валидна: Открытые скобки закрываются тем же типом скобок. Открытые скобки закрываются в корректной последовательности.   Пример 1: Дано: s = "()" Результат: true Пример 2: Дано: s = "()[]{}" Результат : true Пример 3: Дано : s = "(]" Результат : false Пример 4: Дано : s = "([)]" Результат : false Example 5: Дано : s = "{[]}" Результат : true   Ограничения: 1 <= s.length <= 10 4 s состоит только из '()[]{}' . Идея решения Для проверки валидности выражений в скобках удобно использовать стеки. Каждую открывающую скобку бросаем в стек. Как только встречаем закрывающую скобку, смотрим, что у нас в верхушке стека. Там бует открывающая скобка, но нам нужн...