G家数岛题扩展讨论 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家数岛题扩展讨论

G家数岛题扩展讨论# JobHunting - 待字闺中

k*r2015-12-23 08:12

1 楼

原题是2D数有多少个岛，lc中bfs，dfs都可以做。
followup，如果地图很大怎么做，一个方向是切割分别数，但是交界怎样处理呢？
还有另一个方向的followup，是写个函数，int addPoint（int a，int b）返回加一个
点之后岛的个数，这个O(n*n)肯定可以做，怎样更有效率呢？似乎是说可以把每个岛存
成树，加一点之后看看可不可以走到几个树里面。。。那这样的树怎样存呢？
还请大牛们多多提建议。

j*82015-12-23 08:12

2 楼

第一个followup不知道
第二个也是lc的原题阿，可以用union-find做
每次加一个点的时候，check它的周围的8个点，看能不能combine
BTW 牛姐姐也在准备狗狗onsite吗？

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

: 原题是2D数有多少个岛，lc中bfs，dfs都可以做。
: followup，如果地图很大怎么做，一个方向是切割分别数，但是交界怎样处理呢？
: 还有另一个方向的followup，是写个函数，int addPoint（int a，int b）返回加一个
: 点之后岛的个数，这个O(n*n)肯定可以做，怎样更有效率呢？似乎是说可以把每个岛存
: 成树，加一点之后看看可不可以走到几个树里面。。。那这样的树怎样存呢？
: 还请大牛们多多提建议。

k*r2015-12-23 08:12

3 楼

哪道题啊？我怎么一点印象都没有了？
我啊。。。不是说要保持状态嘛。。。不是说生命不息，刷题不止嘛。。。我没确定呢
还。你这拿了大offer也不停歇的节奏啊～

【在 j*****8 的大作中提到】

: 第一个followup不知道
: 第二个也是lc的原题阿，可以用union-find做
: 每次加一个点的时候，check它的周围的8个点，看能不能combine
: BTW 牛姐姐也在准备狗狗onsite吗？

j*82015-12-23 08:12

4 楼

lc 305
你才是拿了大offer还不停歇阿
你不是年前要去面吗。。

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

: 哪道题啊？我怎么一点印象都没有了？
: 我啊。。。不是说要保持状态嘛。。。不是说生命不息，刷题不止嘛。。。我没确定呢
: 还。你这拿了大offer也不停歇的节奏啊～

k*r2015-12-23 08:12

5 楼

原来是那道锁题啊，我已经在几个月前停止交钱了。。。做了也看不到了。。。。
你指的unionfind的做法，是需要先preprocess一下plate吗？能稍微讲下思路不。
没有大offer啦，我跟能给大offer的公司似乎没多大缘分。

【在 j*****8 的大作中提到】

: lc 305
: 你才是拿了大offer还不停歇阿
: 你不是年前要去面吗。。

j*82015-12-23 08:12

6 楼

过200k的还不叫大offer吗。。
我那个题也是好久前刷的，都忘了。刚刚看了下我的代码，和你说的类似，每个island
是一个tree，每个node有一个parent pointer，当你addPoint后，check 它周围的8个
邻居，如果是不同的tree，就合并。判断是不是同样的tree 就是用parent找到tree的
root，看root是不是一样。。
我没查有没有别的最优解，提交accept了就没管了。。

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

: 原来是那道锁题啊，我已经在几个月前停止交钱了。。。做了也看不到了。。。。
: 你指的unionfind的做法，是需要先preprocess一下plate吗？能稍微讲下思路不。
: 没有大offer啦，我跟能给大offer的公司似乎没多大缘分。

k*r2015-12-23 08:12

7 楼

你这拿下L了，不也在攻G嘛，我看你十有八九是可以拿下G的！

island

【在 j*****8 的大作中提到】

: 过200k的还不叫大offer吗。。
: 我那个题也是好久前刷的，都忘了。刚刚看了下我的代码，和你说的类似，每个island
: 是一个tree，每个node有一个parent pointer，当你addPoint后，check 它周围的8个
: 邻居，如果是不同的tree，就合并。判断是不是同样的tree 就是用parent找到tree的
: root，看root是不是一样。。
: 我没查有没有别的最优解，提交accept了就没管了。。

j*82015-12-23 08:12

8 楼

状态全无，十有八九要一轮游了

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

: 你这拿下L了，不也在攻G嘛，我看你十有八九是可以拿下G的！
:
: island

k*r2015-12-23 08:12

9 楼

看了一个用union find做的lc305的解法，似乎是把每个点的root存在一个array里面，
这样的话，加一个新的点，只需要看它周围几点的root有几个不同，每次不同都把当前
这点的root更新，并同时岛数减减。这样每次加一个点的复杂度就是O(1)了吧？因为只
需要查看周围几点的根情况？好留逼的方法啊。

island

【在 j*****8 的大作中提到】

j*82015-12-23 08:12

10 楼

这个和我的一样阿
时间复杂度应该是log(mn) 找root的时间

k*r2015-12-23 08:12

11 楼

是check所有的点加预处理mn吧？如果只是查某个点，是O(1)? 貌似union find的方法
，对于重复多次使用function的情形更加efficient，是吧？

【在 j*****8 的大作中提到】

: 这个和我的一样阿
: 时间复杂度应该是log(mn) 找root的时间

j*82015-12-23 08:12

12 楼

插一个点也是log(mn)，因为你不能保证每个点的当前root是最新的，需要update

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

: 是check所有的点加预处理mn吧？如果只是查某个点，是O(1)? 貌似union find的方法
: ，对于重复多次使用function的情形更加efficient，是吧？

