脸家电面 2h前

楼主你去onsite了吗 我也刚过了电面，onsite有点紧张呢

屌屌的心经 发表于 2018-8-29 00:43
楼主你去onsite了吗 我也刚过了电面，onsite有点紧张呢

没呢 一起努力准备吧

Shp2500 发表于 2018-8-28 23:52
问下LZ，电面过了之后多久通知你去onsite的啊？

隔了1-2天 没记错的话隔了一天第二题下午收到邮件的

好奇一下，这个题目楼主为什么要用bfs做呢？
如果仅仅是需要1所代表的岛屿的数目，然后去掉，上下左右都为1的岛屿数目，
貌似暴力扫一遍就可以吧。
还有什么其他的条件吗？

第二题可以用并查集找岛屿，然后构建hash map，key为parent，value为坐标集，最后数坐标集合的边长

楼主说的题意很清晰，就是BFS的时候注意看看每个cell有没有被4个1包围即可，C++代码测了一下没问题：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. 
   
5. using namespace std;
   
6. 
   
7. static const vector<int> di {0, 0, 1, -1};
   
8. static const vector<int> dj {1, -1, 0, 0};
   
9. 
   
10. bool inBound(const int i, const int j, const size_t m, const size_t n) {
    
11.     return (0 <= i) && (i < m) && (0 <= j) && (j < n);   
    
12. }
    
13. 
    
14. void bfs(vector<vector<int>> &grid, int i, int j, const size_t m, const size_t n,
    
15.          vector<int> &result) {
    
16.     queue<pair<int, int>> q;
    
17.     q.push({i, j});
    
18.     // mark this cell visited
    
19.     grid[i][j] = -1;
    
20.    
    
21.     int perimeter = 0;
    
22.     while (!q.empty()) {
    
23.         pair<int, int> curr = q.front();
    
24.         q.pop();
    
25.         int count = 0;
    
26.         for (int k = 0; k < 4; ++k) {
    
27.             int ni = curr.first + di[k];
    
28.             int nj = curr.second + dj[k];
    
29.             if (inBound(ni, nj, m, n)) {
    
30.                 if (grid[ni][nj] == 0) continue;
    
31.                 if (grid[ni][nj] == 1) {
    
32.                     q.push({ni, nj});
    
33.                     grid[ni][nj] = -1;
    
34.                 }
    
35.                 count++;
    
36.             }
    
37.         }
    
38.         if (count != 4) perimeter++;
    
39.     }
    
40.     result.push_back(perimeter);
    
41. }
    
42. 
    
43. vector<int> computePerimeter(vector<vector<int>> &grid) {
    
44.     if (grid.empty() || grid[0].empty()) {
    
45.         return {};
    
46.     }
    
47.    
    
48.     const size_t m = grid.size(), n = grid[0].size();
    
49.     vector<int> result;
    
50.     for (int i = 0; i < m; ++i) {
    
51.         for (int j = 0; j < n; ++j) {
    
52.             if (grid[i][j] == 1) {
    
53.                 bfs(grid, i, j, m, n, result);
    
54.             }
    
55.         }
    
56.     }
    
57.     return result;
    
58. }
    
59. 
    
60. int main() {
    
61.     vector<vector<int>> grid {{1, 0, 0, 1, 1, 1},
    
62.                               {1, 0, 0, 1, 1, 1},
    
63.                               {0, 0, 0, 0, 1, 1}};
    
64.    
    
65.     vector<int> result = computePerimeter(grid);
    
66.     return 0;
    
67. }

复制代码

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

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

smileyvenice 发表于 2018-8-31 13:10
我觉得返回的结果可能是每个岛的周长分开的，比如楼主的例子返回值就是[2, 7]。这样的话，就需要用bfs把 ...

哦哦，这样的话，感觉DFS还是BFS差不多的样子？
就是为了遍历的过程中把相邻岛屿干掉。