Нахождение вершины списка
Сложность: Средняя
Условие задачи: вершина списка - элемент, который больше как соседа слева, так и соседа справа.
Дается целочисленный массив (проиндексированный с 0), необходимо вычислить элемент, который является вершиной списка, а после вернуть его индекс. В случае нескольких таких элементов можно вернуть любой из вариантов.
Алгоритм должен иметь временную сложность O (log n).
Пример:
Ввод: nums = [1,2,3,1]
Вывод: 2
Ввод: nums = [1,2,1,3,5,6,4]
Вывод: 5
Решение задачи
Сложность: Средняя
Условие задачи: вершина списка - элемент, который больше как соседа слева, так и соседа справа.
Дается целочисленный массив (проиндексированный с 0), необходимо вычислить элемент, который является вершиной списка, а после вернуть его индекс. В случае нескольких таких элементов можно вернуть любой из вариантов.
Алгоритм должен иметь временную сложность O (log n).
Пример:
Ввод: nums = [1,2,3,1]
Вывод: 2
Ввод: nums = [1,2,1,3,5,6,4]
Вывод: 5
Решение задачи
👍1
Монотонное увеличение
Сложность: Средняя
Условие задачи: бинарная строка монотонно увеличивается, если она состоит из некоторого числа 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного).
Дана двоичная строка s. Вы можете перевернуть [i], изменив его с 0 на 1 или с 1 на 0.
Верните минимальное количество переворотов, чтобы сделать s монотонно увеличивающимся.
Пример:
Ввод: s = "00110"
Вывод: 1
Объяснение: 00111
Ввод: s = "010110"
Вывод: 2
Решение задачи
Сложность: Средняя
Условие задачи: бинарная строка монотонно увеличивается, если она состоит из некоторого числа 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного).
Дана двоичная строка s. Вы можете перевернуть [i], изменив его с 0 на 1 или с 1 на 0.
Верните минимальное количество переворотов, чтобы сделать s монотонно увеличивающимся.
Пример:
Ввод: s = "00110"
Вывод: 1
Объяснение: 00111
Ввод: s = "010110"
Вывод: 2
Решение задачи
👍1
Количество узлов
Сложность: Средняя
Условие задачи: дано дерево (т.е. связный неориентированный граф, не имеющий циклов), состоящее из n узлов с числом от 0 до n - 1 и ровно n - 1 ребер. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая представляет собой символ нижнего регистра, указанный в строковых метках (т.е. узел с номером i имеет метку labels[i]).
Массив ребер задан на ребрах фермы[i] = [ai, bi], что означает наличие ребра между узлами ai и bi в дереве.
Возвращает массив размера n, где и[i] - количество узлов в поддереве узла земли, которые имеют ту же метку, что и узел i.
Поддерево дерева - это дерево, состоящее из узла в T и всех его дочерних узлов.
Пример:
Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Вывод: [2,1,1,1,1,1,1]
Объяснение:
Ввод: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Вывод: [4,2,1,1]
Решение задачи
Сложность: Средняя
Условие задачи: дано дерево (т.е. связный неориентированный граф, не имеющий циклов), состоящее из n узлов с числом от 0 до n - 1 и ровно n - 1 ребер. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая представляет собой символ нижнего регистра, указанный в строковых метках (т.е. узел с номером i имеет метку labels[i]).
Массив ребер задан на ребрах фермы[i] = [ai, bi], что означает наличие ребра между узлами ai и bi в дереве.
Возвращает массив размера n, где и[i] - количество узлов в поддереве узла земли, которые имеют ту же метку, что и узел i.
Поддерево дерева - это дерево, состоящее из узла в T и всех его дочерних узлов.
Пример:
Ввод: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Вывод: [2,1,1,1,1,1,1]
Объяснение:
Ввод: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Вывод: [4,2,1,1]
Решение задачи
❤2👍1👎1
Вам нравится читать контент на этом канале?
Возможно, вы задумывались о том, чтобы купить на нем интеграцию?
Следуйте 3 простым шагам, чтобы сделать это:
1) Нажмите на ссылку: Вход
2) Пополняйтесь удобным способом
3) Размещайте публикацию
Если тематика вашего поста подойдет нашему каналу, мы с удовольствием опубликуем его.
Возможно, вы задумывались о том, чтобы купить на нем интеграцию?
Следуйте 3 простым шагам, чтобы сделать это:
1) Нажмите на ссылку: Вход
2) Пополняйтесь удобным способом
3) Размещайте публикацию
Если тематика вашего поста подойдет нашему каналу, мы с удовольствием опубликуем его.
👎2👍1
Наименьшая лексикографически схожая строка
Сложность: Средняя
Условие задачи: даны две строки одинаковой длины s1 и s2 и строка baseStr.
Говорим, что s1[i] и s2[i] являются эквивалентными символами.
Например, если s1 = "abc" и s2 = "cde", то мы имеем 'a' == 'c', 'b' == 'd' и 'c' == 'e'.
Эквивалентные символы следуют обычным правилам отношения эквивалентности:
Рефлексивность: 'a' == 'a'.
Симметрия: 'a' == 'b' подразумевает 'b' == 'a'.
Транзитивность: 'a' == 'b' и 'b' == 'c' подразумевает 'a' == 'c'.
Например, учитывая информацию об эквивалентности из s1 = "abc" и s2 = "cde", "cd" и "ab" являются эквивалентными строками базового Str = "eed", а "aab" является лексикографически наименьшей эквивалентной строкой базового str.
Верните лексикографически наименьшую эквивалентную строку базового Str, используя информацию об эквивалентности из s1 и s2.
Пример:
Ввод: s1 = "parker", s2 = "morris", baseStr = "parser"
Вывод: "makkek"
Ввод: s1 = "hello", s2 = "world", baseStr = "hold"
Вывод: "hdld"
Решение задачи
Сложность: Средняя
Условие задачи: даны две строки одинаковой длины s1 и s2 и строка baseStr.
Говорим, что s1[i] и s2[i] являются эквивалентными символами.
Например, если s1 = "abc" и s2 = "cde", то мы имеем 'a' == 'c', 'b' == 'd' и 'c' == 'e'.
Эквивалентные символы следуют обычным правилам отношения эквивалентности:
Рефлексивность: 'a' == 'a'.
Симметрия: 'a' == 'b' подразумевает 'b' == 'a'.
Транзитивность: 'a' == 'b' и 'b' == 'c' подразумевает 'a' == 'c'.
Например, учитывая информацию об эквивалентности из s1 = "abc" и s2 = "cde", "cd" и "ab" являются эквивалентными строками базового Str = "eed", а "aab" является лексикографически наименьшей эквивалентной строкой базового str.
Верните лексикографически наименьшую эквивалентную строку базового Str, используя информацию об эквивалентности из s1 и s2.
Пример:
Ввод: s1 = "parker", s2 = "morris", baseStr = "parser"
Вывод: "makkek"
Ввод: s1 = "hello", s2 = "world", baseStr = "hold"
Вывод: "hdld"
Решение задачи
👍2
Количество провинций
Сложность: Средняя
Условие задачи: даётся n провинций, какие-то из них соединены между собой, какие-то нет, также соблюдается правило транзитивности: если провинция «1» соединена с провинцией «2», а «2» соединена с «3» провинцией, то и «1» соединена с «3».
Провинцией является совокупность городов, объединённых между собой, но при этом отделенные от других, принадлежащих другим провинциям.
На вход даётся квадратичная матрица, в которой
Необходимо вычислить количество провинций.
Пример:
Ввод:
Решение задачи
Сложность: Средняя
Условие задачи: даётся n провинций, какие-то из них соединены между собой, какие-то нет, также соблюдается правило транзитивности: если провинция «1» соединена с провинцией «2», а «2» соединена с «3» провинцией, то и «1» соединена с «3».
Провинцией является совокупность городов, объединённых между собой, но при этом отделенные от других, принадлежащих другим провинциям.
На вход даётся квадратичная матрица, в которой
isConnected[i][j] = 1 - соединение между i - ым и j - - ым населенными пунктами (1 - имеется соединение, 0 - отсутствует). Необходимо вычислить количество провинций.
Пример:
Ввод:
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Вывод: 2
Объяснение: *во вложенииРешение задачи
👍2
Проверка соответствия строк в двух списках
Сложность: Лёгкая
Условие задачи: на вход подаются два строковых массива, необходимо вернуть true, если два массива представляют одну и ту же строку, false в противном случае.
Под представлением одной и той же строки подразумевается, что после конкатенации всех фрагментов списков, две полученные строки будут идентичными.
Пример:
Ввод: word1 = ["ab", "c"], word2 = ["a", "bc"]
Вывод: true
Объяснение:
word1: "ab" + "c" -> "abc"
word2: "a" + "bc" -> "abc"
Ввод: word1 = ["a", "cb"], word2 = ["ab", "c"]
Вывод: false
Решение задачи
Сложность: Лёгкая
Условие задачи: на вход подаются два строковых массива, необходимо вернуть true, если два массива представляют одну и ту же строку, false в противном случае.
Под представлением одной и той же строки подразумевается, что после конкатенации всех фрагментов списков, две полученные строки будут идентичными.
Пример:
Ввод: word1 = ["ab", "c"], word2 = ["a", "bc"]
Вывод: true
Объяснение:
word1: "ab" + "c" -> "abc"
word2: "a" + "bc" -> "abc"
Ввод: word1 = ["a", "cb"], word2 = ["ab", "c"]
Вывод: false
Решение задачи
👍1
K-ый наибольший элемент
Сложность: Лёгкая
Условие задачи: необходимо разработать класс по нахождению k-ого наибольшего элемента среди передаваемых значений. k-м считается элемент для отсортированного списка, а не по уникальности значения.
Класс содержит следующие методы:
-
-
Пример:
Ввод:
Вывод:
Объяснение:
Решение задачи
Сложность: Лёгкая
Условие задачи: необходимо разработать класс по нахождению k-ого наибольшего элемента среди передаваемых значений. k-м считается элемент для отсортированного списка, а не по уникальности значения.
Класс содержит следующие методы:
-
KthLargest(int k, int[] nums) иниициализирует класс;-
int add(int val) добавляет элемент в спискок и возвращает k-ый наименьший согласно условию.Пример:
Ввод:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]Вывод:
[null, 4, 5, 5, 8, 8]Объяснение:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8Решение задачи
👍1
Сумма тропы в дереве II
Сложность: Средняя
Условие задачи: дается корень бинарного дерева, а также целовое значение суммы, необходимо вернуть такие пути в дереве (от корня до последнего потомка), сумма значений в узлах которых равна целевой сумме. Каждый путь должен быть возвращен как список из значений узлов.
Пример:
Ввод:
Вывод:
Объяснение: * голубые узлы на изображении
Решение задачи
Сложность: Средняя
Условие задачи: дается корень бинарного дерева, а также целовое значение суммы, необходимо вернуть такие пути в дереве (от корня до последнего потомка), сумма значений в узлах которых равна целевой сумме. Каждый путь должен быть возвращен как список из значений узлов.
Пример:
Ввод:
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Вывод:
[[5,4,11,2],[5,8,4,5]]Объяснение: * голубые узлы на изображении
Решение задачи
👍2❤1
Максимальное скользящее
Сложность: Тяжёлая
Условие задачи: дан целочисленный массив, а также размер k подмассива, начинающегося от левой границы, и заканчивающегося в процессе выполнения алгоритма у правой границы. На каждом шаге можно просматривать k последовательных элементов скользящего массива. На каждом шаге надо определить максимальное значение скользящего.
Пример:
Ввод:
Вывод:
Объяснение:
Скользящее на каждой итерации
Ввод:
Вывод:
Решение задачи
Сложность: Тяжёлая
Условие задачи: дан целочисленный массив, а также размер k подмассива, начинающегося от левой границы, и заканчивающегося в процессе выполнения алгоритма у правой границы. На каждом шаге можно просматривать k последовательных элементов скользящего массива. На каждом шаге надо определить максимальное значение скользящего.
Пример:
Ввод:
nums = [1,3,-1,-3,5,3,6,7], k = 3Вывод:
[3,3,5,5,6,7]Объяснение:
Скользящее на каждой итерации
Max
-------------------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7
1 3 [-1 -3 5] 3 6 7
1 3 -1 [-3 5 3] 6 7
1 3 -1 -3 [5 3 6] 7
1 3 -1 -3 5 [3 6 7] Ввод:
nums = [1], k = 1Вывод:
[1]Решение задачи
👍1
Возрастающая подпоследовательность наибольшей длины
Сложность: Средняя
Условие задачи: даётся массив, необходимо вычислить наибольшую длину строго возрастающей подпоследовательности.
Пример:
Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.
Решение задачи
Сложность: Средняя
Условие задачи: даётся массив, необходимо вычислить наибольшую длину строго возрастающей подпоследовательности.
Пример:
Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: подпоследовательность [2,3,7,101] имеет наибольшую длину.
Решение задачи
❤1👍1
Суммы подмассивов, кратные K
Сложность: Средняя
Условие задачи: дается целочисленный массив nums и целое число k, верните количество непустых подмассивов, сумма которых делится на k.
Подмассив - это непрерывная часть массива.
Пример:
Ввод: nums = [4,5,0,-2,-3,1], k = 5
Вывод: 7
Объяснение: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Ввод: nums = [5], k = 9
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: дается целочисленный массив nums и целое число k, верните количество непустых подмассивов, сумма которых делится на k.
Подмассив - это непрерывная часть массива.
Пример:
Ввод: nums = [4,5,0,-2,-3,1], k = 5
Вывод: 7
Объяснение: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Ввод: nums = [5], k = 9
Вывод: 0
Решение задачи
👍1
Восстановить IP
Сложность: Средняя
Условие задачи: действительный IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.
Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.
Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.
Пример:
Ввод:
Вывод:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: действительный IP-адрес состоит ровно из четырех целых чисел, разделенных одиночными точками. Каждое целое число находится в диапазоне от 0 до 255 (включительно) и не может содержать начальных нулей.
Например, "0.1.2.201" и "192.168.1.1" являются допустимыми IP-адресами, но "0.011.255.245", "192.168.1.312" и "192.168@1.1 " являются недопустимыми IP-адресами.
Учитывая строку s, содержащую только цифры, верните все возможные действительные IP-адреса, которые могут быть сформированы путем вставки точек в s. Вам не разрешается изменять порядок или удалять какие-либо цифры в s. Вы можете вернуть действительные IP-адреса в любом порядке.
Пример:
Ввод:
s = "25525511135"Вывод:
["255.255.11.135","255.255.111.35"]Ввод:
s = "0000"Вывод:
["0.0.0.0"]Решение задачи
👍3
Создание четырехугольного дерева
Сложность: Средняя
Условие задачи: дана матричная сетка n * n, состоящая только из 0 и 1. Мы хотим представить сетку в виде четырехъядерного дерева.
Возвращает корень квадродерева, представляющего сетку.
Обратите внимание, что вы можете присвоить значению узла значение True или False, когда isLeaf имеет значение False, и оба значения принимаются в ответе.
Квадродерево - это древовидная структура данных, в которой каждый внутренний узел имеет ровно четыре дочерних элемента. Кроме того, каждый узел имеет два атрибута.
Выполните рекурсию для каждого из дочерних элементов с соответствующей подсеткой.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Решение задачи
Сложность: Средняя
Условие задачи: дана матричная сетка n * n, состоящая только из 0 и 1. Мы хотим представить сетку в виде четырехъядерного дерева.
Возвращает корень квадродерева, представляющего сетку.
Обратите внимание, что вы можете присвоить значению узла значение True или False, когда isLeaf имеет значение False, и оба значения принимаются в ответе.
Квадродерево - это древовидная структура данных, в которой каждый внутренний узел имеет ровно четыре дочерних элемента. Кроме того, каждый узел имеет два атрибута.
Выполните рекурсию для каждого из дочерних элементов с соответствующей подсеткой.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Решение задачи
👍2
Поиск дубликата поддерева
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, верните все повторяющиеся поддеревья.
Для каждого вида повторяющихся поддеревьев вам нужно только вернуть корневой узел любого из них.
Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Ввод: root = [1,2,3,4,null,2,4,null,null,4]
Вывод: [[2,4],[4]]
Решение задачи
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, верните все повторяющиеся поддеревья.
Для каждого вида повторяющихся поддеревьев вам нужно только вернуть корневой узел любого из них.
Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Ввод: root = [1,2,3,4,null,2,4,null,null,4]
Вывод: [[2,4],[4]]
Решение задачи
❤1👍1
Сортировка массива
Сложность: Средняя
Условие задачи: дается массив целых чисел nums, отсортируйте массив в порядке возрастания и верните его.
Вы должны решить проблему без использования каких-либо встроенных функций в O(nlog(n)) временной сложности и с наименьшей возможной пространственной сложностью.
Пример:
Ввод: nums = [5,2,3,1]
Вывод: [1,2,3,5]
Ввод: nums = [5,1,1,2,0,0]
Вывод: [0,0,1,1,2,5]
Решение задачи
Сложность: Средняя
Условие задачи: дается массив целых чисел nums, отсортируйте массив в порядке возрастания и верните его.
Вы должны решить проблему без использования каких-либо встроенных функций в O(nlog(n)) временной сложности и с наименьшей возможной пространственной сложностью.
Пример:
Ввод: nums = [5,2,3,1]
Вывод: [1,2,3,5]
Ввод: nums = [5,1,1,2,0,0]
Вывод: [0,0,1,1,2,5]
Решение задачи
👍1
Извлечение дубликатов из отсортированного списка II
Сложность: Средняя
Условие задачи: на вход подается указатель на начало связного списка, необходимо удалить все узлы, имеющие дубликаты, то есть в списке должны остаться лишь уникальные значения, которые были в изначальном списке. Необходимо вернуть связный список в отсортированном порядке как и был.
Пример:
Ввод: head = [1,2,3,3,4,4,5]
Вывод: [1,2,5]
Ввод: head = [1,1,1,2,3]
Вывод: [2,3]
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается указатель на начало связного списка, необходимо удалить все узлы, имеющие дубликаты, то есть в списке должны остаться лишь уникальные значения, которые были в изначальном списке. Необходимо вернуть связный список в отсортированном порядке как и был.
Пример:
Ввод: head = [1,2,3,3,4,4,5]
Вывод: [1,2,5]
Ввод: head = [1,1,1,2,3]
Вывод: [2,3]
Решение задачи
👍1
Проверка полноты бинарного дерева
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, определите, является ли это полным двоичным деревом.
В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: true
Ввод: root = [1,2,3,4,5,null,7]
Вывод: false
Решение задачи
Сложность: Средняя
Условие задачи: дается корень двоичного дерева, определите, является ли это полным двоичным деревом.
В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно дальше слева. Он может иметь от 1 до 2h узлов включительно на последнем уровне h.
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: true
Ввод: root = [1,2,3,4,5,null,7]
Вывод: false
Решение задачи
👍1
Поиск в двумерной матрице 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
Решение задачи
Сложность: Средняя
Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:
- в строке элементы отсортированы по возрастанию (слева - направо);
- в столбце элементы отсортированы по возрастанию (снизу - вверх).
Пример:
Ввод: 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
Решение задачи
👍1
Подмассив с наибольшим произведением
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается массив из чисел, необходимо вычислить максимальное произведение, которое встречается в подмассиве исходного массива.
Подмассив - последовательный кусок исходного массива.
Пример:
Ввод: nums = [2,3,-2,4]
Вывод: 6
Объяснение: [2, 3] имеют наибольшее произведение.
Ввод: nums = [-2,0,-1]
Вывод: 0
Решение задачи
👍2