[HackerRank]Java訪問者模式(Java Visitor Pattern)

題目描述

物件導向程式設計有一個很重要的開放/封閉原則,就是要能擴充但禁止修改。換句話說,新的功能會是以擴充的方式加在現有的程式之下,而非直接去修改先前寫的程式。這個題目模擬了一個現實中的問題,必須使用物件導向程式設計的開放/封閉原則來實作出來。

有一個「Tree」類別有以下3個public的方法:

  • getValue():回傳節點所儲存的值。
  • getColor():回傳節點的顏色。
  • getDepth():回傳節點的深度。根節點的深度為0。

在這個題目中,我們將樹的內部實作當作是封閉不可修改的,然而在現實世界的情況下,樹應該要可以允與外部的類別來擴充它的功能。具體來說,他允許「TreeVis」類別的物件來使用「accept」方法走訪樹的結構。

題目共有兩大部份。

首先實作出SumInLeavesVisitor、ProductRedNodesVisitor、和FancyVisitor三個不同的訪問者類別(TreeVis),且每個類別都會有以下3個方法:

  • getResult():回傳一個整數結果。「SumInLeavesVisitor」類別會回傳樹中葉子節點所儲存的值之總和;「ProductRedNodesVisitor」類別會回傳紅色節點所儲存的值之積再除以109+7的餘數,如果沒有找到符合的節點則回傳1;「FancyVisitor」類別則是會回傳深度為偶數的非葉子節點之總和與綠色葉子節點的總和之差的絕對值。
  • visitNode(TreeNode node):訪問樹的非葉子節點。
  • visitLeaf(TreeLeaf leaf):訪問樹的葉子節點。

接著要讀取資料並建立出樹。共有n個,編號i為1到n的節點,xi為節點的數值,ci為節點的顏色。樹的根節點編號為1。

原題網址

https://www.hackerrank.com/challenges/java-vistor-pattern

輸入格式

第一行是一個整數n,就是樹所擁有節點的數量。第二行有n個整數xi,表示各節點的數值,用空格分隔。第三行有n個整數ci,表示各節點的顏色,用空格分隔,0代表紅色,1代表綠色。接下來還有n-1行的輸入,每行有兩個整數ui和vi,描述兩個節點間的邊。

n的範圍在2到105之間(包含2和105),xi的範圍在1到103之間(包含1和103),ci只能是0或是1,ui和vi的範圍在1到n之間(包含1和n)。編號1的節點一定是樹的根節點。

輸出格式

輸出有三行,分別是SumInLeavesVisitor、ProductRedNodesVisitor、和FancyVisitor的「getResult」方法的回傳結果。

範例輸入

5
4 7 2 5 12
0 1 0 0 1
1 2
1 3
3 4
3 5

範例輸出

24
40
15

額外解釋

根據輸入,可以畫出如下的樹圖:

一組中括號為一個節點,其中的3個值分別是[i, xi, ci]。

第一行是「SumInLeavesVisitor」的結果,為所有葉子節點值的總和,也就是:

7 + 5 + 12 = 24

第二行是「ProductRedNodesVisitor」的結果,為紅色節點所儲存的值之積再除以109+7的餘數,也就是:

(4 * 2 * 5) % (1000000007) = 40

第三行是「FancyVisitor」的結果,為深度是偶數的非葉子節點之總和與綠色葉子節點的總和之差的絕對值,也就是:

| 4 - (7 + 12) | = | 4 - 19 | = 15

解題概念

此題最難的地方是建立樹的方式,ui和vi的順序沒有保證前後父子關係,因此會造成資料進來的時候會很混亂。而且節點最多可能會有100000個,如果沒有處理好邊的話,會有明顯效能上的問題。由於在建立樹的節點時就要先決定好這個節點的深度和其子節點,因此這題使用DFS(Depth-first search, 廣度優先搜尋法)來建立樹會比較適當。

首先,在一開始的時候,由於輸入量可能會很大,因此使用Scanner加上BufferedInputStream來讀取標準輸入串流,把節點的各項資料讀至記憶體中儲存。在讀取節點的邊時,可以把輸入進來的每組ui和vi掉換順序再存一份,方便之後計算。舉例來說。如果輸入的資料是「1 5」,有可能1是5的父節點,也有可能5才是1的父節點,要知道他們的父子關係,必須在所有邊都讀取完之後從根節點走訪才能知道,因此我們可以先把這兩種可能都存下來,作為到時走訪時的可用路徑。

接著建立Tree(節點)的陣列,陣列大小為n。再來就可以開始實作遞迴的DFS了。我們可以把剛才讀進來的節點資料和Tree的陣列再加上前一個節點和目前節點的索引值和目前節點的深度作為DFS的輸入。在每次DFS遞迴的時候都要去判斷目前節點是否擁有子節點,如果沒有的話(或只有一個我們透過輸入的邊事先預設的子節點),表示這個節點是樹的葉節點,需使用「TreeLeaf」類別來建立出物件實體,並存進Tree的陣列中;如果目前節點擁有子節點,需使用「TreeNode」類別來建立出物件實體,並存進Tree的陣列中接著要準備繼續遞迴呼叫DFS函數來走訪子節點。在走訪前需先判斷子節點是否就是前一個節點,如果是的話表示這個路徑方向是錯誤的(因為一開始我們把每個輸入的邊都存成兩種方向),要跳過該節點,否則會出現循環(cycle)而無窮遞迴。每走訪一個子節點,就使用「addChild」方法將其加入至目前的「TreeNode」物件。全都走訪之後,Tree的陣列中的所有節點物件就都建立好了,索引0的位置即為根節點。

最後依照題目要求實作「SumInLeavesVisitor」、「ProductOfRedNodesVisitor」和「FancyVisitor」類別,這裡比較需要注意的是,由於「ProductOfRedNodesVisitor」的結果是很多數值的乘績,因此會有溢位的情形,可以使用「BigInteger」類別來協助計算乘績,最後再除以「1000000007」並取餘數來轉成整數。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章