Поиск суммы в бинарном дереве поиска
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дано бинарное дерево поиска, а также целевое значение. Необходимо определить, имеется ли в дереве два таких значения, в сумме дающие целевое значение, или же нет.
Пример:
Ввод:
root = [5,3,6,2,4,null,7], k = 9Вывод:
trueВвод:
root = [5,3,6,2,4,null,7], k = 28Вывод:
falseРешение задачи
👍3
Слияние двух бинарных деревьев
Сложность: Лёгкая
Условие задачи: дается два бинарных дерева, надо осуществить их наложение друг на друга и вывести результат в новом дереве.
Наложение представляет из себя суммирование соответствующих значений из узлов двух деревьев.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Лёгкая
Условие задачи: дается два бинарных дерева, надо осуществить их наложение друг на друга и вывести результат в новом дереве.
Наложение представляет из себя суммирование соответствующих значений из узлов двух деревьев.
Пример:
Ввод:
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]Решение задачи
Поток данных в виде непересекающихся интервалов
Сложность: Тяжёлая
Условие задачи: дается ввод потока данных из неотрицательных целых чисел a1, a2, ..., an, суммируйте числа, видимые до сих пор, в виде списка непересекающихся интервалов.
Реализуйте класс сводных диапазонов:
Сводные диапазоны() инициализирует объект пустым потоком.
void addNum(значение int) Добавляет целочисленное значение в поток.
int[][] getinterval() Возвращает сводку целых чисел в потоке в данный момент в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по началу.
Пример:
Ввод: ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Вывод: [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
Решение задачи
Сложность: Тяжёлая
Условие задачи: дается ввод потока данных из неотрицательных целых чисел a1, a2, ..., an, суммируйте числа, видимые до сих пор, в виде списка непересекающихся интервалов.
Реализуйте класс сводных диапазонов:
Сводные диапазоны() инициализирует объект пустым потоком.
void addNum(значение int) Добавляет целочисленное значение в поток.
int[][] getinterval() Возвращает сводку целых чисел в потоке в данный момент в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по началу.
Пример:
Ввод: ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Вывод: [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
Решение задачи
👍2🎄2
Матрица Топлица
Сложность: Лёгкая Средняя Тяжёлая
Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.
Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.
Пример:
Ввод: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Вывод: true
Решение задачи
Сложность: Лёгкая Средняя Тяжёлая
Условие задачи: дается матрица mxn, верните значение true, если матрица является Теплициевой. В противном случае верните значение false.
Матрица является Теплициевой, если каждая диагональ от верхнего левого края до нижнего правого имеет одинаковые элементы.
Пример:
Ввод: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Вывод: true
Решение задачи
❤1👍1
Перелет с наименьшей ценой
Сложность: Средняя
Условие задачи: есть n городов, соединенных некоторым количеством рейсов. Вам предоставляется массив рейсов, где рейсы[i] = [fromi, toi, pricei] указывают, что есть рейс из города из i в город toi со стоимостью pricei.
Вам также даны три целых числа src, dst и k, возвращающие самую дешевую цену из src в dst не более чем с k остановками. Если такого маршрута нет, верните значение -1.
Пример:
Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700
Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200
Решение задачи
Сложность: Средняя
Условие задачи: есть n городов, соединенных некоторым количеством рейсов. Вам предоставляется массив рейсов, где рейсы[i] = [fromi, toi, pricei] указывают, что есть рейс из города из i в город toi со стоимостью pricei.
Вам также даны три целых числа src, dst и k, возвращающие самую дешевую цену из src в dst не более чем с k остановками. Если такого маршрута нет, верните значение -1.
Пример:
Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700
Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200
Решение задачи
👍3
Треугольник
Сложность: Средняя
Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на i-ой позиции можно перемещаться на i-ую или i+1 позицию следующего ряда.
Пример:
Ввод:
Объяснение:
Минимальный путь выглядит следующим образом:
Решение задачи
Сложность: Средняя
Условие задачи: дан двумерный массив, надо посчитать минимальную сумму от вершины тругольника до его основания.
На каждом шаге, анходясь на i-ой позиции можно перемещаться на i-ую или i+1 позицию следующего ряда.
Пример:
Ввод:
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Вывод: 11
Объяснение:
треуголльник выглядит следующим образом:
2
3 4
6 5 7
4 1 8 3
Минимальный путь выглядит следующим образом:
2 + 3 + 5 + 1 = 11.Решение задачи
👍2
Перестановки, зависящие от регистра символа
Сложность: Средняя
Условие задачи: дана строка, содержащая как цифры, так и буквы. Надо вернуть всевозможные варианты перестановок строки, изменяя регистр букв.
Пример:
Ввод: s = "a1b2"
Вывод: ["a1b2","a1B2","A1b2","A1B2"]
Ввод: s = "3z4"
Вывод: ["3z4","3Z4"]
Решение задачи
Сложность: Средняя
Условие задачи: дана строка, содержащая как цифры, так и буквы. Надо вернуть всевозможные варианты перестановок строки, изменяя регистр букв.
Пример:
Ввод: s = "a1b2"
Вывод: ["a1b2","a1B2","A1b2","A1B2"]
Ввод: s = "3z4"
Вывод: ["3z4","3Z4"]
Решение задачи
👍3
Реализация класса MinStack
Сложность: Средняя
Условиеи задачи: разработай пользовательский класс MinStack(), который будет иметь следующие методы:
-
-
-
-
Требуется реализовать все методы таким образом чтобы каждый из них имел временную сложность O(1).
Пример:
Ввод:
Сложность: Средняя
Условиеи задачи: разработай пользовательский класс 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
Решение задачиСхожие деревья
Сложность: Лёгкая
Условие задачи: необходимо рассмотреть конечные листья бинарного дерева слева направо, а точнее их значения.
Два дерева считаются схожими по последним потомкам в случае если последовательность последних потомков и в первом и во втором деревьях идентична.
Пример:
Ввод: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Вывод: true
Объяснение: *во вложении
Решение задачи
Сложность: Лёгкая
Условие задачи: необходимо рассмотреть конечные листья бинарного дерева слева направо, а точнее их значения.
Два дерева считаются схожими по последним потомкам в случае если последовательность последних потомков и в первом и во втором деревьях идентична.
Пример:
Ввод: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Вывод: true
Объяснение: *во вложении
Решение задачи
👍2🎄1
Сцепка бинарного дерева из центрированного и прямого проходов
Сложность: Средняя
Условие задачи: даны два списка 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]
Решение задачи
Сложность: Средняя
Условие задачи: даны два списка 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]
Решение задачи
👍4
Заправочная станция
Сложность: Средняя
Условие задачи: вдоль кольцевого маршрута расположено n заправочных станций, где количество газа на i-й станции равно gas[i].
У вас есть автомобиль с неограниченным запасом бензина, и проезд от i-й станции до следующей (i + 1)-й станции обходится в стоимость [i] бензина. Вы начинаете путешествие с пустым баком на одной из заправочных станций.
Учитывая два целочисленных массива gas и cost, верните индекс начальной заправочной станции, если вы можете объехать круг один раз по часовой стрелке, в противном случае верните -1. Если существует решение, оно гарантированно будет уникальным
Пример:
Ввод: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Вывод: 3
Ввод: gas = [2,3,4], cost = [3,4,3]
Вывод: -1
Решение задачи
Сложность: Средняя
Условие задачи: вдоль кольцевого маршрута расположено n заправочных станций, где количество газа на i-й станции равно gas[i].
У вас есть автомобиль с неограниченным запасом бензина, и проезд от i-й станции до следующей (i + 1)-й станции обходится в стоимость [i] бензина. Вы начинаете путешествие с пустым баком на одной из заправочных станций.
Учитывая два целочисленных массива gas и cost, верните индекс начальной заправочной станции, если вы можете объехать круг один раз по часовой стрелке, в противном случае верните -1. Если существует решение, оно гарантированно будет уникальным
Пример:
Ввод: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Вывод: 3
Ввод: gas = [2,3,4], cost = [3,4,3]
Вывод: -1
Решение задачи
👍3👎2🎄1
Пацифисты
Сложность: Средняя
Условие задачи: вы менеджер баскетбольной команды. Для предстоящего турнира вы хотите выбрать команду с наибольшим общим счетом. Счет команды - это сумма очков всех игроков в команде.
Однако баскетбольной команде не разрешается иметь конфликтов. Конфликт возникает, если у младшего игрока строго более высокий балл, чем у старшего игрока. Конфликт не возникает между игроками одного возраста.
Учитывая два списка, баллы и возрасты, где каждый балл [i] и возраст [i] представляют счет и возраст i-го игрока соответственно, возвращают наивысший общий балл всех возможных баскетбольных команд.
Пример:
Ввод: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Вывод: 34
Ввод: scores = [4,5,6,5], ages = [2,1,2,1]
Вывод: 16
Решение задачи
Сложность: Средняя
Условие задачи: вы менеджер баскетбольной команды. Для предстоящего турнира вы хотите выбрать команду с наибольшим общим счетом. Счет команды - это сумма очков всех игроков в команде.
Однако баскетбольной команде не разрешается иметь конфликтов. Конфликт возникает, если у младшего игрока строго более высокий балл, чем у старшего игрока. Конфликт не возникает между игроками одного возраста.
Учитывая два списка, баллы и возрасты, где каждый балл [i] и возраст [i] представляют счет и возраст i-го игрока соответственно, возвращают наивысший общий балл всех возможных баскетбольных команд.
Пример:
Ввод: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Вывод: 34
Ввод: scores = [4,5,6,5], ages = [2,1,2,1]
Вывод: 16
Решение задачи
👍2
Наибольший общий делитель строки
Сложность: Лёгкая
Условие задачи: для двух строк s и t мы говорим "t делит s" тогда и только тогда, когда s = t + ... + t (т.е. t объединяется с самим собой один или несколько раз).
Дается две строки str1 и str2, верните самую большую строку x, такую, что x делит как str1, так и str2.
Пример:
Ввод: str1 = "ABCABC", str2 = "ABC"
Вывод: "ABC"
Ввод: str1 = "ABABAB", str2 = "ABAB"
Вывод: "AB"
Решение задачи
Сложность: Лёгкая
Условие задачи: для двух строк s и t мы говорим "t делит s" тогда и только тогда, когда s = t + ... + t (т.е. t объединяется с самим собой один или несколько раз).
Дается две строки str1 и str2, верните самую большую строку x, такую, что x делит как str1, так и str2.
Пример:
Ввод: str1 = "ABCABC", str2 = "ABC"
Вывод: "ABC"
Ввод: str1 = "ABABAB", str2 = "ABAB"
Вывод: "AB"
Решение задачи
👍1
Считалка
Сложность: Средняя
Условие задачи: последовательность "Посчитай и скажи" - это последовательность строк цифр, определяемая рекурсивной формулой:
посчитайте и скажите(1) = "1"
countAndSay(n) - это способ, которым вы бы "сказали" строку цифр из countAndSay(n-1), которая затем преобразуется в другую строку цифр.
Чтобы определить, как вы "произносите" строку цифр, разделите ее на минимальное количество подстрок таким образом, чтобы каждая подстрока содержала ровно одну уникальную цифру. Затем для каждой подстроки произнесите количество цифр, затем произнесите цифру. Наконец, объедините каждую указанную цифру.
Например, высказывание и преобразование для цифровой строки "3322251" (*во вложении)
Дается положительное целое число n, верните n-й член последовательности "посчитай и скажи".
Пример:
Ввод: n = 1
Вывод: "1"
Решение задачи
Сложность: Средняя
Условие задачи: последовательность "Посчитай и скажи" - это последовательность строк цифр, определяемая рекурсивной формулой:
посчитайте и скажите(1) = "1"
countAndSay(n) - это способ, которым вы бы "сказали" строку цифр из countAndSay(n-1), которая затем преобразуется в другую строку цифр.
Чтобы определить, как вы "произносите" строку цифр, разделите ее на минимальное количество подстрок таким образом, чтобы каждая подстрока содержала ровно одну уникальную цифру. Затем для каждой подстроки произнесите количество цифр, затем произнесите цифру. Наконец, объедините каждую указанную цифру.
Например, высказывание и преобразование для цифровой строки "3322251" (*во вложении)
Дается положительное целое число n, верните n-й член последовательности "посчитай и скажи".
Пример:
Ввод: n = 1
Вывод: "1"
Решение задачи
👍1
Международная азбука Морзе
Сложность: Лёгкая
Условие задачи: международная азбука Морзе определяет стандартную кодировку, в которой каждая буква сопоставляется с серией точек и тире следующим образом:
"a" соответствует ".-",
"b" соответствует "-...",
"c" соответствует "-.-." и так далее.
Для удобства ниже приведена полная таблица для 26 букв английского алфавита:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Дан массив строк words, где каждое слово может быть записано как объединение азбуки Морзе каждой буквы.
Верните количество различных преобразований среди всех слов, которые у нас есть.
Пример:
Ввод: words = ["gin","zen","gig","msg"]
Вывод: 2
Объяснение:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
Ввод: words = ["a"]
Вывод: 1
Решение задачи
Сложность: Лёгкая
Условие задачи: международная азбука Морзе определяет стандартную кодировку, в которой каждая буква сопоставляется с серией точек и тире следующим образом:
"a" соответствует ".-",
"b" соответствует "-...",
"c" соответствует "-.-." и так далее.
Для удобства ниже приведена полная таблица для 26 букв английского алфавита:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Дан массив строк words, где каждое слово может быть записано как объединение азбуки Морзе каждой буквы.
Верните количество различных преобразований среди всех слов, которые у нас есть.
Пример:
Ввод: words = ["gin","zen","gig","msg"]
Вывод: 2
Объяснение:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
Ввод: words = ["a"]
Вывод: 1
Решение задачи
👍4❤1
Среднее по уровню
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, верните среднее значение узлов на каждом уровне в виде массива. Будут приняты ответы в пределах 10-5 от фактического ответа.
Пример:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: [3.00000,14.50000,11.00000]
Решение задачи
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, верните среднее значение узлов на каждом уровне в виде массива. Будут приняты ответы в пределах 10-5 от фактического ответа.
Пример:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: [3.00000,14.50000,11.00000]
Решение задачи
👍7🎄2
Самый длинный путь с разными соседними символами
Сложность: Тяжёлая
Условие задачи: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 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
Решение задачи
Сложность: Тяжёлая
Условие задачи: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 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
Решение задачи
👍2
Перестановки 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]]
Решение задачи
Сложность: Средняя
Условие задачи: дается список чисел, который может содержать дубликаты, необходимо вычислить всевозможные уникальные перестановки.
Пример:
Ввод: 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]]
Решение задачи
👍2
Неубывающий подмассив
Сложность: Средняя
Условие задачи: дается целочисленный массив nums, верните все различные возможные неубывающие подпоследовательности данного массива, по крайней мере, с двумя элементами. Вы можете вернуть ответ в любом порядке.
Пример:
Ввод: nums = [4,6,7,7]
Вывод: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Ввод: nums = [4,4,3,2,1]
Вывод: [[4,4]]
Решение задачи
Сложность: Средняя
Условие задачи: дается целочисленный массив nums, верните все различные возможные неубывающие подпоследовательности данного массива, по крайней мере, с двумя элементами. Вы можете вернуть ответ в любом порядке.
Пример:
Ввод: nums = [4,6,7,7]
Вывод: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Ввод: nums = [4,4,3,2,1]
Вывод: [[4,4]]
Решение задачи
👍4
Строка из дерева
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, постройте строку, состоящую из круглых скобок и целых чисел из двоичного дерева с помощью способа обхода предварительного порядка, и верните ее.
Опустите все пары пустых скобок, которые не влияют на взаимно однозначное сопоставление между строкой и исходным двоичным деревом.
Пример:
Ввод: root = [1,2,3,4]
Вывод: "1(2(4))(3)"
Ввод: root = [1,2,3,null,4]
Вывод: "1(2()(4))(3)"
Решение задачи
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, постройте строку, состоящую из круглых скобок и целых чисел из двоичного дерева с помощью способа обхода предварительного порядка, и верните ее.
Опустите все пары пустых скобок, которые не влияют на взаимно однозначное сопоставление между строкой и исходным двоичным деревом.
Пример:
Ввод: root = [1,2,3,4]
Вывод: "1(2(4))(3)"
Ввод: root = [1,2,3,null,4]
Вывод: "1(2()(4))(3)"
Решение задачи
👍5👎1