Snapchat电面

1. public class Solution {
   
2.     public List<List<Integer>> groupOfFriend(int[][] matrix) {
   
3.         if(matrix == null || matrix.length == 0) return new ArrayList<>();
   
4. 
   
5.         List<List<Integer>> res = new ArrayList<>();
   
6.         int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
   
7. 
   
8.         for(int i = 0; i < matrix.length; i++) {
   
9.             for(int j = i; j < matrix[0].length; j++) {
   
10.                 Set<Integer> tmpRes = new HashSet<>();
    
11.                 if(j >= i && matrix[i][j] == 1) {
    
12.                     tmpRes.add(i);
    
13.                     matrix[i][j] = 0;
    
14.                     dfs(matrix, i, j, tmpRes, dirs);
    
15.                     res.add(new ArrayList<>(tmpRes));
    
16.                 }
    
17.             }
    
18.         }
    
19.         return res;
    
20.     }
    
21. 
    
22.     private void dfs(int[][] matrix, int i, int j, Set<Integer> tmpRes, int[][] dirs) {
    
23.         tmpRes.add(j);
    
24.         matrix[i][j] = 0;
    
25.         for(int[] dir: dirs) {
    
26.             int newRow = i + dir[0], newCol = j + dir[1];
    
27.             if(newRow >= 0 && newCol >= 0 && newCol < matrix[0].length && newRow < matrix.length &&
    
28.                     newCol >= newRow && matrix[newRow][newCol] == 1) {
    
29.                 dfs(matrix, newRow, newCol, tmpRes, dirs);
    
30.             }
    
31.         }
    
32.     }
    
33. }

复制代码

楼主，输出为什么是2？1认识0，1认识2 —> 0,1,2算一个group？那输出不就应该是1了吗？

超分 发表于 2016-9-28 13:27
楼主，输出为什么是2？1认识0，1认识2 —> 0,1,2算一个group？那输出不就应该是1了吗？

一共有三个人啊：0，1，2，3.最后一个人谁也不认识，所以自己独立算一个group～～

补充内容 (2016-9-29 00:40):
一共是四个人哈。最后一个自己一个group

不对，一共四个人～～。然后最后一个人谁也不认识，所以自己成一个group。

xietao0221 发表于 2016-9-28 12:18

这个应该不是上下左右搜吧？ 当遇到一个1以后，应该一整行，一整列得去搜吧？

Lynnklj 发表于 2016-9-29 00:39
不对，一共四个人～～。然后最后一个人谁也不认识，所以自己成一个group。

多谢楼主分享。 请问应该就是八楼分享的代码那样的吧？

小A要当码农 发表于 2016-9-29 00:50
多谢楼主分享。 请问应该就是八楼分享的代码那样的吧？

嗯，其实BFS或者DFS都可以～

Lynnklj 发表于 2016-9-29 01:34
嗯，其实BFS或者DFS都可以～

所以肯定是symmetric matrix吗？

一个group of friends的定义就是 这个group里的任何人必须被至少一个group里的人认识吗？

linweihua0 发表于 2016-9-29 06:55
所以肯定是symmetric matrix吗？

一个group of friends的定义就是 这个group里的任何人必须被至少一个 ...

嗯，是的是的。一定是对称的～～

xietao0221 发表于 2016-9-28 12:18

这道题好像和number of island不太一样把，他不是算所有1连成的区域，每个1代表的是i knows j。比如：
｛1，1，0，1｝
｛1，1，1，0｝
｛0，1，1，0｝
｛1，0，0，1｝
返回的应该是1，按照你的代码，返回的是4了