facebook 电面

intern第一轮面试。小哥应该不是三哥。
给一个0 1 矩阵，连在一起的1算做岛。求问岛的个数

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
ahoma,">写的慢，就这一个题。小哥也没说满意不满意。
不知道能不能过啊。

jzy637 发表于 2015-3-16 07:42
学校牛b就能过。
背景一般就跪。

真相了。。。。。。

1. def check(row, col, board, visit):
   
2.         m = len(board)
   
3.         n = len(board[0])
   
4.         if row >= 0 and row < m and col >= 0 and col < n and visit[row][col] == False and board[row][col] == 1:
   
5.                 return True
   
6.         return False
   
7. def dfs(row, col, board, visit, curcount):
   
8.         nbrow = [1, 0, -1, 0]
   
9.         nbcol = [0, 1, 0, -1]
   
10.         visit[row][col] = True
    
11.         curcount += 1
    
12.         for k in xrange(4):
    
13.                 if check(row + nbrow[k], col + nbcol[k], board, visit):
    
14.                         #curcount += 1
    
15.                         dfs(row + nbrow[k], col + nbcol[k], board, visit, curcount)
    
16.         print curcount
    
17. 
    
18. 
    
19. 
    
20. def getRes(board):
    
21.         count = 0
    
22.         visit = [[False for i in range(len(board[0]))] for j in range(len(board))]
    
23.         curcount = 0
    
24.         res = []
    
25. 
    
26.         for row in xrange(len(board)):
    
27.                  for  col in xrange(len(board[0])):
    
28.                          if board[row][col] == 1 and visit[row][col] == False:
    
29.                                  dfs(row, col, board, visit, curcount)
    
30.                                  count += 1
    
31.                                  res.append(curcount)
    
32.         print visit
    
33.         return count, res
    
34. 
    
35. board = [[1, 1, 0, 0, 1], [1, 0, 0, 1, 1]]
    
36. 
    
37. print getRes(board)
    
38. 
    

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

一个电面，，，我一直主张电面不要炫技。。就plain的暴力就ok。贴个子集拙劣的code吧 这是DFS的。

1. public class SolutionDFS {
   
2.    
   
3.     private int row;
   
4.     private int col;   
   
5. 
   
6.     public int solve(int[][] a) {
   
7.         this.row = a.length;
   
8.         this.col = a[0].length;
   
9.         int ans = 0;
   
10.         for (int i = 0; i < row; i++) {
    
11.             for (int j = 0; j < col; j++) {
    
12.                 if (a[i][j] == 1) {
    
13.                     dfs(a, i, j);
    
14.                     ans++;
    
15.                 }
    
16.             }
    
17.         }
    
18.         
    
19.         return ans;
    
20.     }
    
21. 
    
22.     private void dfs(int[][] a, int i, int j){
    
23.         if (i < 0 || i >= row || j < 0 || j >= col || a[i][j] != 1) {
    
24.             return;
    
25.         }
    
26.         a[i][j] = 2;
    
27.         dfs(a, i + 1, j);
    
28.         dfs(a, i, j + 1);
    
29.         dfs(a, i - 1, j);
    
30.         dfs(a, i, j - 1);
    
31.     }
    
32. }

复制代码

学校牛b就能过。
背景一般就跪。

jzy637 发表于 2015-3-16 07:42
学校牛b就能过。
背景一般就跪。

我了去。。。还可以这样啊

这题咋做, bfs吗?

wy193777 发表于 2015-3-16 10:19
这题咋做, bfs吗?

感觉BFS ， DFS都可以，类似于找多少个connected component吧，只是我们关心 1的CC

有个东西叫做并查集……

……这个是典型的连通图问题。

无向图一般两种做法，dfs，或者是并查集。

这题可以扩展，

一种是扩展到二分图问题。

另外一种可以扩展成多维并查集，这个比较好举例子，比如说两点之间有多条路径，问连通图。

shawlin 发表于 2015-3-17 00:12
感觉BFS ， DFS都可以，类似于找多少个connected component吧，只是我们关心 1的CC

BFS一般不是处理这种问题用的。类似的科研中估计也不会用BFS，因为收敛速度的问题。当然这题一定要用也没有问题的。

另外如果是strong connected components，就不是类似的做法了。

robinho364 发表于 2015-3-17 00:36
……这个是典型的连通图问题。

无向图一般两种做法，dfs，或者是并查集。

请问这题面试官expect的答案是DFS还是union find呢？各自有什么优劣呢?

yuxrose 发表于 2015-3-17 01:59
请问这题面试官expect的答案是DFS还是union find呢？各自有什么优劣呢?

我用dfs做的，面试官好沉默，感觉闷闷不乐的样子。也没说他expect啥。我说dfs，他说好。。