返回具有相同值节点的最长路径

Question

我刚刚在学习一些谷歌面试题，偶然发现了一个问题，但是我似乎无法理解。

考虑一个具有N个节点的无向树，编号从1到N。每个节点都有与之相关联的标签，这是一个整数值。不同的节点可以具有相同的标签。编写一个函数，给定长度为N的零索引数组A，其中A[j]是树中第(j + 1)个节点的标签值，以及长度为K = (N - 1) * 2的零索引数组E，其中描述了树的边缘，返回最长路径的长度，使得该路径上的所有节点具有相同的标签。长度是该路径中的边数。

例如：

A = [1, 1, 1, 2, 2] E = [1, 2, 1, 3, 2, 4, 2, 5]

此树如下所示。节点遵循标签，值的形式。

----------1, 1

-----1, 2        1, 3

2, 4      2, 5

该函数应该返回2，因为最长的路径是2->1->3，这条路径上有2条边。

假设1 <= N <= 1000，并且数组A的每个元素都是范围在[1, 1000000000]之间的整数。

你认为如何分解问题以便解决？谢谢！

- GettingPractice

Answer 1

这是我的建议，我还没有仔细检查过。

from collections import defaultdict

A = [1, 1, 1, 2, 2] 

E = [1, 2, 1, 3, 2, 4, 2, 5]

d = defaultdict(list)
it = iter(E)
for k, v in zip(it, it):
    d[k].append(v)
    d[v].append(k)

leaves = [k for k, v in d.items() if len(v) == 1]

def len_path(node, length=0, coming_from=None):

    max_loc_len = length
    loc_data = A[node-1]

    available_nodes = {i: A[i-1] for i in d[node]}
    available_nodes.pop(coming_from, None)

    for i, i_data in available_nodes.items():
        cumul = length + 1 if loc_data == i_data else 0
        loc_len = len_path(i, cumul, node)
        if loc_len > max_loc_len:
            max_loc_len = loc_len 

    return max_loc_len

max_len = max([len_path(leaf) for leaf in leaves])

更复杂的搜索，避免重复计算相同的路径：

# ...
def len_path(node, length=0, coming_from=None, fork=False):

    max_loc_len = length
    loc_data = A[node-1]

    available_nodes = {i: A[i-1] for i in d[node]}
    available_nodes.pop(coming_from, None)

    matching_nodes = [k for k, v in available_nodes.items()
                         if v == loc_data and k not in leaves[:explored]]
    if len(matching_nodes) > 1:
        fork = True

    if not available_nodes and not fork and node in leaves[explored:]:
        # Reached an unexplored leaf without forks on the path, 
        # hence no need to explore it later
        leaves.remove(node)

    for i, i_data in available_nodes.items():
        cumul = length + 1 if loc_data == i_data else 0
        loc_len = len_path(i, cumul, node, fork)
        if loc_len > max_loc_len:
            max_loc_len = loc_len 

    return max_loc_len

explored = 0
max_len =0

while explored < len(leaves):
    length = len_path(leaves[explored])
    if length > max_len:
        max_len = length
    explored += 1

- Jacques Gaudin

Answer 2

一种方法可以是这样的：

• 从输入构建邻接表
• 选择一个节点并找到具有相同标签的子树的直径

最大直径将是答案

- otaku

Answer 3

更简单的方法：

import operator

A = [1, 1, 1 ,2, 2]

d = {}
final = {}

def func(node, val):
    if len(A) < node: return 0
    if A[node-1] == val: return 1
    else: return 0

for idx, a in enumerate(A):
    id = idx+1
    d[id] = (a,func(id+id, a),func((id*2)+1 , a))

for val in d.values():
    i1,i2,i3 = val
    if i1 not in final:
        final[i1] = 0
    final[i1] += i2 + i3

print(max(final.iteritems(),key = operator.itemgetter(1))[1])

- group work