資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告