Сообщения

Показаны сообщения с ярлыком "BFS"

Наикратчайшее расстояние до всех домов

Изображение
Источник: https://leetcode.com/problems/shortest-distance-from-all-buildings/ Дана матрица размером m x n называется grid заполнена значениями 0 ,   1 или 2 , где: каждый 0 означает пустое пространство, на которое можно вступить; каждая 1 означает здание, на эту ячейку нельзя вступить; каждая 2 означает препятствие, на эту ячейку нельзя вступить. Мы хотим построить дом на пустом пространстве так, чтобы расстояние от него до остальных домов было наикратчайшим. Разрешения направления движения по матрице: вверх, вниз, вправо, влево. В ответе указать наикратчайшее рсстояние для такого дома. Если невозможно построить дом, чтобы остальные дома были для него доступны, вернуть -1. Дистанция считается, как Manhattan Distance , где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y| . Пример 1: Дано: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] Результат: 7 Пояснение: Три здания находятся в чейках (0,0), (0,4), (2,2), и препятсвие в ячейке (0,2). Ячейка (1,2) пустая и она идеальна...

Бинарное дерево: вид справа

Изображение
Источник: https://leetcode.com/problems/binary-tree-right-side-view/ Дан корень root бинарного дерева. Представьте, что вы смотрите на дерева справа. Вернуть его узлы, которые вам видны, сверху вниз. Пример 1: Дано: root = [1,2,3,null,5,null,4] Результат: [1,3,4] Пример 2: Дано: root = [1,null,3] Результат: [1,3] Пример 3: Дано: root = [] Результат: []   Ограничения: Количество узлов в дереве: [0, 100] . -100 <= Node.val <= 100 Идея решения Мы будем обходить дерево в порядке BFS, то есть по "этажам". Элемента "этажа" будем записывать так, чтобы самый правыйэлемент шел первым. Его будем записывать и в результат, а остальные элементы этажа нам нужны, чтобы подсчитать следующий "этаж". Имплементация class Solution {     public List<Integer> rightSideView(TreeNode root) {         List<Integer> result = new ArrayList(); //   результат запишем сюда         Queue<Tre...

Вода впадает в оба океана

Изображение
Источник: https://leetcode.com/problems/pacific-atlantic-water-flow/ Остров представлен матрицей m x n граничит с Тихим и Атлантическим океанами: сверху и слева от острова Тихий океан, снизу и справа - Атдантический. Остров поделен на ячейки, соответствующие ячейкам матрицы. Значение каждой ячейки - это высота над уровнем моря. На остров проливается дождь. Дождь стекает по поверхности острова и вода впадает в океаны в 4 направлениях: вверх, вниз, вправо, влево. Вода может перетекать из первой ячейки во вторую, если значение первой ячейки больше или равно значения второй ячейки. Вернуть список ячеек, заданных своими координатами, из которых вода стекает в оба океана. На изображении выше виден пример, что остров задан матрицей: [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]. Желтым цветом отмечены ячейки, из которых вода стекает в оба океана: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Идея решения Мы отдельно подсчитываем ячейки, из которых вода может стечь в один океан,...

Проверить полноту двоичного дерева

Изображение
Дан корень бинарного дерева. Определить, являтеся ли дерево полным. В полном бинарном дереве каждый уровень, за исклением возможно последнего (с листьями), полностью заполен. Если последний уровень не заполнен, то все его элементы занимают все левые позиции. Пример 1: Дано: root = [1,2,3,4,5,6] Результат: true Пояснение: Каждый уровень дерева, за исключением нижнего, заполнен. Самый нижний уровень имеет пробелы только справа. Пример 2: Дано: root = [1,2,3,4,5,null,7] Результат: false Пояснение: Узел с числом 7 следует за "дыркой", которая находится левее его. Ограничения: Количество вершин в дереве находится в интервале [1, 100] . 1 <= Node.val <= 1000 Идея решения Будем обходить дерево по BFS, и на каждом уровне будем добавлять в очередь левое и правое поддерево рассматриваемой вершины, даже если они нулевые.  Если дерево полное, то после рассмотрения всех вершин в очереди останутся только нулевые элементы. В противном случае, дерево не полное, а с "дырками...

Взвешенная сумма вложенного списка

Источник: https://leetcode.com/problems/nested-list-weight-sum-ii/ Дан вложенный список целых чисел. Подсчитать сумму всех его элементов, взвешенных их глубиной. Каждый элемент вложенного списка может быть целым числом или вложенным списком - тоже состоящий из целых чисел и вложенных списков. Вес увеличивается снизу вверх, то есть "листьевые" целые элементы имеют вес 1. А корень имеет наибольший вес. Как изменится алгоритм, если вес увеличивается от корня к листьям? Пример 1: Дано: [[1,1],2,[1,1]] Результат: 8 Пояснение: Четыре единицы находятся на глубине 1, а 2 - на глубине 2 . Поэтому сумма считается: 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8. Пример 2: Дано: [1,[4,[6]]] Результат: 17 Поясненеи: Число 1 находится на глубине 3, 4 - на глубине 2, 6 - на глубине 1. Поэтому сумма считается: 1*3 + 4*2 + 6*1 = 17. Есть некоторый класс NestedInteger, со следующим интерфейсом: /**  * // Интерфейс для вложенного списка, не нужно его имплементировать  *  * public interface NestedIn...

Следующий правый указатель в каждой вершине дерева

Изображение
 Дано бинарное дерево: struct Node { int val; Node *left; Node *right; Node *next; } Заполнить поле next так, чтобы вершина дерева указывала на соседнюю вершину справа, если та существует. Если же никакой вершины справа не существует, то указательnext принимает значение NULL. Изначально все next указатели имеют значение NULL. Ограничение: можно использовать константный объём (не зависящий от размера лерева) дополнительной памяти. Пример: Дано: root = [1,2,3,4,5,null,7] Результат: [1,#,2,3,#,4,5,7,#] Объяснение: Исходное бинарное дерево на рисунке A. Результат на рисунке B: каждая вершина указывает на соседа справа, если он существует. А если не существует, то указывает на NULL. Сериализованный результат выведен в порядке уровней дерева, где уровни разделены символом #. Внутри уровня его элементы указаны слева направо. Идея решения Нам нужно обойти все "этажи" дерева и выстроить в цепочку элементы дерева, находящиеся на одном "этаже". Самый правый элемент ...

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

Дана матрица целых чисел. Найти самый длинный путь, в котором чисоа возастают. Из каждой ячейки матрицы можно двигаться в 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...