Coding interview scrapbook

 Источник: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/ Даны два узла p и q бинарного дерева, вернуть их ближайший общий предокт, lowest common ancestor (LCA) . У каждого узла есть указатель на родителя. Определение Node следуюшее : class Node { public int val; public Node left; public Node right; public Node parent; } По определению LCA в Wikipedia : "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow   a node to be a descendant of itself )." Пример 1: Дано: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Результат: 3 Пояснение: 3 - ближайший общий предок и для 5, и для 1 Пример 2: Дано: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Результат: 5 Пояснение: 5 - это потомок самого себя, согласно определнию LCA, значит LCA=5 для 5 и 4. Пример 3: Дано: root = [1,2], p = 1, q = 2 Результат: 1 Ограничения: Количество узлов в дереве н...

Источник: https://leetcode.com/problems/shortest-distance-from-all-buildings/ Дана матрица размером m x n называется grid заполнена значениями 0 ,   1 или 2 , где: каждый 0 означает пустое пространство, на которое можно вступить; каждая 1 означает здание, на эту ячейку нельзя вступить; каждая 2 означает препятствие, на эту ячейку нельзя вступить. Мы хотим построить дом на пустом пространстве так, чтобы расстояние от него до остальных домов было наикратчайшим. Разрешения направления движения по матрице: вверх, вниз, вправо, влево. В ответе указать наикратчайшее рсстояние для такого дома. Если невозможно построить дом, чтобы остальные дома были для него доступны, вернуть -1. Дистанция считается, как Manhattan Distance , где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y| . Пример 1: Дано: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] Результат: 7 Пояснение: Три здания находятся в чейках (0,0), (0,4), (2,2), и препятсвие в ячейке (0,2). Ячейка (1,2) пустая и она идеальна...

 Источник: https://leetcode.com/problems/merge-k-sorted-lists Дан массив из k связных списокв lists , элементы в каждом идут в возрастающем порядке. Объединить все связные списки в один список,в к отором элементы идут в возрастающем порядке, и вернуть его. Пример 1: Дано: lists = [[1,4,5],[1,3,4],[2,6]] Результат: [1,1,2,3,4,4,5,6] Пояснение: Исходные списки такие: [ 1->4->5, 1->3->4, 2->6 ] если их объединить, то мы получим такой список: 1->1->2->3->4->4->5->6 Пример 2: Дано : lists = [] Результат : [] Пример 3: Дано : lists = [[]] Результат : [] Ограничения: k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] содержит элементы отсортированные в возрастающем порядке Скммарная длиннавсех списков не превышает 10^4 . Идея решения Мы можем объединить два списка в один отсортированный за линейное время. Для этого мы сканируем оба списка и заносим в результат наименьший...

Источник: https://leetcode.com/problems/integer-to-english-words/ Дано целое число num. Вывести его словами на английском языке. Пример 1: Дано: num = 123 Результат: "One Hundred Twenty Three" Пример 2: Дано : num = 12345 Результат : "Twelve Thousand Three Hundred Forty Five" Пример 3: Дано : num = 1234567 Результат : "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Пример 4: Дано : num = 1234567891 Результат : "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One" Ограничения: 0 <= num <= 2 31   - 1 Имплементация class Solution {     public String numberToWords(int num) {         if(num==0) {             return "Zero";         }         return helper(num);     }     public String helper(int n...

Источник: https://leetcode.com/problems/product-of-array-except-self/ Дан массив целых чисел nums , подсчитать массив answer такой, что answer[i] равен произведению всех элементов из nums за исключением nums[i] . Алгоритм должен быть линейным и не должен содержать операций деления. Пример 1: Дано: nums = [1,2,3,4] Результат: [24,12,8,6] Пример 2: Дано : nums = [-1,1,0,-3,3] Результат : [0,0,9,0,0] Ограничения: 2 <= nums.length <= 10 5 -30 <= nums[i] <= 30 Произведение любого суффикса или префикса массива nums гарантированно помещается в целое 32-битное число. Идея решения Мы можем итеративно подсчитвать произведение всех элементов слева от индекса i, продвигаясь по i от 0 до n (длинна массива). И запоминать в массиве L длинной n промежуточное произведение. Затем мы сканируем массив в обратном направлении от n до 0, и считаем произведение всех элементов слева от индекса i. Эти значения мы можем тоже запомнить во временном массиве R. L[i]*R[i] даст искомый результа...

Источник: https://leetcode.com/problems/knight-dialer/ Шахматный конь ходит буквой Г: две клетки в любом направлении по вертикали/горизонтали, и ещё одна клетка в перпендикулярном направлении по горизонтали/вертикали. Все возможные ходы показаны на диаграмме: Допустим, конь ходит по телефонной клавиатуре, только по кнопкам с цифрами (синие кнопки на диаграмме ниже): Дано целое число n , подсчитать, сколько различных номеров можно набрать за n ходов. Ответ можно вернуть по модулю 10 9   + 7 . Пример 1: Дано: n = 1 Результат: 10 Пояснение: Нам нужно набрать номер длинной 1, поэтому нужно расположить коня в каждой из 10 кнопок - и это и будет результат. Пример 2: Дано : n = 2 Результат : 20 Пояснение : Мы можем набрать: [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94] Пример 3: Дано : n = 3 Результат : 46 Пример 4: Дано : n = 4 Результат : 104 Пример 5: Дано : n = 3131 Результат : 136006598 Пояснение : Принимаем во внимание результат ...