Google最新面試題

　　給一個(gè)矩陣，其中0代表海洋，其他數(shù)字代表高度，秉著水往低處流的原則，求出能夠流向任意海洋的點(diǎn)。 比如說(shuō)

　　0 0 0 1 2 3 0

　　0 1 2 2 4 3 2

　　2 1 1 3 3 2 0

　　0 3 3 3 2 3 3

　　那么就要給出 第二行的4 (這有這點(diǎn)出發(fā)，能夠找到連通道四個(gè)0的區(qū)域的一條非遞增路線)，當(dāng)然也有可能找不到這樣的點(diǎn)，或者找到多個(gè)點(diǎn)。

　　小編解答：

　　題目類型TAG：

　　圖論，搜索，并集，擴(kuò)散染色

　　一句話思路：

　　從原題矩陣中建立一個(gè)有向圖，其中結(jié)點(diǎn)是矩陣中等高聯(lián)通區(qū)域，而有向邊連接的這些結(jié)點(diǎn)在矩陣中所代表的聯(lián)通區(qū)域相鄰，其方向是從底高度節(jié)點(diǎn)指向高高度結(jié)點(diǎn);我們從低高度結(jié)點(diǎn)到高高度結(jié)點(diǎn)遍歷整個(gè)有向圖，并在遍歷中不斷地對(duì)匯入當(dāng)前節(jié)點(diǎn)的海洋節(jié)點(diǎn)求并集;最后包括所有海洋節(jié)點(diǎn)的節(jié)點(diǎn)便是所求的節(jié)點(diǎn)。

　　詳細(xì)步驟：

　　1. 建立所有有向圖節(jié)點(diǎn)：通過(guò)遍歷矩陣，我們可以找到所有的相鄰的高度一樣的區(qū)域。我們把每一個(gè)這樣的區(qū)域組成一個(gè)有向圖的節(jié)點(diǎn)，用這個(gè)區(qū)域的高度來(lái)標(biāo)識(shí)這個(gè)節(jié)點(diǎn)的.高度。要注意的是，我們要在原矩陣的每個(gè)元素上記錄其所屬的有向圖節(jié)點(diǎn)，以便于下一步中建立有向邊。這些有向圖的節(jié)點(diǎn)里面還應(yīng)包括一個(gè)bitset，以便第三步中進(jìn)行對(duì)其能到達(dá)海洋求并集。給每一個(gè)高度為0 的有向圖節(jié)點(diǎn)的bitset里面set一個(gè)unique 的bit。

　　2. 建立節(jié)點(diǎn)有向邊: 再次遍歷矩陣，這次注意所遍歷元素的上下左右所有相鄰元素。如果這些相鄰元素和當(dāng)前元素屬于不同有向圖的節(jié)點(diǎn)，則通過(guò)有向邊連接他們，邊的方向是由底高度節(jié)點(diǎn)指向高高度節(jié)點(diǎn)。在設(shè)置有向邊的時(shí)候，要注意去除重復(fù)的邊。

　　3. 遍歷有向圖：將有向圖從底到頂遍歷。遍歷的時(shí)候，將前導(dǎo)節(jié)點(diǎn)的bitset 并入當(dāng)前節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)的bitset中包括所有的海洋bits，那么當(dāng)前節(jié)點(diǎn)就標(biāo)記為成功節(jié)點(diǎn)。

　　4. 得出答案：再一次遍歷原矩陣?yán)锩娴乃�有元素，如果某個(gè)元素所屬的有向圖節(jié)點(diǎn)是成功節(jié)點(diǎn)，那么這個(gè)元素也就是屬于所要找的點(diǎn)。

　　時(shí)間復(fù)雜度分析：

　　由于步驟1，2，3, 4 的復(fù)雜度都是O(n),n表示矩陣中的元素個(gè)數(shù)，那么最后的整體時(shí)間復(fù)雜度也是O(n)

http://www.shddsc.com/