Сообщения

Максимальная сумма по подмассиву с одним удалением

Источник: https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ Дан массив целых чисел, вернуть сумму по не пустому подмассиву (состоит из смежных элементов исходного массива), который можно получить удалением не более одного элемента массива. Другими словами, можно выбрать подмассив и опционально удалить из него один элемент, чтобы получить подмассив с максимальной суммой элементов. Пример 1: Дано: arr = [1,-2,0,3] Результат: 4 Пояснение: Мы можем взять весь иходный массив [1, -2, 0, 3] и удалить из него -2, и таким образом получим подмассив [1, 0, 3], сумма элементов которого даст максимум по всем возможным подмассивам. Пример 2: Дано: arr = [1,-2,-2,3] Результат: 3 Пояснение: Мы просто берем подмассив [3] и он даст максимально возможную сумму по всем подмассивам даже с удалением одного элемента. Пример 3: Дано : arr = [-1,-1,-1,-1] Результат: -1 Пояснение:  Результата не существует. Мы можем выбрать подмассив [-1] и удалить из него -1, и мы получим тогда...

Максимальная сумма в k-конкатенации массива

Источник: https://leetcode.com/problems/k-concatenation-maximum-sum/ Дан целочисленный массив arr и целое число k . Сделайте конкатенацию массива k раз . Например, если arr = [1, 2] и k = 3 , то новый массив будет [1, 2, 1, 2, 1, 2] . Надо посчитать максимальную сумму, которую можно получить из какого-либо подмассива этого нового массива. Заметьте, что подмассив может быть нулевой длинны, и тогда сумма его элементов будет рана 0. Ответ сфоррмировать по модулю 10 9   + 7 . Пример 1: Дано: arr = [1,2], k = 3 Результат: 9 (все элементы нового массива) Пример 2: Дано: arr = [1,-2,1], k = 5 Результат: 2 (две подряд идущие 1) Пример 3: Дано: arr = [-1,-2], k = 7 Результат: 0 (все элементы отрицательные, значит максимальную сумму даст пустой подмассив). Ограничения: 1 <= arr.length <= 10 5 1 <= k <= 10 5 -10 4   <= arr[i] <= 10 4 Идея решения Мы можем выделить несколько случаев: Case 1 : когда k == 1 , тогда нам нужно найти только подмассив с максимал...

k самых частых элементов

Источник: https://leetcode.com/problems/top-k-frequent-elements/ Дан массив целых чисел nums и число k , вернуть   k самых частых элементов . Самые частые элементы можно вернуть в любом порядке. Пример 1: Дано: nums = [1,1,1,2,2,3], k = 2 Результат: [1,2] Пример 2: Дано: nums = [1], k = 1 Результат: [1] Ограниечения: 1 <= nums.length <= 10 5 k в интервале [1, число уникальных жлементов в массиве] . Изветно, что решение существует и уникально . Алгоритм должен быть быстрее O(n log n) , где n - размер массива (то есть обойтись без сортировки).   Имплементация class Solution {     public int[] topKFrequent(int[] nums, int k) {         // O(1) time         if (k == nums.length) {             return nums;         }               ...

Ближайший общий предок в бинарном дереве

Изображение
 Источник: 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) пустая и она идеальна...

Объединить k отсортированных списков в один отсортированный список

 Источник: 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 . Идея решения Мы можем объединить два списка в один отсортированный за линейное время. Для этого мы сканируем оба списка и заносим в результат наименьший...