s*x2015-12-23 08:12

13 楼

好像union find average 是O(1).

【在 j*****8 的大作中提到】

: 插一个点也是log(mn)，因为你不能保证每个点的当前root是最新的，需要update

m*82015-12-23 08:12

14 楼

第一个follow up 感觉可以用一个一维数组来记录上一个边界的情况然后跟下一个分块
merge，不知道是否有更省空间的方法。
第二个follow up 㐈 union-find 然后优化是用weighted quick-union with
path compression, 这样时间复杂度就是 preprocess 的O（mn） + O（K * lg(mn)）
m 和 n代表边数，K代表总共数岛的次数。这样find和union都是lg(mn)union之所以是
lg(mn)是因为要先找两个节点的根节点再把根节点连一起。优化后在leetcode上的时间
从486ms 优化到了26ms。
没有优化的解法很简单，优化的有点小技巧但是也不是很难，如果有兴趣的话建议你看
下Princeton 算法课讲union-find的PPT，讲的浅显易懂。

k*r2015-12-23 08:12

15 楼

谢谢你的回答！
1. 如果分块，是不是每个块要计算4个方向的边界情况？这样的话，每个边界会被计算
2次，也就是说有2次重复的岛树减少，总体再加回来一次是不是就ok了，用个以为
array记录减少的次数也行，但每个element是不是可以用4个方向？这样下次计算相同
边界就不用再次计算了；或是所有块都计算左上两个方向？这样没有重复计算。
2。还是有点不清楚union的复杂度，拿lc那道题来讲，一个solution是用一个array来
表示每个点的root的，当add一个新点，只要看新点4个方向的root即可，加入之后如果
有union，好像不更新4个方向的root情况。。。。。。。。。。突然觉得还是应该更
新的。。。。不然下次其他点怎么判断是不是已经被连起来的岛。。。。好吧，我似乎
明白O(lg(mn))了。

）

【在 m********8 的大作中提到】

: 第一个follow up 感觉可以用一个一维数组来记录上一个边界的情况然后跟下一个分块
: merge，不知道是否有更省空间的方法。
: 第二个follow up 㐈 union-find 然后优化是用weighted quick-union with
: path compression, 这样时间复杂度就是 preprocess 的O（mn） + O（K * lg(mn)）
: m 和 n代表边数，K代表总共数岛的次数。这样find和union都是lg(mn)union之所以是
: lg(mn)是因为要先找两个节点的根节点再把根节点连一起。优化后在leetcode上的时间
: 从486ms 优化到了26ms。
: 没有优化的解法很简单，优化的有点小技巧但是也不是很难，如果有兴趣的话建议你看
: 下Princeton 算法课讲union-find的PPT，讲的浅显易懂。

j*82015-12-23 08:12

16 楼

第二个，看看下面的例子
11111 22222
11111A22222
11111 22222
11111B22222
11111 22222
第一次在A点加一个，第二次在B点加一个

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

: 谢谢你的回答！
: 1. 如果分块，是不是每个块要计算4个方向的边界情况？这样的话，每个边界会被计算
: 2次，也就是说有2次重复的岛树减少，总体再加回来一次是不是就ok了，用个以为
: array记录减少的次数也行，但每个element是不是可以用4个方向？这样下次计算相同
: 边界就不用再次计算了；或是所有块都计算左上两个方向？这样没有重复计算。
: 2。还是有点不清楚union的复杂度，拿lc那道题来讲，一个solution是用一个array来
: 表示每个点的root的，当add一个新点，只要看新点4个方向的root即可，加入之后如果
: 有union，好像不更新4个方向的root情况。。。。。。。。。。突然觉得还是应该更
: 新的。。。。不然下次其他点怎么判断是不是已经被连起来的岛。。。。好吧，我似乎
: 明白O(lg(mn))了。

l*82015-12-23 08:12

17 楼

看了你贴的题号我去做了一下，我是这样做的，和用tree用union find有点不大一样：
https://leetcode.com/discuss/75922/python-solution-with-explaination-372-ms-
100%25-for-now
总的复杂度应该是klog(k)，因为每个点最多merge的次数是O(log(k))。k最大是mn，所
以也可以说是klog(mn)。
小弟新人，leetcode还没刷完，各位大哥请指教轻拍。

【在 j*****8 的大作中提到】

: 这个和我的一样阿
: 时间复杂度应该是log(mn) 找root的时间

l*82015-12-23 08:12

18 楼

第一个方向，具体要看实现的方法，不过想过去的话，如果分界的时候不要分得泾渭分
明，而是有一行（纵向的情况就一列）的重叠，在用某些实现方法时可能会有帮助。具
体我没有做，所以也不好说。

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

l*32015-12-23 08:12

19 楼

关于 union-find 操作，推荐楼主看一下这个wiki关于 disjoint set forest 的文章
，核心部分很短，这是个很有效的数据结构
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
此数据结构就是专门处理集合合并的问题的，也可以拿来做最小生成树。关于复杂度，
楼上们的说法基本都是错的。
这个算法的复杂度分析及其高端（我也没看过具体的证明方法），结果就是：复杂度 O
(N alpha(N) )，N是你input的size，其中alpha(x) 是一个叫做 inverse ackermann
function 的东西（https://en.wikipedia.org/wiki/Ackermann_function），简单来
说就是一个增长速度很慢的函数，比log还要慢很多很很多（比 log log log (x) 都
要慢很多很多很多很多。。），practically可以认为对于认知范围内的整数，此函数
值不超过4。。。