Среднее по уровню
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, верните среднее значение узлов на каждом уровне в виде массива. Будут приняты ответы в пределах 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]
Решение задачи
👍4
Самый длинный путь с разными соседними символами
Сложность: Тяжёлая
Условие задачи: дано дерево (т.е. связанный неориентированный граф, не имеющий циклов) с корнем в узле 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]]
Решение задачи
👍1
Строка из дерева
Сложность: Лёгкая
Условие задачи: дается корень двоичного дерева, постройте строку, состоящую из круглых скобок и целых чисел из двоичного дерева с помощью способа обхода предварительного порядка, и верните ее.
Опустите все пары пустых скобок, которые не влияют на взаимно однозначное сопоставление между строкой и исходным двоичным деревом.
Пример:
Ввод: 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)"
Решение задачи
❤1👍1
Количество точек на прямой
Сложность: Тяжёлая
Условие задачи: дается массив точек, где точки [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
Решение задачи
Сложность: Тяжёлая
Условие задачи: дается массив точек, где точки [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
Решение задачи
👍1
Сбор урожая яблок
Сложность: Средняя
Условие задачи: дано неориентированное дерево, состоящее из 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
Решение задачи
Сложность: Средняя
Условие задачи: дано неориентированное дерево, состоящее из 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
Решение задачи
👍3
Мост наименьшей длины
Сложность: Средняя
Условие задачи: на вход подается матрица, в которой 1 - суша, 0 - вода.
Остров представляет из себя совокупность частей суши, соединенных в четырех направлениях. На решетке существуют только два острова.
Можно изменить 0 на 1 для соединения двух островов в один.
Необходимо посчитать количество смен нулей на единицу для соединения двух островов.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: 1
Объяснение:
Ввод: grid = [[0,1,0],[0,0,0],[0,0,1]]
Вывод: 2
Решение задачи
Сложность: Средняя
Условие задачи: на вход подается матрица, в которой 1 - суша, 0 - вода.
Остров представляет из себя совокупность частей суши, соединенных в четырех направлениях. На решетке существуют только два острова.
Можно изменить 0 на 1 для соединения двух островов в один.
Необходимо посчитать количество смен нулей на единицу для соединения двух островов.
Пример:
Ввод: grid = [[0,1],[1,0]]
Вывод: 1
Объяснение:
Ввод: grid = [[0,1,0],[0,0,0],[0,0,1]]
Вывод: 2
Решение задачи
👍1
Подсчет подостровов
Сложность: Средняя
Условие задачи: дается два двумерных массива, содержащих нули (означают воду) и единицы (суша). Остров - совокупность единиц, соединенных между собой в четырех направлениях (по горизонтали или вертикали).
Острова на второй решетке рассматриваются как подострова только в случае полного соответствия отображения с первой решетки.
Необходимо вычислить количество подостровов на втором поле.
Пример:
Ввод:
Вывод:
Объяснение:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается два двумерных массива, содержащих нули (означают воду) и единицы (суша). Остров - совокупность единиц, соединенных между собой в четырех направлениях (по горизонтали или вертикали).
Острова на второй решетке рассматриваются как подострова только в случае полного соответствия отображения с первой решетки.
Необходимо вычислить количество подостровов на втором поле.
Пример:
Ввод:
grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]Вывод:
3Объяснение:
Ввод:
grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]Вывод:
2 Решение задачи
👍2
Путь минимальной суммы
Сложность: Средняя
Условие задачи: дается двумерная матрица, заполненная неотрицательными числами. Необходимо найти путь из левого верхнего угла в правый нижний, который имеет наименьшую сумму.
Двигаться можно лишь вправо и вниз.
Пример:
Ввод: grid = [[1,3,1],[1,5,1],[4,2,1]]
Вывод: 7
Объяснение: *во вложении
Решение задачи
Сложность: Средняя
Условие задачи: дается двумерная матрица, заполненная неотрицательными числами. Необходимо найти путь из левого верхнего угла в правый нижний, который имеет наименьшую сумму.
Двигаться можно лишь вправо и вниз.
Пример:
Ввод: grid = [[1,3,1],[1,5,1],[4,2,1]]
Вывод: 7
Объяснение: *во вложении
Решение задачи
👍2
Избыточность соединения
Сложность: Средняя
Условие задачи: дается ненправленный граф, не имеющий циклов.
Узлы графа соединены между собой и отражаются списком соединения
В графе имеется избытоное ребро, которое может быть безболезнено извлечено из списка связности.
Необходимо вывести ребро, которое можно удалить без потери информации.
Пример:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается ненправленный граф, не имеющий циклов.
Узлы графа соединены между собой и отражаются списком соединения
edges[i] = [ai, bi]. В графе имеется избытоное ребро, которое может быть безболезнено извлечено из списка связности.
Необходимо вывести ребро, которое можно удалить без потери информации.
Пример:
Ввод:
edges = [[1,2],[1,3],[2,3]]Вывод:
[2,3]Решение задачи
👍3
Сводные диапазоны
Сложность: Лёгкая
Условие задачи: дается массив из уникальных целых чисел цисел. Срез [a,b] - включает в себя множество значений из данного отрезка включительно.
Необходимо верноть наименьший отсортированный список диапазонов, покрывающих все в массиве. Это означает, что каждый элемент из исходного массива должен быть включен только в единственный диапазон, и нет такого элемнта из исходного массива, что этот элемент будет в одном из диапазонов, но будет остутствовать в исходном массиве.
• "a->b" if a != b
• "a" if a == b
Пример:
Ввод: nums = [0,1,2,4,5,7]
Вывод: ["0->2","4->5","7"]
Объяснение:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Ввод: nums = [0,2,3,4,6,8,9]
Вывод: ["0","2->4","6","8->9"]
Решение задачи
Сложность: Лёгкая
Условие задачи: дается массив из уникальных целых чисел цисел. Срез [a,b] - включает в себя множество значений из данного отрезка включительно.
Необходимо верноть наименьший отсортированный список диапазонов, покрывающих все в массиве. Это означает, что каждый элемент из исходного массива должен быть включен только в единственный диапазон, и нет такого элемнта из исходного массива, что этот элемент будет в одном из диапазонов, но будет остутствовать в исходном массиве.
• "a->b" if a != b
• "a" if a == b
Пример:
Ввод: nums = [0,1,2,4,5,7]
Вывод: ["0->2","4->5","7"]
Объяснение:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Ввод: nums = [0,2,3,4,6,8,9]
Вывод: ["0","2->4","6","8->9"]
Решение задачи
👍2
Змейка из машин
Сложность: Средняя
Условие задачи: есть n машин, направляющихся в одно и то же место на расстоянии target по однополосной дороге.
Дается два целочисленных массива длины n, в первом хранится положение, а во втором скорость соответствующей машины.
Машины не могут обгонять друг друга, и в случае если быстрая машина догнала медленную, то движение она у же продолжает со скоростью медленной машины.
Змейка из машин - группа нескольких или одной машины, достигающих одновременно целевого пункта (расстояние между машинами в одной змейке не учитывается).
Необходимо вычислить количество таких змеек.
Пример:
Ввод: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Вывод: 3
Объяснение:
Ввод: target = 10, position = [3], speed = [3]
Вывод: 1
Решение задачи
Сложность: Средняя
Условие задачи: есть n машин, направляющихся в одно и то же место на расстоянии target по однополосной дороге.
Дается два целочисленных массива длины n, в первом хранится положение, а во втором скорость соответствующей машины.
Машины не могут обгонять друг друга, и в случае если быстрая машина догнала медленную, то движение она у же продолжает со скоростью медленной машины.
Змейка из машин - группа нескольких или одной машины, достигающих одновременно целевого пункта (расстояние между машинами в одной змейке не учитывается).
Необходимо вычислить количество таких змеек.
Пример:
Ввод: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Вывод: 3
Объяснение:
Ввод: target = 10, position = [3], speed = [3]
Вывод: 1
Решение задачи
👍1
Максимальная разница между узлом и предком
Сложность: Средняя
Условие задачи: дается бинарное дерево, необходимо вычислить максимальное значение разницы между двумя узлами, при этом должно соблюдаться строгое условие на узлы: один должен быть потомком, а другой быть его прямым родителем.
Пример:
Ввод:
Вывод:
Объяснение: некоторые из комбинаций пар потомок-родитель:
Ввод:
Вывод:
Решение задачи
Сложность: Средняя
Условие задачи: дается бинарное дерево, необходимо вычислить максимальное значение разницы между двумя узлами, при этом должно соблюдаться строгое условие на узлы: один должен быть потомком, а другой быть его прямым родителем.
Пример:
Ввод:
root = [8,3,10,1,6,null,14,null,null,4,7,13]Вывод:
7Объяснение: некоторые из комбинаций пар потомок-родитель:
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3Ввод:
root = [1,null,2,null,0,3]Вывод:
3Решение задачи
👍1
Конструирование прямоугольника
Сложность: Лёгкая
Условие задачи: web-разработчикам необходимо знать размеры окна создаваемого приложения. Дается специальная прямоугольная рамка, имеющая размеры L (длина) и W (ширина). На данные габариты накладываются определенные условия:
- площадь прямоугольника, разрабатываемого нами окна, должна быть меньше или равна целевому значению;
- ширина должна быть не больше длины;
- разница между длинной и шириной должна быть минимальной.
Необходимо вычислить пару длины и ширины, удовлетворяющих вышеуказанным условиям.
Пример:
Ввод: area = 4
Вывод: [2,2]
Объяснение:
Ввод: area = 122122
Вывод: [427,286]
Решение задачи
Сложность: Лёгкая
Условие задачи: web-разработчикам необходимо знать размеры окна создаваемого приложения. Дается специальная прямоугольная рамка, имеющая размеры L (длина) и W (ширина). На данные габариты накладываются определенные условия:
- площадь прямоугольника, разрабатываемого нами окна, должна быть меньше или равна целевому значению;
- ширина должна быть не больше длины;
- разница между длинной и шириной должна быть минимальной.
Необходимо вычислить пару длины и ширины, удовлетворяющих вышеуказанным условиям.
Пример:
Ввод: area = 4
Вывод: [2,2]
Объяснение:
Ввод: area = 122122
Вывод: [427,286]
Решение задачи
❤1👍1
Конструирование прямоугольника
Сложность: Лёгкая
Условие задачи: web-разработчикам необходимо знать размеры окна создаваемого приложения. Дается специальная прямоугольная рамка, имеющая размеры L (длина) и W (ширина). На данные габариты накладываются определенные условия:
- площадь прямоугольника, разрабатываемого нами окна, должна быть меньше или равна целевому значению;
- ширина должна быть не больше длины;
- разница между длинной и шириной должна быть минимальной.
Необходимо вычислить пару длины и ширины, удовлетворяющих вышеуказанным условиям.
Пример:
Ввод: area = 4
Вывод: [2,2]
Объяснение:
Ввод: area = 122122
Вывод: [427,286]
Решение задачи
Сложность: Лёгкая
Условие задачи: web-разработчикам необходимо знать размеры окна создаваемого приложения. Дается специальная прямоугольная рамка, имеющая размеры L (длина) и W (ширина). На данные габариты накладываются определенные условия:
- площадь прямоугольника, разрабатываемого нами окна, должна быть меньше или равна целевому значению;
- ширина должна быть не больше длины;
- разница между длинной и шириной должна быть минимальной.
Необходимо вычислить пару длины и ширины, удовлетворяющих вышеуказанным условиям.
Пример:
Ввод: area = 4
Вывод: [2,2]
Объяснение:
Ввод: area = 122122
Вывод: [427,286]
Решение задачи
👍1
Нахождение вершины списка
Сложность: Средняя
Условие задачи: вершина списка - элемент, который больше как соседа слева, так и соседа справа.
Дается целочисленный массив (проиндексированный с 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
Решение задачи
👍2❤1👎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]
Решение задачи
❤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
Объяснение: *во вложенииРешение задачи
👍1