打车二电

/** * From a given 2D matrix of 0's and 1's, find an index that when toggled will result in creation of a single largest island.Island is a group of adjascent 1's. e.g     [[0,1,1,0],         [0,0,0,0],  

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rgb(118, 70, 255)">楼主不会做。。。所以挂了。。。嘤

/** * From a given 2D matrix of 0's and 1's, find an index that when toggled will result in creation of a single largest island. Island is a group of adjascent 1's.

e.g     
[[0,1,1,0],         
[0,0,0,0],         
[1,0,0,0],         
[1,0,0,1],         
[0,0,0,0],         
[0,0,1,1]]

In the given example they are 4 islands.    (2) (0,1),(0,2)    (2) (2,0),(3,0)    (1) (3,3)    (2) (5,2),(5,3)

Find all the islands, number of elements in each Island and there indices.**/   

我format一下

longfeix 发表于 2018-4-20 01:35
我format一下

感谢@@@@@

看着有点像利口number of island，做法应该类似

请问楼主，toggle 是把 0 变为 1，然后看是否连接了岛屿而形成更大的岛？union-find 可以做，遍历所有的 0，然后 find 0 四周的 1 是否属于不同的岛屿，如果不同，则相加求 max。

lakeshore 发表于 2018-4-20 00:21
请问楼主，toggle 是把 0 变为 1，然后看是否连接了岛屿而形成更大的岛？union-find 可以做，遍历所有的 0 ...

言之有理。我也隐约觉得是union find。谢谢兄弟/姐妹！

lakeshore 发表于 2018-4-20 00:21
请问楼主，toggle 是把 0 变为 1，然后看是否连接了岛屿而形成更大的岛？union-find 可以做，遍历所有的 0 ...

如果0比较多，还可以从已知的1开始找它周围可以与其他连的0

这个题要考虑对角线吗？ 只需要找到可以形成最大岛屿的index？

dw841128 发表于 2018-4-23 12:21
这个题要考虑对角线吗？ 只需要找到可以形成最大岛屿的index？

并不知道。。。应该可以和面试官交流吧

uber真是，电面就这么难了。。。。