菜牛在么问下HBAN - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

菜牛在么问下HBAN

菜牛在么问下HBAN# Stock

R*52011-03-04 08:03

1 楼

大家好，
最近onsite了一家公司，被问到一道经典得number of islands题，就是给一个二维
01矩阵，求数出有多少个island。时间复杂度O(mn), 空间复杂度O(1). 也就是说不能
用BFS和DFS。而且island得shape是任意的。当时实在拿这题没办法。后来回来去网上
搜了下，也没找到好的方法，所以到论坛来求助，希望知道的朋友指点下迷津，谢
谢了。

b*r2011-03-04 08:03

2 楼

还拿着么？记得你是长期仓位的。
考虑搞支小银行玩玩了，打算拿6个月。这支目前还稳定吧？
前段时间看了一支HCBK，没想到突然就祸起萧墙，不敢上了。

h*n2011-03-04 08:03

3 楼

空间复杂度一般不算递归本身的overhead。
在这个前提下，DFS就是O(mn) + O(1).

【在 R******5 的大作中提到】

: 大家好，
: 最近onsite了一家公司，被问到一道经典得number of islands题，就是给一个二维
: 01矩阵，求数出有多少个island。时间复杂度O(mn), 空间复杂度O(1). 也就是说不能
: 用BFS和DFS。而且island得shape是任意的。当时实在拿这题没办法。后来回来去网上
: 搜了下，也没找到好的方法，所以到论坛来求助，希望知道的朋友指点下迷津，谢
: 谢了。

g*l2011-03-04 08:03

4 楼

等这波盘子跌下去再上吧，现在上位置偏高，要赶上盘子不好，估计要损失一些。

【在 b******r 的大作中提到】

: 还拿着么？记得你是长期仓位的。
: 考虑搞支小银行玩玩了，打算拿6个月。这支目前还稳定吧？
: 前段时间看了一支HCBK，没想到突然就祸起萧墙，不敢上了。

z*n2011-03-04 08:03

5 楼

面试官专门说了不许BFS和DFS吗？这么奇葩的要求？还是题目有变化你没注意到。

g*42011-03-04 08:03

6 楼

hoho。

t*b2011-03-04 08:03

7 楼

这个明显就是dfs吧
楼主面的时候被告知dfs 不行？

b*r2011-03-04 08:03

8 楼

我又要忍不住长线变短线，短线变DT了。

R*52011-03-04 08:03

9 楼

真的是面试官说了不能用BFS和DFS，不能用extra space。他给我的提示是，如果
matrix只有一层，则可以用个counter解决，如果matrix多层，而shape是rectangle也
是可以用一个counter解决，现在问题是拓展到shape为任意连着的shape，算法该怎
么改可以解决这个问题。然后我有给出反例，但他说可以考虑减counter。但我还是不
知道这样做是否能解决所有case。在网上搜了一些帖子，基本都是用BFS和DFS的，或者
变形。实在没办法才上来求助。
不知道是否有大神知道这个算法存在，还是说我被这个韩国小哥给黑了。。。

Z*g2011-03-04 08:03

10 楼

肌肉哥，阿姨好猪啊
能进吗

【在 g***l 的大作中提到】

: 等这波盘子跌下去再上吧，现在上位置偏高，要赶上盘子不好，估计要损失一些。

z*o2011-03-04 08:03

11 楼

好像真可以,
在原来矩阵上直接改,设id标志,
下一行计数时查和上一行是否连接,根据id还可以合并.

【在 R******5 的大作中提到】

: 真的是面试官说了不能用BFS和DFS，不能用extra space。他给我的提示是，如果
: matrix只有一层，则可以用个counter解决，如果matrix多层，而shape是rectangle也
: 是可以用一个counter解决，现在问题是拓展到shape为任意连着的shape，算法该怎
: 么改可以解决这个问题。然后我有给出反例，但他说可以考虑减counter。但我还是不
: 知道这样做是否能解决所有case。在网上搜了一些帖子，基本都是用BFS和DFS的，或者
: 变形。实在没办法才上来求助。
: 不知道是否有大神知道这个算法存在，还是说我被这个韩国小哥给黑了。。。

r*m2011-03-04 08:03

12 楼

我倒是觉得你应该感到开心，现在进HCBK便宜了很多。重要的是，幺蛾子已经出来了，
比再去另挑一个还更保险些。

【在 b******r 的大作中提到】

u*n2011-03-04 08:03

13 楼

我记得我好像做过，忘鸟

g*l2011-03-04 08:03

14 楼

不进也不卖，死猪不怕开水烫，现在不是操作的好时机

【在 Z****g 的大作中提到】

: 肌肉哥，阿姨好猪啊
: 能进吗

D*02011-03-04 08:03

15 楼

Union Find.
这都是原题。

s*g2011-03-04 08:03

16 楼

union find不需要额外space存root？

【在 D**********0 的大作中提到】

: Union Find.
: 这都是原题。

z*n2011-03-04 08:03

17 楼

这不是原题。。起码我是第一次听说number of island要求这么解的。。
个人感觉面试官提示的想法也无法做到O(1)space，至少需要记录一下哪几个id合并了。
版上的街霸帮搞Poj的人呢？赶快现身帮lz解惑，需要你们的时候到了。

【在 D**********0 的大作中提到】

: Union Find.
: 这都是原题。

D*02011-03-04 08:03

18 楼

那就不知道了，等大神来解。

了。

【在 z*********n 的大作中提到】

:
: 这不是原题。。起码我是第一次听说number of island要求这么解的。。
: 个人感觉面试官提示的想法也无法做到O(1)space，至少需要记录一下哪几个id合并了。
: 版上的街霸帮搞Poj的人呢？赶快现身帮lz解惑，需要你们的时候到了。

R*52011-03-04 08:03

19 楼

嗯，我也这么觉得，起码像以下这种case：
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
你不mapping区分下各个island的话，到最后一行没法判断该不该减。我也是实在不知
道怎么解这题，我面试时都说了BFS和union find 的方法，但面试官说不是他想要的
，他觉得按照他提示得方法用counter就可以O(mn) 时间复杂度和O(1)空间复杂度解出
这题。

了。

【在 z*********n 的大作中提到】

z*o2011-03-04 08:03

20 楼

我有个idea:
就是给每个为1的element设一个值: i*cols+j+2
凡是有连接的:从上至下,从下到上,从左到右,从右到左,四个方向, populate该岛中最
小值.
再遍历matrix,
if matrix[i][j]==i*cols+j+2: cnt+=1
写起来太麻烦

z*o2011-03-04 08:03

21 楼

我觉得可行.