Coding interview scrapbook

Источник: https://leetcode.com/problems/trapping-rain-water/ Даны n неотрицательных чисел, которые кодируют неровную поверхность, состояющую из столбиков. Ширина каждого столбика = 1. Подсчитать, сколько дождевой воды можно накопить между столбиками.   Пример 1: Дано: height = [0,1,0,2,1,0,1,3,2,1,2,1] Результат: 6 Объяснение: Неровная поверхность, образуемая столбиками (черные квадраты) закодирована массивом [0,1,0,2,1,0,1,3,2,1,2,1]. Вода (голубые столбики) задерживается во впадинах паверхности. И обозначена голубыми квадратами. Всего у нас 6 голубых квадратов. Пример 2: Дано: height = [4,2,0,3,2,5] Результат: 9 Ограничения: n == height.length 1 <= n <= 2 * 10 4 0 <= height[i] <= 10 5 Идея решения Мы можем использовать стек, чтобы учитывать столбики поверхности, которые окружены другими столбиками - и значит, они могут быть покрыты водой. Сканируем массив и добавляем индекс элемента в стек, когда он меньше или равен элементу, соответствующему индексу в топе...

Источник: https://leetcode.com/problems/kth-largest-element-in-an-array/ Дан массив целых чисел nums и целое число k , вернуть k -й наибольший элемент в массиве , как сли бы массив был отсортирован. Задачу нужно решить за O(n) . Пример 1: Дано: nums = [3,2,1,5,6,4], k = 2 Результат: 5 Пример 2: Дано : nums = [3,2,3,1,2,4,5,5,6], k = 4 Результат: 4   Ограничения: 1 <= k <= nums.length <= 10 5 -10 4   <= nums[i] <= 10 4 Идея решения 1 Будем использовать кучу с наименьшим элементом в вершине, ограничив размер кучи числом k. Добавляя все элементы в массиве, один за другим, как только мы превысим размер кучи, то удалим наименьший элемент. Таким образом, в куче будет всегда находиться  k наибольших элементов. После обработки всего массива, k-й наибольший элемент будет находится в вершине кучи. Сложность алгоритма: добавление в кучу размера k занимает O(log k). мы добавляем N элментов в кучу, где N - размер массива. Итого общая сложность = O(N log k) Им...

Источник: https://leetcode.com/problems/binary-search-tree-iterator-ii/ Заимплементировать класс BSTIterator который представляет собой in-order обход (левое поддерево - текущий узел - правое поддерево) бинарного поискового дерева (BST): BSTIterator(TreeNode root) конструктор. Корень root является входным значением для конструктора. boolean hasNext() возвращает true если можно перейти вправо, иначе false . int next() перемещает указатель вправо и возвращает значение вершины. boolean hasPrev() возвращает true если можно перейти влево, иначе false . int prev() перемещает указатель влево и возвращает значение вершины. После инициализации курсор указывает на несуществующее значение, то есть можно сделать next() и получить наименьший элемент в дереве. Можем считать, что next() и prev() всегда валидны. То есть когда мы их вызваем, то всегда возвращаем какое-то значение. Пример: Дано ["BSTIterator", "next", "next", "prev", "n...

Источник: https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/ Дан массив строк words и строка chars . Страка хорошая , если ее можно составить из символов строки chars (каждый символ может быть использован только раз). Вернуть сумму длинн все хороших слов из массива words . Пример 1: Дано: words = ["cat","bt","hat","tree"], chars = "atach" Результат: 6 Пояснение: Мы можем сформировать строки "cat" и "hat", поэтому 3 + 3 = 6. Пример 2: Дано : words = ["hello","world","leetcode"], chars = "welldonehoneyr" Результат : 10 Пояснение : Мы можем сформировать строки "hello" и "world", поэтому 5 + 5 = 10. Ограничения: 1 <= words.length <= 1000 1 <= words[i].length, chars.length <= 100 words[i] и chars состоят из строчных букв английского алфавита   Идея решения Идея достаточно примитивна: нужно попробовать собрать ка...

Источник: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/ Дан массив целых чисел nums . За один ход можно выбрать один элемент из nums и заместить его на любой другой элемент массива . Вернуть минимальную разность между самым большим и самым маленьким элементом из nums за не более 3 шагов . Пример 1: Дано: nums = [5,3,2,4] Результат: 0 Поянение: Исходный массив [5,3,2,4] превращаем в [ 2 , 2 ,2, 2 ]. Разница между минимальным и максимальным значением: 2-2 = 0. Пример 2: Дано : nums = [1,5,0,10,14] Результат : 1 Explanation: Исходный массив [1,5,0,10,14] превращаем в [1, 1 ,0, 1 , 1 ]. Разница между минимальным и максимальным значением: 1-0 = 1. Ограничения: 1 <= nums.length <= 10 5 -10 9   <= nums[i] <= 10 9 Идея решения Если у нас 0 шагов, мы вернем max(A) - min(A) Если у нас 1 шаг, мы вернем min(the second max(A) - min(A), the max(A) - second min(A)) и так далее. Поскольку у нас не более 3 шагов, то у на...