Поиск в двумерной матрице II

Сложность: Средняя

Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:

- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).

Пример:

Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true

Решение задачи

Подмассив с наибольшим произведением

Сложность: Средняя

Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.

Подмассив - последовательный кусок исходного массива.

Пример:

Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.

Ввод: nums = [-2,0,-1]
Вывод: 0

Решение задачи

Текущая длительность котировок

Сложность: Средняя

Условие задачи: разработайте алгоритм, который сохраняет котировки некоторой акции текущего дня и осуществляет подсчёт, сколько дней до этого стоимость бумаг была меньше или равна цена на текущий день (включая текущий день).

Пример:

Ввод: ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Вывод: [null, 1, 1, 1, 2, 1, 4, 6]

Объяснение:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, так как цены за четыре предыдущих дня (включая сегодняшний) были меньше или равны;
stockSpanner.next(85); // return 6

Решение задачи

Подсчет узлов бинарного дерева

Сложность: Средняя

Условие задачи: дается корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.

Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.

Необходимо разработать алгоритм с временной сложностью менее O(n).

Пример:

Ввод: root = [1,2,3,4,5,6]
Вывод: 6
Объяснение: *во вложении

Решение задачи

Произведение подмассива меньше  K

Сложность: Средняя

Условие задачи: дается массив и целевое значение произведения, необходимо вернуть количесво подмассивов, в которых последовательные элементы будут при умножении давать значение меньшее или равное целевому.

Пример:

Ввод: nums = [10,5,2,6], k = 100
Вывод: 8
Объяснение: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

Решение задачи

Поиск суммы в бинарном дереве поиска

Сложность: Лёгкая

Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.

Пример:

Ввод: root = [5,3,6,2,4,null,7], k = 9
Вывод: true

Ввод: root = [5,3,6,2,4,null,7], k = 28
Вывод: false

Решение задачи

Слияние двух бинарных деревьев

Сложность: Лёгкая

Условие задачи: дается два бинарных дерева, надо осуществить их наложение друг на друга и вывести результат в новом дереве.

Наложение представляет из себя суммирование соответствующих значений из узлов двух деревьев.

Пример:

Ввод: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Вывод:[3,4,5,5,4,null,7]

Ввод: root1 = [1], root2 = [1,2]
Вывод: [2,2]

Решение задачи

Матрица Топлица

Сложность: Лёгкая Средняя Тяжёлая

Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.

Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.

Пример:

Ввод: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Вывод: true

Решение задачи

Перестановки, зависящие от регистра символа

Сложность: Средняя

Условие задачи: дана строка, содержащая как цифры, так и буквы. Надо вернуть всевозможные варианты перестановок строки, изменяя регистр букв.

Пример:

Ввод: s = "a1b2"
Вывод: ["a1b2","a1B2","A1b2","A1B2"]

Ввод: s = "3z4"
Вывод: ["3z4","3Z4"]

Решение задачи

Реализация класса MinStack

Сложность: Средняя

Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:

- void push(int val), который добавляет элемент в стак;
- void pop(), удаляющий верхний элемент стака;
- int top(), возвращающий верхний элемент на стаке;
- int getMin(), возвращающий минимальный элемент в стаке на момент вызова метода.

Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).

Пример:

Ввод:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Вывод:
[null,null,null,null,-3,null,0,-2]

Объяснение:

MinStack minStack = новый объект класса MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Решение задачи

Сцепка бинарного дерева из центрированного и прямого проходов

Сложность: Средняя

Условие задачи: даны два списка preorder и inorder, где preorder - центрированный порядок дерева (сenter > left > rigth), inorder - прямой проход (left > center > right). Оба - описывают структуру одного дерева, необходимо сконструировать бинарное дерево.

Пример:

Ввод: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Вывод: [3,9,20,null,null,15,7]

Ввод: preorder = [-1], inorder = [-1]
Вывод: [-1]

Решение задачи

Наибольший общий делитель строки

Сложность: Лёгкая

Условие задачи: для двух строк s и t мы говорим "t делит s" тогда и только тогда, когда s = t + ... + t (т.е. t объединяется с самим собой один или несколько раз).

Дается две строки str1 и str2, верните самую большую строку x, такую, что x делит как str1, так и str2.

Пример:

Ввод: str1 = "ABCABC", str2 = "ABC"
Вывод: "ABC"

Ввод: str1 = "ABABAB", str2 = "ABAB"
Вывод: "AB"

Решение задачи

Международная азбука Морзе

Сложность: Лёгкая

