Berkeley biostat应该是biostat里最非传统,最偏ml的超棒项目了!

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1446|回复: 21
收起左侧

[算法题] Number of Islands那道题用Union Find的优点在哪?比起BFS

[复制链接] |试试Instant~
我的人缘0
shuatizhe 发表于 2018-5-12 21:05:26 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (4)
 
 
20% (1)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
感觉bfs就很方便,为什么还要用union find,有什么优点吗?节省时间,空间?没看出来

上一篇:刷题打卡
下一篇:reverse linked list 和 Swap Nodes in Pairs的递归写法
我的人缘0
vegito2002 发表于 2018-5-13 01:32:03 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  86% (263)
 
 
13% (40)  踩
题目本身UF是没有优点. 但是比如假如给你一个Follow-Up: land cell是一个stream不断出现的, 这个时候UF这题就有价值了. 反正多掌握一个方法没有坏处, UF其实还是出场率比较高的一个算法.
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘3
pxu 发表于 2018-5-24 09:34:10 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  67% (308)
 
 
32% (149)  踩
bfs 解决Number of Islands没问题。但处理Number of IslandsII时间复杂度上好像就比较吃力了。另外,我个人觉得用UnionFind不会忘了怎么做的细节。用dfs或BFS,有时候忘了细节,完蛋啦。
回复

使用道具 举报

我的人缘0
oio14644 发表于 2018-5-15 07:55:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  93% (211)
 
 
6% (15)  踩
不是说uf 优点在哪儿,而是有的面试官指定你用uf写,bsf 写的再6, 又如何
回复

使用道具 举报

我的人缘0
hotinherre 发表于 2018-5-14 12:46:18 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  89% (89)
 
 
10% (10)  踩
uf 适合动态生成集合。 bfs dfs 都是对已知数据的遍历

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
buranmilk4 发表于 2018-5-13 02:27:29 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  77% (7)
 
 
22% (2)  踩
一,前面的同学说得对,第二题的话用UF比较好做;二,UF是一种解题思想,适用于这种找集群的题目,不能说BFS不好,但是从这道题目的名字上来讲UF更符合,只是恰巧题目本身用BFS/DFS更加简洁明了
回复

使用道具 举报

我的人缘3
pxu 发表于 2018-5-12 22:53:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (308)
 
 
32% (149)  踩
Number of island I 就是我用bsf 实现的。island II 不知道能不能只用bsf实现
回复

使用道具 举报

我的人缘0
eason0218 发表于 2018-5-13 08:00:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (87)
 
 
20% (22)  踩
试试Number of Island 2,你就知道用union find有什么好处了。。。

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
2006reload 发表于 2018-5-13 13:06:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
union find会省时间如果一直query
回复

使用道具 举报

我的人缘0
 楼主| shuatizhe 发表于 2018-5-14 11:13:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (4)
 
 
20% (1)  踩
用bfs和UF的时间和空间复杂度分别是多少?
回复

使用道具 举报

我的人缘0
阿钟 发表于 2018-5-14 12:47:32 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (8)
 
 
33% (4)  踩
同楼上,BFS/DFS感觉就是不大能retain information

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| shuatizhe 发表于 2018-5-25 23:09:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (4)
 
 
20% (1)  踩
请问uf不会忘了怎么做的细节是指:uf 不用写uf class 的各个细节还是说好写而不会忘记?
回复

使用道具 举报

我的人缘3
pxu 发表于 2018-6-11 10:59:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (308)
 
 
32% (149)  踩
我不知道dfs怎么解决,用island1的思路去做超时了。
uf不会忘了是指我记得UnionFind Class怎么写,这部分基本上是直接写出了。
[Java] 纯文本查看 复制代码
 class UnionFind{
        int parents[];
        
        public UnionFind(int m, int n){
            parents = new int[m*n];
            for(int i = 0; i < m*n;i++){
                parents[i] = i;
            }
        }
        
        public int find(int u){
            if(u != parents[u]){
                parents[u] = find(parents[u]);
            }
            return parents[u];
        }
        
        public boolean union(int u, int v){
            int pu = find(u);
            int pv = find(v);
            
            if(pu == pv){
                return false;
            }
            
            parents[pv] = pu;
            return true;
        }
    }



上面写出之后,我只需要使用就行,对于新的position,先对count增加1, 向左,上,右,下的顺序判断是否属于同一个父类,如果是的,那么count--。代码我觉得比较容易记。
[Java] 纯文本查看 复制代码
public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int count = 0;
        List<Integer> res = new ArrayList<>();
        UnionFind uf = new UnionFind(m,n);
        int grid[][] = new int[m][n];
        
        if(positions == null || positions.length == 0){
            return res;
        }
        
        for(int p[]:positions){         
            grid[p[0]][p[1]] = 1;
           int curr = n*p[0] + p[1]; 

            count++;
            for(int dir[]:dirs){
                int newRow = p[0] + dir[0];
                int newCol = p[1] + dir[1];
                if(newRow >= 0 && newRow < m && newCol >= 0 && newCol<n && grid[newRow][newCol] ==1){
                    if(uf.union(n*newRow+newCol, curr)){
                        count--;
                    }

                }
            }
               
               res.add(count); 
        }
       
        return res;

    }



回复

使用道具 举报

我的人缘3
pxu 发表于 2018-6-11 11:02:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (308)
 
 
32% (149)  踩
UnionFind 时间复杂度要少,因为只需要跟上下左右的节点比较。
回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-6-12 11:22:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  79% (573)
 
 
20% (152)  踩
union find的时间复杂度应该是alpha, 当然这个看的是你对子树都做多少操作
回复

使用道具 举报

我的人缘0
biomedicineman 发表于 2018-6-14 16:49:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  54% (975)
 
 
45% (815)  踩
这道题经典至极
一定要DFS/BFS/UF都要会做
回复

使用道具 举报

我的人缘0
cai_lw 发表于 2018-6-14 20:47:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (120)
 
 
9% (12)  踩
这类问题的标准做法是BFS(不考虑follow up),甚至它们有一个专门的名字叫flood fill

递归式写法的DFS会爆栈,非递归式的写起来比BFS麻烦
UFS理论时间复杂度更高,多一个alpha(n)因子
回复

使用道具 举报

我的人缘0
biomedicineman 发表于 2018-6-15 06:47:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  54% (975)
 
 
45% (815)  踩
cai_lw 发表于 2018-6-14 20:47
这类问题的标准做法是BFS(不考虑follow up),甚至它们有一个专门的名字叫flood fill

递归式写法的DFS ...

可很多时候,尤其单就200 Number of Island这道题来说,DFS的时候我们可以及时把grid[x][y]设置为0;迅速pruning;DFS + pruning最后速度也很快。
回复

使用道具 举报

我的人缘3
pxu 发表于 2018-6-15 07:36:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (308)
 
 
32% (149)  踩
一题多解有助于提高你的解题能力。DFS需改变grid的值,所以,有时候可能只能用UF.
回复

使用道具 举报

我的人缘0
martinliu2218 发表于 2018-6-15 11:47:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  72% (73)
 
 
27% (28)  踩

这道题经典至极
一定要DFS/BFS/UF都要会做
======================================
同意,UF实在太高频了,还有trie,都是要做到随手能写bug free才行。这俩其实就是一开始掌握麻烦点,只要把属于这个tag的都写一遍想一想就可以知道套路啦,以后写起来就比较顺手了~
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-26 14:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表