Coding interview scrapbook

Источник: https://leetcode.com/problems/delete-and-earn/ Дан массив nums целых чисел. Из массива можно удалить эемент nums[i] и заработать nums[i] очков . После чего нужно удалить все элементы равные nums[i] - 1 или nums[i] + 1 . Перед проведением операци йдаления у вас 0 очков. Вернуть максимальное значение очков, которые можно заработать, применяя операцию "удалить и заработать", описанную выше. Пример 1: Дано: nums = [3,4,2] Результат: 6 Пояснение: Удялем и зарабатываем 4, затем 3 тоже удаляем, поскольку 3=4-1. Остается [2]. Удаляем 2 и зарабатываем +2. Итого 4+2=6. Пример 2: Дано : nums = [2,2,3,3,3,4] Результат : 9 Пояснение : Удаляем и зарабатываем 3. 2=3-1 и 4=3+1 - удаляем ВСЕ 2 и 4. Остается [3,3]. Удаляем и зарабатываем +3, но больше нет соседних значений (2 и 4). Остается [3]. Удалеям и зарабатываем ещё раз +3. Итого 3+3+3=9. Огранияения: 1 <= nums.length <= 2 * 10 4 1 <= nums[i] <= 10 4 Идея решения Заметим, что если в массиве есть дубл...

Источник: https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/ Дань корень root двоичного дерева с n вершинами , где значение каждой вершины уникально в интервале от 1 до n . Дана также последовательность voyage из n элементов , которая обозначает желаемый прямой (pre-order: root, left, right) обход дерева. Каждая вершина в исходном дереве может быть развернута, то есть его левое поддерево становится правым, а правое - левым. Например, разворот вершины 1 дает такой эффект: Развернуть наименьшее число вершин, чтобы прямой обход финального дерева  соответствовал последовательности voyage . Вернуть список развернутых вершин (их порядок в ответе не имеет значения). Если невозможно никакими разворотами получить voyage , вернуть список в единственным элементом [-1] . Пример 1: Дано: root = [1,2], voyage = [2,1] Результат: [-1] Пояснение : Невозможно никак развернуть это дерево, чтобы получить искомую последовательность. Прямой обход подразумевает, что п...

Источник: https://leetcode.com/problems/meeting-rooms/ Дан массив интервалов, в которые проходят совещания intervals, где intervals[i] = [start i , end i ] . Определить, можно ли посетить все интервалы. Пример 1: Дано: intervals = [[0,30],[5,10],[15,20]] Результат: false Пример 2: Дано : intervals = [[7,10],[2,4]] Результат : true Ограничения: 0 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i   < end i   <= 10 6 Идея решения Фактически нам нужно отследить, перекрываются ли интервалы. Если перекрываются, что человек может присутствовать на одной встрече, а в это время начнется другая встреча. Два интервала, например [start1, end1] и [start2, end2] перекрываются, когда  min(end1, end2)>max(start1, start2). min(end1, end2) - это завершение первого интервала, max(start1, start2) - это начало второго интервала. И если первый интервал завершается позже начала второго интервала, то у нас имеет место перекрытие интервалов. Без ограни...

Источник: https://leetcode.com/problems/sum-of-subsequence-widths/ Дан массив целых чисел nums . Для каждой непустой подпоследовательности  seq , назовем шириной разницу между минимальным и максимальным элементами подпоследовательности seq . Вернуть сумму ширин всех подпоследовательностей массива nums .  Поскольку ответ может быть очень большим, вернуть ответ по по модулю 10 9   + 7 . Пример 1: Дано: nums = [2,1,3] Результат: 6 Пояснение: Подпоследовательности массива: [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3]. Их соответствующие ширины: 0, 0, 0, 1, 1, 2, 2. Сумма ширин = 6. Примечания: 1 <= nums.length <= 20000 1 <= nums[i] <= 20000 Идея решения Исходная последовательность чисел не имеет значения, поэтому без ограничения общности мы можем отсортировать массив. Для каждого элемента отсортированного массива A[i] : Существуют i элементов которые меньше его, поэтому существуют 2 ^ i подпоследовательносетй,в которых A[i] - это максимум. Поэтому м...

Источник задачи: https://leetcode.com/problems/binary-tree-pruning Дан корень бинарного дерева. В его вершинах значение может быть 1 или 0. Обрезать поддеревья этого дерева, целиком состоящие из 0. Пример 1: Дано: [1,null,0,0,1] Результат: [1,null,0,null,1] Пояснение: Только оранжевые составляют поддерево, целиком состоящее из 0 Пример 2: Дано : [1,0,1,0,0,0,1] Результат : [1,null,1,null,1]   Пример 3: Дано : [1,1,0,1,1,0,1,0] Результат : [1,1,0,1,1,null,1] Примечения: В дереве не более 200 вершин. Значения вершины принимает 1 или 0.  Идея решения Лучше проверить все листья (вершины без поддеревьев) дерева. Если лист содержит значение 0, то его можно обрезать. У родителя этого листа может быть другой лист. Если он тоже 0, то мы и его обрежем, и тогда сам родитель станет листом. И его мы тоже проверим. Если же тот другой лист = 1, то мы отсавим эту ветку в покое, даже если родитель = 0. Мы не можем применить BFS, потому что мы теряем связь с родителями. Чтобы поддер...

Источник: https://leetcode.com/problems/frog-jump/ Лягушка переберитается через реку. Река разделена на участки, в каждом участке есть камни (но их также может и не быть), по которым прыгает лягушка. Оягушке нельзя упасть в воду. Дан список stones позиций (на участках), отсортированных в возрастающем порядке. Определить, может ли лягушка перейти реку, приземлившись на поседний камень. В начальной позиции лягука на первом камне и может прыгнуть вперед на 1 участок (ход). Если предыдущий прыжок лягушки был на k ходов, ее следующий прыжко может быть на k - 1 ,   k , или k + 1 ходов . Прыгать можно только вперед. Пример 1: Дано: stones = [0,1,3,5,6,8,12,17] Результат: true Пояснение: Лягушка может допрыгнуть до последнего камня так:  1. на k=1 ход до 2-го камня (=1). 2. на k=2 хода до 3-го камня (=3). 2. на k=2 хода до 4-го камня (=5). 2. на k=3 хода до 6-го камня (=8). 2. на k=4 хода до 7-го камня (=12). 2. на k=5 хода до 8-го камня (=17). Пример 2: Дано : stones = [0,1,2,...

Источник: https://leetcode.com/problems/plus-one/ Дан не пустой массив десятичных чисел, которые представляют собой неотрицательное число. Увеличить это число на 1. Старший разряд числа находится в голове массива (в индексе 0)б каждая чейка массива содержит число от 0 до 9. Данное представление числа не имеет в начале нулей, кроме случая, когда массив и представляет собой 0. Пример 1: Дано: digits = [1,2,3] Результат: [1,2,4] Пояснение: Исходный массив кодирует число 123. 123+1=124. Пример 2: Дано : digits = [4,3,2,1] Результат : [4,3,2,2] Пример 3: Дано : digits = [0] Результат : [1] Ограничения: 1 <= digits.length <= 100 0 <= digits[i] <= 9 Идея решения Мы все в школе учились складыватьв столбик, когда к младшему разряду числа добавляется  младший разряд другого числа. Если их сумма меньше 9, то в младший разряд результирующего числа записывается эта сумма. Если же сумма больше 9, то в младший разряд записываем остаток от деления на 10, а целочисленную часть от...