Google最新面試題

　　給一個矩陣，其中0代表海洋，其他數字代表高度，秉著水往低處流的原則，求出能夠流向任意海洋的點。 比如說

　　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 (這有這點出發，能夠找到連通道四個0的區域的一條非遞增路線)，當然也有可能找不到這樣的點，或者找到多個點。

　　小編解答：

　　題目類型TAG：

　　圖論，搜索，并集，擴散染色

　　一句話思路：

　　從原題矩陣中建立一個有向圖，其中結點是矩陣中等高聯通區域，而有向邊連接的這些結點在矩陣中所代表的聯通區域相鄰，其方向是從底高度節點指向高高度結點;我們從低高度結點到高高度結點遍歷整個有向圖，并在遍歷中不斷地對匯入當前節點的海洋節點求并集;最后包括所有海洋節點的節點便是所求的節點。

　　詳細步驟：

　　1. 建立所有有向圖節點：通過遍歷矩陣，我們可以找到所有的相鄰的高度一樣的區域。我們把每一個這樣的區域組成一個有向圖的節點，用這個區域的高度來標識這個節點的.高度。要注意的是，我們要在原矩陣的每個元素上記錄其所屬的有向圖節點，以便于下一步中建立有向邊。這些有向圖的節點里面還應包括一個bitset，以便第三步中進行對其能到達海洋求并集。給每一個高度為0 的有向圖節點的bitset里面set一個unique 的bit。

　　2. 建立節點有向邊: 再次遍歷矩陣，這次注意所遍歷元素的上下左右所有相鄰元素。如果這些相鄰元素和當前元素屬于不同有向圖的節點，則通過有向邊連接他們，邊的方向是由底高度節點指向高高度節點。在設置有向邊的時候，要注意去除重復的邊。

　　3. 遍歷有向圖：將有向圖從底到頂遍歷。遍歷的時候，將前導節點的bitset 并入當前節點，如果當前節點的bitset中包括所有的海洋bits，那么當前節點就標記為成功節點。

　　4. 得出答案：再一次遍歷原矩陣里面的所有元素，如果某個元素所屬的有向圖節點是成功節點，那么這個元素也就是屬于所要找的點。

　　時間復雜度分析：

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

http://m.shddsc.com/