谷歌时间线（VO 5轮+加面2轮 ）

VO (09/09/2020)

1. 蠡口 珥陵灵
follow up: 返回每个island的面积。当有被陆地包围的湖泊时，湖泊面积也算在island内。
e.g.
[0,0,0,0,1]
[0,1,1,1,0]
[0,1,0,1,0]
[0,1,1,1,0]
[0,0,0,0,0]
两个island，第一个面积为1，第二个为9.

2. given a s

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

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

..  Match上那个组的manager也完全没想到这个结果。recruiter说如果有competing offer的话，可以尽量多给 compensation，前提是要有其他家书面offer的截屏。那个时候已经拿到亚麻lvl 5的顶包，就没和谷歌接着耗下去了。

请问第一题有啥思路吗？我的做法是先遍历一遍，然后把所有的和边界相连的'0‘ 变成 ’*‘， 第二次遍历的时候剩下的'0' 和 '1' 就是岛屿面积。
不知道还有什么更好的方法

加面两轮是1074和1048。

第一题岛屿面积的 one pass 解法：

1.     public int maxArea(int[][] matrix) {
   
2.         int[][] visited = new int[matrix.length][matrix[0].length];
   
3.         int max = 0;
   
4.         for (int i = 0; i < matrix.length; i ++) {
   
5.             for (int j = 0; j < matrix.length; j ++) {
   
6.                 if (visited[i][j] == 0 && matrix[i][j] == 1) {
   
7.                     max = Math.max(max, countIsland(matrix, visited, i, j));
   
8.                 }
   
9.             }
   
10.         }
    
11.         return max;
    
12.     }
    
13. 
    
14.     private int countIsland(int[][] matrix, int[][] visited, int i, int j) {
    
15.         if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j] != 0) return 0;
    
16. 
    
17.         if (matrix[i][j] == 1) {
    
18.             visited[i][j] = 1;
    
19.             int res = 0;
    
20.             for (int[] dir : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
    
21.                 res += countIsland(matrix, visited, i + dir[0], j + dir[1]);
    
22.             }
    
23.             return res;
    
24.         }
    
25.         else {
    
26.             int[] res = new int[1];
    
27.             if (countLake(matrix, visited, i, j, res)) {
    
28.                 return res[0];
    
29.             }
    
30.             else {
    
31.                 return 0;
    
32.             }
    
33.         }
    
34.     }
    
35. 
    
36.     private boolean countLake(int[][] matrix, int[][] visited, int i, int j, int[] res) {
    
37.         if (i == 0 || i == matrix.length - 1 || j == 0 || j == matrix[0].length - 1 || visited[i][j] == -1 && matrix[i][j] == 0) return false;
    
38.         if (visited[i][j] == 1 || matrix[i][j] == 1) return true;
    
39. 
    
40.         res[0] += 1;
    
41.         for (int[] dir : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
    
42.             boolean isLake = countLake(matrix, visited, i + dir[0], j + dir[1], res);
    
43.             if (!isLake) {
    
44.                 visited[i][j] = -1;
    
45.                 return false;
    
46.             }
    
47.         }
    
48.         visited[i][j] = 1;
    
49.         return true;
    
50.     }

复制代码

求大米！

给楼主加了米 恭喜楼主 楼主最后看到狗家offer的数字了么

syuan16 发表于 2020-10-11 05:32
请问第一题有啥思路吗？我的做法是先遍历一遍，然后把所有的和边界相连的'0‘ 变成 ’*‘， 第二次遍历的时 ...

我给的也是这个办法。感觉复杂度应该很难提高了。

请问楼主系统设计怎么答的啊，感觉好难

系统设计好难啊，怎么答啊/

第二题不是数学题么。。。这题有点偏吧

想问一下楼主第一题下面这三种算不算包围呢? 谢谢

[0,1,0]
[1,0,1]
[0,1,0]

[0,1,1]
[1,0,1]
[1,1,0]

[0,1,1]
[1,0,1]
[1,1,1]