Условие задачи: международная азбука Морзе определяет стандартную кодировку, в которой каждая буква сопоставляется с серией точек и тире следующим образом:

"a" соответствует ".-",
"b" соответствует "-...",
"c" соответствует "-.-." и так далее.
Для удобства ниже приведена полная таблица для 26 букв английского алфавита:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Дан массив строк words, где каждое слово может быть записано как объединение азбуки Морзе каждой буквы.

Верните количество различных преобразований среди всех слов, которые у нас есть.

Пример:

Ввод: words = ["gin","zen","gig","msg"]
Вывод: 2

Объяснение:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

Ввод: words = ["a"]
Вывод: 1

Решение задачи

Среднее по уровню

Сложность: Лёгкая

Условие задачи: дается корень двоичного дерева, верните среднее значение узлов на каждом уровне в виде массива. Будут приняты ответы в пределах 10-5 от фактического ответа.

Пример:

Ввод: root = [3,9,20,null,null,15,7]
Вывод: [3.00000,14.50000,11.00000]

Решение задачи

Самый длинный путь с разными соседними символами

Сложность: Тяжёлая

Условие задачи: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 0, состоящее из n узлов, пронумерованных от 0 до n - 1. Дерево представлено родительским массивом с индексом 0 размера n, где родительский элемент[i] является родительским элементом узла i. Поскольку узел 0 является корневым, родительский элемент[0] == -1.

Вам также выдаются строки длиной n, где s[i] - символ, присвоенный узлу i.

Возвращает длину самого длинного пути в дереве таким образом, чтобы ни одной паре соседних узлов пути не был присвоен один и тот же символ.

Пример:

Ввод: parent = [-1,0,0,1,1,2], s = "abacbe"
Вывод: 3

Ввод: parent = [-1,0,0,0], s = "aabc"
Вывод: 3

Решение задачи

Перестановки II

Сложность: Средняя

Условие задачи: дается список чисел, который может содержать дубликаты, необходимо вычислить всевозможные уникальные перестановки.

Пример:

Ввод: nums = [1,1,2]
Вывод: [[1,1,2],
[1,2,1],
[2,1,1]]

Ввод: nums = [1,2,3]
Вывод: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Решение задачи

Строка из дерева

Сложность: Лёгкая

Условие задачи: дается корень двоичного дерева, постройте строку, состоящую из круглых скобок и целых чисел из двоичного дерева с помощью способа обхода предварительного порядка, и верните ее.

Опустите все пары пустых скобок, которые не влияют на взаимно однозначное сопоставление между строкой и исходным двоичным деревом.

Пример:

Ввод: root = [1,2,3,4]
Вывод: "1(2(4))(3)"

Ввод: root = [1,2,3,null,4]
Вывод: "1(2()(4))(3)"

Решение задачи

Количество точек на прямой

Сложность: Тяжёлая

Условие задачи: дается массив точек, где точки [i] = [xi, yi] представляют точку на плоскости X-Y, верните максимальное количество точек, которые лежат на одной прямой.

Пример:

Ввод: points = [[1,1],[2,2],[3,3]]
Вывод: 3

Ввод: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Вывод: 4

Решение задачи

Сбор урожая яблок

Сложность: Средняя

Условие задачи: дано неориентированное дерево, состоящее из n вершин, пронумерованных от 0 до n-1, в вершинах которого есть несколько яблок. Вы тратите 1 секунду, чтобы пройти по одному ребру дерева. Верните минимальное время в секундах, которое вы должны потратить, чтобы собрать все яблоки на дереве, начиная с вершины 0 и возвращаясь к этой вершине.

Ребра неориентированного дерева заданы в массиве ребер, где ребра[i] = [ai, bi] означают, что существует ребро, соединяющее вершины ai и bi. Кроме того, существует логический массив has Apple, где has Apple[i] = true означает, что в вершине i есть яблоко; в противном случае в ней нет никакого яблока.

Пример:

Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Вывод: 8


Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Вывод: 6

Решение задачи

Мост наименьшей длины

Сложность: Средняя

Условие задачи: на вход подается матрица, в которой 1 - суша, 0 - вода.

Остров представляет из себя совокупность частей суши, соединенных в четырех направлениях. На решетке существуют только два острова.

Можно изменить 0 на 1 для соединения двух островов в один.

Необходимо посчитать количество смен нулей на единицу для соединения двух островов.

Пример:

Ввод: grid = [[0,1],[1,0]]
Вывод: 1
Объяснение:

Ввод: grid = [[0,1,0],[0,0,0],[0,0,1]]
Вывод: 2

Решение задачи