Сообщения

Найти медиану среди элементов потока данных

 Источник: https://leetcode.com/problems/find-median-from-data-stream/ Медиана - это значение, которое находится в середине отсортированного списка целых чисел. Если размер списка четный, то медиана - это среднее арифметическое двух элементов из середины списка. Например, для arr = [2,3,4] , медиана = 3 . Для arr = [2,3] , медиана = (2 + 3) / 2 = 2.5 . Заимплементировать класс MedianFinder такой, что: MedianFinder()   iинициализирует объект MedianFinder . void addNum(int num) добавляет целое число num из потока данных в структуру данных. double findMedian() возвращает медиану полученных данных на текущий момент.  Пример 1: Дано ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Результат [null, null, null, 1.5, null, 2.0] Пояснение MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] me...

Эксклюзивное время исполнения функций

Изображение
Источник: https://leetcode.com/problems/exclusive-time-of-functions/ На однопотоково процессоре исполняется программа из n функций. У каждой функции есть уникальный ID между 0 и n-1. Вызовы функций хрнаятся в стеке: ID функции заносится в стек в начале исполнения функции и удаляется из него в конке исполнения функции. Функция, чей ID в верхушке стека - исполняющаяся в текущий момент функция. Каждый раз, когда функция начинается и заканчивается, мы пишем лог с ID, начало или конец исполнения, таймстемп. Дон список логов logs, где logs[i] предсталяет собой i-е сообщение лога в формате: "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что функция с ID=0 стартовала в момент времени, кjгда timestamp=3, "1:end:2" функция с ID=1 закончилась в момент времени timestamp=2.  Функиця может быть вызвана много раз, в том числе и рекурсивно. Эксклюзивное время фукнции - это сумма всех интервалов исполнения. Например, есл...

Разбиение числа на сумму с максимальным произведнием слагаемых

Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...

Бинарное дерево: вид справа

Изображение
Источник: https://leetcode.com/problems/binary-tree-right-side-view/ Дан корень root бинарного дерева. Представьте, что вы смотрите на дерева справа. Вернуть его узлы, которые вам видны, сверху вниз. Пример 1: Дано: root = [1,2,3,null,5,null,4] Результат: [1,3,4] Пример 2: Дано: root = [1,null,3] Результат: [1,3] Пример 3: Дано: root = [] Результат: []   Ограничения: Количество узлов в дереве: [0, 100] . -100 <= Node.val <= 100 Идея решения Мы будем обходить дерево в порядке BFS, то есть по "этажам". Элемента "этажа" будем записывать так, чтобы самый правыйэлемент шел первым. Его будем записывать и в результат, а остальные элементы этажа нам нужны, чтобы подсчитать следующий "этаж". Имплементация class Solution {     public List<Integer> rightSideView(TreeNode root) {         List<Integer> result = new ArrayList(); //   результат запишем сюда         Queue<Tre...

Отсортировать массив, трансформированный квадратичной функцией

Изображение
Источник: https://leetcode.com/problems/sort-transformed-array/ Дан отсортированный массив целых чисел nums и три клэффициента a ,   b   and   c . Применить квадратичную фугкцию f(x) = ax 2   + bx + c к каэжлму элементу nums[i]в массивеи вернуть результат в отсортированном порядк . Пример 1: Дано: nums = [-4,-2,2,4], a = 1, b = 3, c = 5 Результат: [3,9,15,33] Пример 2: Дано : nums = [-4,-2,2,4], a = -1, b = 3, c = 5 Результат: [-23,-5,1,7] Идея решения Квадратичную функцию можно переписать: ax^2+bx+c = a(x+p)^2 + q, где p и q можно выразить через a, b, c. Но в переписанной форме мы легко можем представить, где распаложена на декартовой плоскости парабола: она будет смещена по горизонтальной оси на -p, и по вертикальной оси на q. Например: x^2-7x+10=(x-3,5)^2-2,5. То  есть самая нижняя точка параболы смещена вправо на 3,5 и вниз на 2,5, как показано на рисунке:     Если коэффициент a отрицателен, то парабола будет повернута вниз, а экстрем...

Вода впадает в оба океана

Изображение
Источник: https://leetcode.com/problems/pacific-atlantic-water-flow/ Остров представлен матрицей m x n граничит с Тихим и Атлантическим океанами: сверху и слева от острова Тихий океан, снизу и справа - Атдантический. Остров поделен на ячейки, соответствующие ячейкам матрицы. Значение каждой ячейки - это высота над уровнем моря. На остров проливается дождь. Дождь стекает по поверхности острова и вода впадает в океаны в 4 направлениях: вверх, вниз, вправо, влево. Вода может перетекать из первой ячейки во вторую, если значение первой ячейки больше или равно значения второй ячейки. Вернуть список ячеек, заданных своими координатами, из которых вода стекает в оба океана. На изображении выше виден пример, что остров задан матрицей: [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]. Желтым цветом отмечены ячейки, из которых вода стекает в оба океана: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Идея решения Мы отдельно подсчитываем ячейки, из которых вода может стечь в один океан,...