FB实习面经

king_lm 发表于 2017-11-6 12:24
那如果是这种情况呢？第一行的0变成了1。。。岛屿数量应该会减1吧

嗯。。我这种情况当时没有考虑到。。面试官也没指出来。那是这样，看看能否标记当前点是“几个”附近小岛的neighbor(0-4)。

1. 
   
2. 00100
   
3. 00100
   
4. 11011
   
5. 00100
   
6. 00100
   

复制代码

类似上面[2,2]的地方，标记为4个neighbor，那么变之前小岛数为4，之后为1，就是n-i+1=4-4+1
在你那个例子里，n-i+1 = 2-2+1=1。之后变岛的node旁边四个node的neighbor数也需要更新(减个1？)。
这样应该ok吧？

rippersean 发表于 2017-11-6 13:25
嗯。。我这种情况当时没有考虑到。。面试官也没指出来。那是这样，看看能否标记当前点是“几个 ...

是呀，所以感觉好麻烦。。。之前在另外一个帖子中又见到过，有人提出了一个割点的概念= =，不太懂= =

king_lm 发表于 2017-11-6 13:34
是呀，所以感觉好麻烦。。。之前在另外一个帖子中又见到过，有人提出了一个割点的概念= =，不太懂= =

我搜了一下，感觉这个和小岛二是类似的。可以看看这个。

rippersean 发表于 2017-11-6 13:42
我搜了一下，感觉这个和小岛二是类似的。可以看看这个。

ok，多谢啦！

刚开始以为lz这么多题目都是一轮做的，惊呆了，哈哈

zmy1101 发表于 2017-11-9 03:14
刚开始以为lz这么多题目都是一轮做的，惊呆了，哈哈

lol。。。运气还可以，都属于高频或者tag里的。

求问一下楼主如果是有一个点从1变成0要怎么做呢？感觉比有一个点从0变成1要难多了。

请问时间复杂度，O(n)， n是什么呢？小岛的个数吗？谢谢楼主

xiayank 发表于 2017-11-28 07:39
请问时间复杂度，O(n)， n是什么呢？小岛的个数吗？谢谢楼主

是小岛个数。。紫薯

rippersean 发表于 2017-11-28 12:53
是小岛个数。。紫薯

我查了一下时间是不是应该是O(m*n)啊？就是整个图的大小。空间复杂度是O(k)，k为最大的island包含的1的个数，就是最大深度？