面经里的描述五花八门，大概是一条高速公路宽度为m，路上有sensor，每个sensor有坐标（x,y)和半径r, 问有没有一条直线（也有的面经说曲线）能绕开所有sensor到达终点。
提示里说用union find， 具体怎么做我想了好久也没想到，想问问思路？
这个首先是预处理数据，如果假设是matrix表示平面，可以是boolean二维数组，被sensor扫到的地方置为TRUE。那么就是起点到终点是否可以有path。dfs可解
没看出union find的优势，虽然也是可以做，相当于找connected component。其实思路很简单，把所有sensor 分组union起来就行，写代码会费点时间
如果follow up问这个路很宽 sensor的半径很大呢
那就别预处理，直接从起点开始dfs，然后每步遍历所有的sensor，看是否被扫描到，扫到就不行
FLAG备战2群 微信群上的聊天记录如下，请查收。
————— 2019-01-22 —————
X 18:02
征人一起讨论谷歌sensor题目 Google Sensor面经题
梢笛 18:03
这不雷达小车题么
梢笛 18:04
最早好像是snap出的
X 18:05
嗯，解法呢
梢笛 18:05
其实思路很简单，把所有sensor 分组union起来就行，写代码会费点时间
梢笛 18:05
我当年就是面的这个题啊
X 18:05
比dfs有优势？
梢笛 18:05
第三轮，一个中国大哥面的
X 18:06
我没觉得union find比dfs好
梢笛 18:06
dfs解法我还真不知道
梢笛 18:08
关键它这个题可以是浮点数的
X 18:08
啥意思
X 18:09
半径吗
梢笛 18:09
对
梢笛 18:09
我当年被要求的就是浮点数
X 18:09
union find也有问题吧
梢笛 18:09
半径可以是浮点数，路宽也可以是浮点数
梢笛 18:10
union find可以做，对于每一个sensor都要去跟别的sensor计算一下是否overlap
梢笛 18:11
通过它们坐标算出圆心间距离是否小于等于它们两半径之和
X 18:12
overlap有什么意思？反正是不能通过的
梢笛 18:12
就是把overlap在一起的sensor都union起来，然后计算它们会不会cover整一条道路
X 18:13
题目不是求是否可以到终点么
梢笛 18:13
只要找到这个group里最上边界和最下边界就可以了
X 18:14
就算不cover 整条路，我把中间给断了可以不？
梢笛 18:14
对呀，如果所有的sensor都不会把路完全堵住，它势必能找到路到达终点
X 18:14
X 18:15
找到这个group里最上边界和最下边界就可以了 – 不明白
梢笛 18:16
你这种情况，这两个圆就会被union起来啊，因为它们有overlap，然后上边界到下边界cover了整条路，所以return false。题目应该是“问有没有一条 曲线 能绕开所有sensor到达终点。
谷歌sensor题目 微信群上的聊天记录如下，请查收。
————— 2019-01-22 —————
谢雄炜 19:39
union find 把所有连在一起的sensor连在一起 然后将每个连在一起的片 的sensor按y排序 路是平行x轴的 看第一个sensor 是否cover路的下边缘 最后一个sensor是否cover路的上边缘算法 中心点加减半径
神月蜘九 19:40
有道理
神月蜘九 19:40
连在一起就行，看下半径是不是r R
神月蜘九 19:41
但是你怎么确定哪些sensor开始连
神月蜘九 19:41
互相连也要n^2的复杂度
谢雄炜 19:41
union find o n
谢雄炜 19:45
把他们sort一下 在按半径距离来判断 太远的就肯定不用试了
神月蜘九 19:47
怎么sort
谢雄炜 19:47
worse case n方
神月蜘九 19:48
写一个看看
神月蜘九 19:48
matrix = [8] * [8]
x, y, r
sersors=[(1,1,3),(2,5,2),(5,1,4)]
谢雄炜 19:51
面试直接n方 我觉得没什么问题
路的坐标是啥