专栏首页包子铺里聊IT[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)

本文分享自微信公众号 - 包子铺里聊IT(baozitraining)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-02-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈Java面试过程中的Encapsulation, Inheritance and Polymorphism

    在Java面试过程中,我们通常会被问到作为一门OOP的语言,最主要的特点有哪些? 或许很多同学在实际的应用中都能够慢慢的总结出OOP这种语言在实际工作中所带...

    包子面试培训
  • [Hot Technology系列]从此之后再无Load Balancer--SmartStack

    什么是SmartStack? SmartStack is an automated service discovery and registration fr...

    包子面试培训
  • Baozi Training Leetcode solution 199:Binary Tree Right Side View

    Leetcode solution 199:Binary Tree Right Side View

    包子面试培训
  • 工程师应该学点算法——图论2

    这种遍历算法可以想象成在玩迷宫,我们选择一个方向走到底,直至不能走了然后再返回一步继续尝试其他的方向,在代码中就是递归+回溯,这就是 深度优先遍历。

    机智的程序员小熊
  • 图文详解 DFS 和 BFS

    深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search)是图论中两种非常重要的算法,生产上...

    kunge
  • 初识广度优先搜索与解题套路

    先来看看其中比较简单的数据结构 - 链表,它和数组类似,也是一个线性的结构,简单来说就是一条路径,你从头开始遍历,最终会将链表上面的节点都访问到,到达终点。

    五分钟学算法
  • 5分钟轻松理解二叉树的深度遍历策略

    我们知道普通的线性数据结构如链表,数组等,遍历方式单一,都是从头到尾遍历就行,但树这种数据结构却不一样,我们从一个节点出发,下一个节点却有可能遇到多个分支路径,...

    我是攻城师
  • 有向图之数据类型和可达性分析

    本篇主要讲有向图的两个方面,1、有向图的数据类型,2有向图的可达性分析。要是了解的同学欢迎讨论 。当然拉觉得无趣的也可以跳过。

    大数据和云计算技术
  • 死磕 java集合之TreeMap源码分析(四)- 内含彩蛋

    这里的前中后都是以“我”的顺序为准的,我在前就是前序遍历,我在中就是中序遍历,我在后就是后序遍历。

    彤哥
  • Zookeeper实现分布式锁详细步骤,你一定要知道

    前几天分享了分布式锁的三种实现方案(我们是这样一步一步实现分布式锁的),其中对于zookeeper实现方式,有些朋友说想知道实现的总体流程。那么今天我就来将zo...

    架构师修炼

扫码关注云+社区

领取腾讯云代金券