Описание тега lowest-common-ancestor
3
ответа
Самая быстрая нерекурсивная реализация LCA?
Вот алгоритм, который я придумал для нерекурсивного нахождения наименьшего общего предка двух узлов в двоичном дереве. Вот основная стратегия: Используйте словарь / хеш-таблицу для хранения дерева. Каждая пара ключ-значение представляет узел и его р…
01 янв '17 в 20:23
2
ответа
Самый низкий общий предок в Python NetworkX
Использование NetworkX Я хочу получить наименьшего общего предка от node1 и node11 в DiGraph. Ниже приведен код. import networkx as nx G = nx.DiGraph() #Directed graph G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]) G.add_edges_from([(2,1),(…
08 окт '16 в 16:30
1
ответ
Расстояние между двумя узлами в весовом дереве
Мой вопрос очень прост. Дается взвешенное дерево. Мы должны найти расстояние между двумя заданными узлами. так как количество запросов очень велико (около 75000) каждый раз, когда время ожидания bfs истекает, поэтому я попробовал другой способ сдела…
06 ноя '15 в 20:03
0
ответов
Получение 3-х неудачных тестов при запуске LowestCommonAncestor для BST
Не уверен, что мне не хватает некоторых утверждений if. Мой профессор сказал мне использовать вспомогательный метод для рекурсии. Ошибки:1. Когда v1 или v2 является родителем другого.2. Когда Root - это LCA.3. Когда у родителей обоих есть ДМС. КОД: …
09 дек '17 в 23:38
1
ответ
Найти самого низкого общего предка во вложенном множестве
Я ищу способ найти самого низкого общего предка во вложенном множестве, используя одно уравнение. Например, из изображения по адресу: https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg LCA между костюмами и женщинами - это одеж…
07 мар '17 в 17:19
1
ответ
Название алгоритма восстановления дерева по наименьшему общему предку?
Я хотел бы написать инструмент, который работает с некоторыми древовидными данными. (На самом деле он будет работать с древовидным подмножеством GAG-версии DAG, но для этого вопроса это не важно). В частности, я хочу алгоритм, который восстанавливае…
10 ноя '17 в 12:39
2
ответа
Самый низкий общий предок - код объяснения
LCA путем прохождения по порядку и порядку заказа был легко реализован и понят мной. Но есть рекурсивный подход снизу вверх. Я взглянул на код в Интернете и не понял ни одной строки: Вот код: public Node lowestCommonAncestor(int val1, int val2,Node …
06 окт '15 в 09:26
1
ответ
Python: самый низкий общий предок в двоичном дереве, вызов на CodeEval
Прежде всего, я знаю, что есть много других тем, посвященных этой проблеме. То, что я хочу знать, - это то, почему мое решение, кажется, не оценивается на 100%, когда я отправляю его на CodeEval. Это только занимает 70%. Когда я тестирую его в своей…
08 июн '14 в 18:17
1
ответ
Найти наименьшего общего предка двух узлов дерева, без ссылки на корень?
class TreeNode { TreeNode parent; TreeNode left; TreeNode right; // other data fields omitted - not relevant } Вам дано два узла p, а также qКак вы находите самого низкого общего предка? (Предположим, они оба принадлежат очень большому дереву) У вас…
23 окт '17 в 02:09
0
ответов
Слияние многострочных строк в php
Я пытаюсь объединить многострочные строки. Я написал код для объединения данных, который не имеет символа "/n", но не может продолжить его. Чего мне нужно добиться, так это сравнить узел-предок с удаленным узлом и локальным узлом и построчно объедин…
15 июн '16 в 04:45
1
ответ
Найти самого низкого общего предка в общем дереве, имеющем родительские идентификаторы
Моя проблема заключается в том, чтобы найти LCA для общего дерева, которое будет создано из списка в текстовом файле. Я ищу наиболее эффективную реализацию. Данные представлены в виде: Id, info, ParentId Данные никак не сортируются. Я думал о создан…
02 дек '14 в 15:11
0
ответов
Как вычислить наименьшего общего предка во времени NlogN, используя динамическое программирование на python
Это домашнее задание. Входные данные: словарь списков, где каждый ключ является узлом, а значение - списком родителей узла. Пустой список означает, что узел является корнем. {'1': ['3'], '2': ['3'], '4': ['5'], '3': ['5'], '6': ['7'], '8': ['7'], '7…
16 апр '18 в 01:37
2
ответа
Найти несколько LCA в корне дерева
Я пытаюсь реализовать LCA для корня дерева. Я дал дерево (связный неориентированный граф без циклов) и последовательность запросов о LCA для некоторого корня и двух вершин. Каждый конкретный запрос может иметь различный корень, поэтому я не могу исп…
18 авг '14 в 20:54
2
ответа
Как найти самого низкого предка с нисходящим листовым узлом с некоторой меткой?
Эта проблема Дано корневое дерево с n узлами, где все листья помечены из набора меток. Создайте структуру данных, которая, учитывая листовой узел, a и метку l, может найти самого младшего предка u, a, где u имеет хотя бы одного потомка с меткой l. …
26 июл '18 в 11:19
0
ответов
Неясное понимание алгоритма самого низкого общего предка (LCA)
Я пытался выучить алгоритм LCA O(nlog n) и предварительную обработку O(log n). Я читаю его с русского сайта с помощью google translate. Но он плохо переводится, и мне трудно понять его Кто-нибудь может мне помочь с этим? Это псевдокод, который я взя…
14 окт '15 в 15:40
1
ответ
Как определить, лежит ли узел w на пути между узлом u и узлом v в дереве?
Я пытаюсь решить проблему, которая требует от меня определить, лежит ли узел w на пути между узлом u и узлом v в дереве (не обязательно двоичном). Например, для следующего дерева: 1 2 3 4 5 6 7 Узел 2 лежит на пути от узла 4 до 7. Очевидным решением…
20 июн '17 в 04:25
1
ответ
ДМС бинарного дерева - нужен совет
Я знаю, что этот вопрос задавался много раз. Мне нужно уточнить LCA двоичного дерева (не BST). Если я пытаюсь найти LCA двух узлов (3,11) из данного дерева: _______1______ / \ ___2__ ___4__ / \ / \ 6 5 9 11 / \ 7 3 Код возвращает 11 для (3,11). // B…
12 окт '15 в 20:42
1
ответ
LCA с использованием разреженной матрицы за время O(logn)
[1]: https://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/ for (int i=0; i<level; i++) if ((diff>>i)&1) v = parent[v][i]; В приведенном выше коде он переходит только к 2-му родительскому эл…
14 сен '18 в 09:51
1
ответ
Самые низкие общие предки (LCAS) нескольких узлов в ориентированном графе?
Я заинтересован в вычислении наименьших общих предков нескольких узлов в ориентированном графе. Я протестировал метод findlcas, предложенный классом NaiveLcaFinder проекта jGrapht ( https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/mai…
17 апр '18 в 13:39
2
ответа
Как решить SPOJ DISQUERY?
Проблема основана на концепции самого низкого общего предка.Требуется найти длину самого короткого и самого длинного ребра на пути между парой узлов в дереве.Вот ссылка на проблему: SPOJ DISQUERY
18 мар '16 в 11:39