Facebook 2016 summer intern一面跪经

题目是leetcode原题第200题, 01组成二维数组,0代表水,1代表陆地, 求岛屿数目. 目测已跪, 写的代码漏洞百出改半天没改完, 很想自己抽自己.

看地里面经看的比较多, 感觉重题挺多的, 于是乎最近一周天天刷面经, 结果三个月之前看过的题目忘得差不多了, 比如这一个 BFS (看TAG, DFS也可以解决,不过貌似BFS更直观一些) 的题目, 虽然我一上来就看出来了这题是BFS的解法, 也感觉以前见过别

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

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

/>;
4. 不要太急着去写, 想清楚再动手比较重要, 这个题我就思路没搞清晰, 上去就码, 发现错误再改, 浪费时间了.



补充内容 (2016-2-19 14:13):
刚刚收到拒信, 面试之后18个小时左右, 唉, 虽然有心理准备, 还是蛋蛋的忧桑啊

1. int numIslands(vector<vector<char>>& grid) {
   
2.         int count = 0;
   
3.         for (int i = 0; i < grid.size(); ++i) {
   
4.             for (int j = 0; j < grid[0].size();++j) {
   
5.                 if (grid[i][j] == '1') {
   
6.                     ++count;
   
7.                     DFS(grid,i,j);
   
8.                 }
   
9.             }
   
10.         }
    
11.         return count;
    
12.     }
    
13.    
    
14.     void DFS(vector<vector<char>>& grid, int i, int j) {
    
15.         if (grid[i][j] == '0') return;
    
16.         if (grid[i][j] == '1') grid[i][j] = '0';
    
17.         if (i > 0 && grid[i-1][j] == '1') DFS(grid,i-1,j);
    
18.         if (i < grid.size() - 1 && grid[i+1][j] == '1') DFS(grid,i+1,j);
    
19.         if (j > 0 && grid[i][j-1] == '1') DFS(grid,i,j-1);
    
20.         if (j < grid[0].size()-1 && grid[i][j+1] == '1') DFS(grid,i,j+1);
    
21.     }

复制代码

走过的路径标0就不会重复走了

zhenjieruan 发表于 2016-2-19 14:22
走过的路径标0就不会重复走了

你贴的这个代码我看到过, 和我当时面试时写的也差不多, 我的理解这就是BFS, 只不过写这个代码的人function名字取错了, 取成了DFS. 看这篇文章你就明白我想法的依据了/
http://www.cnblogs.com/skywang12345/p/3711483.html

zhenjieruan 发表于 2016-2-19 13:10
其实个人觉得这道题DFS更直观。。

我觉得因为要向四个方向, 同时找相连的1, 所以BFS效率更高吧, 不知道理解的对不对, 是不是同时往图的多个方向扩展就是BFS? DFS 是一条路走到头再换下一条吧!

其实个人觉得这道题DFS更直观。。

zhenjieruan 发表于 2016-2-19 11:22
走过的路径标0就不会重复走了

你的情况跟我一样啊！改了又改，哈哈，加油

gaocan1992 发表于 2016-2-19 14:32
你的情况跟我一样啊！改了又改，哈哈，加油

谢谢! 一起加油! 我已经被拒了, 祝你好运!

dukangs 发表于 2016-2-19 11:47
谢谢! 一起加油! 我已经被拒了, 祝你好运!

你几号面的？？？

gaocan1992 发表于 2016-2-19 14:48
你几号面的？？？

昨天下午

dukangs 发表于 2016-2-19 11:49
昨天下午

我也是，你是Nenad Bozidarevic吗