ETH官方钱包

前往
大廳
主題

LeetCode - 2867. Count Valid Paths in a Tree 解題心得

Not In My Back Yard | 2024-11-29 12:00:06 | 巴幣 2 | 人氣 23

題目連結(jié):


題目意譯:
現(xiàn)在有一棵有著 n 個(gè)節(jié)點(diǎn)的無(wú)向樹(shù),其節(jié)點(diǎn)編號(hào)為 1 到 n。你被給定一個(gè)整數(shù) n 以及一個(gè)長(zhǎng)度為 n - 1 的二維整數(shù)陣列 edges,其中 edges[i] = [ui, vi] 代表著在樹(shù)中節(jié)點(diǎn) ui 和 vi 之間有一條邊。

回傳樹(shù)中的「合法路徑」數(shù)。
Return the number of valid paths in the tree.

一條路徑 (a, b) 是「合法」的,代表著從 a 走到 b 的路徑上只有恰好一個(gè)節(jié)點(diǎn)的編號(hào)是質(zhì)數(shù)。

注:
路徑 (a, b) 代表著一個(gè)節(jié)點(diǎn)序列,其從節(jié)點(diǎn) a 開(kāi)始並結(jié)束於節(jié)點(diǎn) b,並使得序列中任兩個(gè)相鄰節(jié)點(diǎn)在樹(shù)中之間有邊存在。
路徑 (a, b) 和路徑 (b, a) 視為同一條路徑,並只會(huì)被算進(jìn)答案一次。

限制:
1 ≦ n ≦ 10 ^ 5
edges.length == n - 1
edges[i].length == 2
1 ≦ ui, vi ≦ n
輸入之生成滿足給定的 edges 代表著一棵合法的樹(shù)。



範(fàn)例測(cè)資:
範(fàn)例 1:
輸入: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]
輸出: 4
解釋: 路徑上只有恰好一個(gè)質(zhì)數(shù)編號(hào)的數(shù)對(duì)為以下:
- (1, 2) 因?yàn)閺?1 到 2 的路徑上包含著質(zhì)數(shù) 2。
- (1, 3) 因?yàn)閺?1 到 3 的路徑上包含著質(zhì)數(shù) 3。
- (1, 4) 因?yàn)閺?1 到 4 的路徑上包含著質(zhì)數(shù) 2。
- (2, 4) 因?yàn)閺?2 到 4 的路徑上包含著質(zhì)數(shù) 2。
可以證明只有 4 條合法路徑。

範(fàn)例 2:
輸入: n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]
輸出: 6
解釋: The pairs with exactly one prime number on the path between them are:
- (1, 2) 因?yàn)閺?1 到 2 的路徑上包含著質(zhì)數(shù) 2。
- (1, 3) 因?yàn)閺?1 到 3 的路徑上包含著質(zhì)數(shù) 3。
- (1, 4) 因?yàn)閺?1 到 4 的路徑上包含著質(zhì)數(shù) 2。
- (1, 6) 因?yàn)閺?1 到 6 的路徑上包含著質(zhì)數(shù) 3。
- (2, 4) 因?yàn)閺?2 到 4 的路徑上包含著質(zhì)數(shù) 2。
- (3, 6) 因?yàn)閺?3 到 6 的路徑上包含著質(zhì)數(shù) 3。
可以證明只有 6 條合法路徑。


解題思維:
基本上思維跟這題一模一樣(所求當(dāng)然不一樣,但足夠像了)。當(dāng)然,記得先建一個(gè)質(zhì)數(shù)表以便查詢某些數(shù)字是不是質(zhì)數(shù)。




此次分享到此為止,如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方,也煩請(qǐng)各位大大撥冗討論。

創(chuàng)作回應(yīng)

更多創(chuàng)作