834 Sum of Distances in Tree

思路：一顆無向的樹有N個節(jié)點(diǎn)，分別標(biāo)記為0,1,2,…N-1，有若干條邊。結(jié)果返回每個節(jié)點(diǎn)到其他節(jié)點(diǎn)的路徑和。

以上面這棵樹為例。從節(jié)點(diǎn)0到其他點(diǎn)的路徑查找過程是：節(jié)點(diǎn)0有兩條邊分別到達(dá)子節(jié)點(diǎn)1和子節(jié)點(diǎn)2；遞歸查找節(jié)點(diǎn)1（節(jié)點(diǎn)1沒有子節(jié)點(diǎn)），節(jié)點(diǎn)2；繼續(xù)查找節(jié)點(diǎn)2的子節(jié)點(diǎn)…依次下去。遞歸每進(jìn)一層，路徑就需要加1。
遍歷完節(jié)點(diǎn)0以后，再以節(jié)點(diǎn)1為根節(jié)點(diǎn)，遍歷。
時間復(fù)雜度O(N*E),E是邊的數(shù)目。這個思路超時。既然是超時，定是因?yàn)橛兄貜?fù)計算的。例如遍歷邊(0,2)，之后又遍歷了一次(2,0)。但是該怎么合并計算，我沒想出來。
學(xué)習(xí)：接下來的描述，相當(dāng)于翻譯官方解釋吧。

用一顆新的樹為例子。節(jié)點(diǎn)0和節(jié)點(diǎn)4是父子關(guān)系，也是相鄰節(jié)點(diǎn)。現(xiàn)在觀察一下相鄰節(jié)點(diǎn)連接后，路徑和發(fā)生什么變化。
將節(jié)點(diǎn)0和節(jié)點(diǎn)4的路徑斷開，得到下圖。

記：stsum[0] 表示節(jié)點(diǎn)0在節(jié)點(diǎn)0子樹上的路徑和。stsum[4]表示節(jié)點(diǎn)4在節(jié)點(diǎn)4子樹上的路徑和。count[0]表示節(jié)點(diǎn)0子樹的節(jié)點(diǎn)數(shù)。answer[0]表示節(jié)點(diǎn)0在整個樹的路徑和。answer[4]表示節(jié)點(diǎn)4在整個樹的路徑和。

當(dāng)節(jié)點(diǎn)0和節(jié)點(diǎn)4之間加上路徑后，answer[0]= stsum[0] + stsum[4] + count[4]。因?yàn)楣?jié)點(diǎn)0到節(jié)點(diǎn)4子樹上所有點(diǎn)的距離與節(jié)點(diǎn)4到節(jié)點(diǎn)4子樹上所有點(diǎn)的距離都要加1。answer[4]= stsum[4] + stsum[0] + count[0]。而且能得到answer[0]-answer[4]=count[4]-count[0]。

所以得到結(jié)論:相鄰節(jié)點(diǎn)（父子節(jié)點(diǎn)）x,y在整個樹的路徑和是：$answer[x]?answer[y]=count[y]?count[x]$。
編碼過程：
1 answer[]存儲以每個節(jié)點(diǎn)為根節(jié)點(diǎn)在整個樹的路徑和；
2 count[] 存儲以每個節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹的節(jié)點(diǎn)數(shù)，初始化每個元素值=1；
3 對某個節(jié)點(diǎn)node,dfs后序遍歷,先處理子節(jié)點(diǎn),計算每個子節(jié)點(diǎn)y的count和stsum，$count[node]+=count[child]$，$stsum[node]+=stsum[child]+count[child]$，當(dāng)遍歷了所有的邊以后$answer[node]=stsum[node]$；如果我們從節(jié)點(diǎn)0開始遍歷。這次遍歷結(jié)束后只有answer[0]是正確的。其他節(jié)點(diǎn)都沒有遍歷完全。
4 再看，上面分析了兩個相鄰節(jié)點(diǎn)（父子節(jié)點(diǎn)）的路徑和關(guān)系。如果有節(jié)點(diǎn)parent和子節(jié)點(diǎn)child，則有$answer[child]=answer[parent]?count[child]+(N?count[child])$，因?yàn)槲覀円呀?jīng)得到answer[0]的正確結(jié)果，可以依據(jù)算式計算節(jié)點(diǎn)0的子節(jié)點(diǎn)的answer。算式中之所以使用count[child]來計算count[parent]：$N?count[child])=count[prent]$，是因?yàn)樵谏弦徊降暮罄m(xù)遍歷過程中，count[parent]的值已經(jīng)發(fā)生變化，不再是parent、child狀態(tài)下的count
(原文的解釋是：count[child]從child得到parent比較容易)。用先序遍歷再次遍歷樹，修改每個子節(jié)點(diǎn)的answer，得到最終結(jié)果。
代碼

301 Remove Invalid Parentheses

思路：最直接的想法：把s中每一個(,)去掉，檢查新的字符串是不是有效字符串，如果是則加入到結(jié)果集。
這樣不符合題意的要求：去掉最少的括號。那么需要計算最少去掉幾個左括號，去掉幾個右括號，就可以是有效字符串。
在編碼過程中注意去重。
代碼
學(xué)習(xí)：可以改進(jìn)，不再需要判斷是否是有效字符串。添加變量open。有效字符的特征是：左括號在前，所以open>0；左右括號個數(shù)相同=>open=0；多余的左右括號都去掉了=>leftCount=0 and rightCount=0。
代碼

總結(jié)

以上是生活随笔為你收集整理的Depth-first Search深度优先搜索专题7的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。