Coding interview scrapbook

Источник:  https://leetcode.com/problems/split-array-largest-sum/ Дан массив nums состоящий из целочисленных положитльных элементов, и дано целое число m . Нужно разделить этот массив на m непустых непрерывных подмассивов. При этом самая максимальная сумма элементов в этих подмассивах должна быть минимизирована. Пример 1: Дано: nums = [7,2,5,10,8], m = 2 Результат: 18 Пояснение: Можно разбить массив на 2 подмассива четырьмя способами. Но мы выберем разбиение на [7,2,5] и [10,8], потому что именно здесь максимальная сумма = 18, и она минимальна по сравнению с другими разбиениями. Пример 2: Дано : nums = [1,2,3,4,5], m = 2 Результат : 9 Пример 3: Дано : nums = [1,4,4], m = 3 Результат : 4 Ограничения: 1 <= nums.length <= 1000 0 <= nums[i] <= 10 6 1 <= m <= min(50, nums.length)   Идея решения   Переформулируем эту задачу в утилитарном виде. Есть набор коробок разного размера. Порядок коробок не должен меняться, все коробки заранее известны. Кор...

Источник: https://leetcode.com/problems/lru-cache/ Создайте структуру данных для  Least Recently Used (LRU) cache . Эта структура поддерживает две операции: get и put . get(key)   - извлекает значение (всегда положительное) по ключу key, если ключ присутствует в кэше, а в противном случае возвращает -1. put(key, value)   - помещает или изменяет значение по ключу.  Когда кэш достигает своей вместимости, наименее используемые элемент можно удалить и поместить новый элемент. Кэш инициализируется положительной вместимостью. Сделайте так, чтобы обе операции выполнялись за время со сложностью O(1) , то есть за константу. Пример 1: Входные данные ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Результат [null, null, null, 1, null, -1, null, -1, 3, 4] Пояснение LRUCache lRUCache = new LRUCache(2);...

Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...

Дана непустая строка s , в которой можно удалить 0 или 1 символ. Выяснить, можно ли таким образом получить палиндром. Пример 1: Дано: "aba" Результат: True Пример 2: Дано: "abca" Результат: True Пояснение: Чтобы получился палиндром, можно удалить символ 'c'. Примечания:   Строка состоит из букв нижнего регистра a-z. Максимальная длина строки равна 50000. Идея решения: Палиндром - это строка, которая читается одинаково, как слева направо, так и справа налево. Типовая проверка палиндрома состоит в том, что мы просматриваем символы одновременно слева и справа, два указателя движутся навстречу друг к другу, пока не встретятся. В нашей задаче допускается вариант, что есть какой-то лишний символ. В таком случае, просматривая строку на предмет палиндрома, возникнет ситуация, когда символ справа не равен символу слева. В таком случае нам нужно рассмотреть два варианта: если мы удалим символ справа, то получится палиндром? если мы удалим символ слева, то получи...

У нас есть массив points , в котором хранятся координаты точек на декартовой поверхности. Найи K точек ближайшик к центру (0, 0) . (Здесь мы имеем в виду, что расстояние между точками Евклидово) Можно вернуть список ближайших точек отсортированных в любом порядке. Ответ гарантированно существует и единственнй. Пример 1: Дано: points = [[1,3],[-2,2]] , K = 1 Результат: [[-2,2]] Пояснение: Расстояние между (1, 3) и нулевой точкой = sqrt(10). Расстояние между (-2, 2) и нулевой точкой = sqrt(8). Поскольку sqrt(8) < sqrt(10), (-2, 2) - ближайшая точка. Нам нужно найти только K = 1 блиайших точек, поэтому в ответе только [[-2,2]]. Пример 2: Дано: points = [[3,3],[5,-1],[-2,4]] , K = 2 Результат: [[3,3],[-2,4]] (Ответ [[-2,4],[3,3]] тоже принимается.) Примечания: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000 Идея решения Идея достаточно проста: создать массив расстояний от каждой точки до нулевой; отсортировать его; ...

Дана матрица целых чисел. Найти самый длинный путь, в котором чисоа возастают. Из каждой ячейки матрицы можно двигаться в 4 направлениях: вверх, вниз, влево, вправо. Нельзя двигаться диагонально или за пределы матриы (то есть выйдя за пределы матрицы в конце строки/столбца, вы не попадаете в начало следующей строки/столбца). Пример 1: Дано: nums = [ [ 9 ,9,4], [ 6 ,6,8], [ 2 , 1 ,1] ] Результат: 4 Пояснение: Самый длинный возрастающий путь состоит из значений [1, 2, 6, 9] . Пример 2: Дано: nums = [ [ 3 , 4 , 5 ], [3,2, 6 ], [2,2,1] ] Результат: 4 Пояснение: Самый длинный возрастающий путь состоит из значений [3, 4, 5, 6] . Идея решения 1 (DFS) Мы должны применить поиск в глубину (DFS) для каждой ячейки. При этом будем кэшировать промежуточные результаты, чтобы не пересчитвать их повторно. Поскольку ячеек в матрице O(mn) и для каждой ячейки нам нужно поиском обойти все другие ячейки, то общая сложность алгоритма будет O ( m 2 n 2 ) . Мы рекурсивно вызываем dfs(x, y...