[Google最新面试题] Continental divider

Google最新面经,图论搜索相关,很有意思。

题目引用

Continental divider

给一个矩阵,其中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)。

博客推送