数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用Python查找具有相同标签的子树中的节点数的程序
假设我们有一棵具有n个节点的根广义树，其节点编号从0到n-1。每个节点都有一个带有小写英文字母的标签。标签作为输入在labels数组中给出，其中lables[i]包含第i个节点的标签。树由边列表表示，其中每条边e都具有[u,v]，表示u是父节点，v是子节点。我们必须找到一个大小为n的数组A，它表示第i个节点的子树中与i具有相同标签的节点数。
因此，如果输入如下所示：
这里n = 5，label = “ccaca”
则输出将为[3, 2, 1, 1, 1]，因为根节点有三个具有相同标签的后代，节点1有两个后代，而所有其他节点本身都具有该标签。
为了解决这个问题，我们将遵循以下步骤：
E := 从给定的边列表创建图
N := 一个包含每个节点编号及其相应标签的映射
R := 一个大小为n的列表，并填充为0
定义一个函数r()。这将采用ni
C := 一个用于保存键频率的映射
对于E[ni]中的每个e，执行以下操作：
从E[e]中删除ni
在C中更新r(e)
在C中更新N[ni]
R[ni] := C[N[ni]]
返回C
从主方法调用r(0)
返回R
让我们看看下面的实现，以便更好地理解：
示例
from collections import defaultdict, Counter
def solve(n, edges, labels):
E = defaultdict(set)
for f,t in edges:
E[f].add(t)
E[t].add(f)
N = {i:e for i,e in enumerate(labels)}
R = [0]*n
def r(ni):
C = Counter()
for e in E[ni]:
E[e].remove(ni)
C.update(r(e))
C.update((N[ni]))
R[ni] = C[N[ni]]
return C
r(0)
return R
n = 5
edges = [[0,1],[0,2],[1,3],[0,4]]
labels = "ccaca"
print(solve(n, edges, labels))输入
5, [[0,1],[0,2],[1,3],[0,4]], "ccaca"
输出
[3, 2, 1, 1, 1]
更新于：2021年5月29日
373 次浏览
广告