🐶 店面

矩阵里面有很多 1 -1 0 然后把所有的1(可

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

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

点的坐标in a list

Solumilken 发表于 2023-6-9 21:34
想問問樓主,
1. 連接起來的方式是上下左右四個方向的1都可連接嗎？ 還是說可以 上+下+左+右 + 左上+左下+ ...

1 4个方向
2 对
3 把能连接的所有1都连起来 可能有多个1 所以连的路线可能有多条 路线也可以有重叠

minimal spanning tree?

1. public class ConnectOne {
   
2. 
   
3.     int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
4. 
   
5.     public List<List<Integer>> solution(int[][] matrix) {
   
6.         Set<Integer> resSet = new HashSet<>();
   
7.         List<List<Integer>> res = new LinkedList<>();
   
8.         boolean[][] visitedOne = new boolean[matrix.length][matrix[0].length];
   
9.         for (int i = 0; i < matrix.length; i++) {
   
10.             for (int j = 0; j < matrix[0].length; j++) {
    
11.                 if (matrix[i][j] == 1 && !visitedOne[i][j]) {
    
12.                     helper(resSet, matrix, i, j, new boolean[matrix.length][matrix[0].length], visitedOne, 0);
    
13.                 }
    
14.             }
    
15.         }
    
16. 
    
17.         for (int idx : resSet) {
    
18.             res.add(Arrays.asList(idx / matrix[0].length, idx % matrix[0].length));
    
19.         }
    
20. 
    
21.         return res;
    
22.     }
    
23. 
    
24.     private void helper(Set<Integer> resSet, int[][] matrix, int row, int col, boolean[][] curVisited, boolean[][] visitedOne, int len) {
    
25.         if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || matrix[row][col] == -1 || curVisited[row][col]) {
    
26.             return;
    
27.         }
    
28. 
    
29.         resSet.add(row * matrix[0].length + col);
    
30.         if (matrix[row][col] == 1) {
    
31.             visitedOne[row][col] = true;
    
32.             if (len != 0) {
    
33.                 return;
    
34.             }
    
35.         }
    
36. 
    
37.         curVisited[row][col] = true;
    
38.         for (int[] dir : DIRS) {
    
39.             int newRow = row + dir[0];
    
40.             int newCol = col + dir[1];
    
41.             helper(resSet, matrix, newRow, newCol, curVisited, visitedOne, len + 1);
    
42.         }
    
43.         curVisited[row][col] = false;
    
44.     }
    
45. 
    
46.     public static void main(String[] args) {
    
47.         ConnectOne solution = new ConnectOne();
    
48.         int[][] matrix = {{1, 0, -1, -1, 1}, {0, 0, 1, -1, 0}, {0, 1, -1, -1, 0}, {-1, -1, -1, -1, 1}};
    
49.         List<List<Integer>> resSet = solution.solution(matrix);
    
50.         int[][] printMatrix = new int[matrix.length][matrix[0].length];
    
51.         for (List<Integer> list : resSet) {
    
52.             printMatrix[list.get(0)][list.get(1)] = 1;
    
53.         }
    
54.         for (int i = 0; i < printMatrix.length; i++) {
    
55.             for (int j = 0; j < printMatrix[0].length; j++) {
    
56.                 System.out.print(printMatrix[i][j] + ",");
    
57.             }
    
58.             System.out.println();
    
59.         }
    
60.     }
    
61. }
    

复制代码

可以revisit坐标吗

应该就是个dfs

从所有1开始bfs就可以。没有follow up吗？

x24yang 发表于 2023-06-05 10:35:50
从所有1开始bfs就可以。没有follow up吗？

请问bfs怎么判断1全部连接了

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

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

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

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

UnionFind能不能做呀