🐶 店面

很簡單和典型的graph題了其實 無論哪一種，幾乎都是dfs+set，或者dfs+backtrack（通常是給終點起點然後找所有可能路線），o不overflow的看你recursion是tail還是non tail recursion，幾乎都不存在大問題

TerryK 发表于 2023-6-11 09:14
很簡單和典型的graph題了其實 無論哪一種，幾乎都是dfs+set，或者dfs+backtrack（通常是給終點起點然後找所 ...

dfs你怎么做到尾递归？？

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

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

TerryK 发表于 2023-6-15 22:55
加個stack，類似

def preOrderTraversal(node):

加个stack只是把递归的调用stack移到自己定义的stack，该overflow还是会overflow，你这样也没解决这个问题。

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

bfs怎么记录path啊？如果path有0但最后没有1的话那这些0会被记录但应该是不需要的吧

呆呆大师兄 发表于 2023-6-27 17:05
bfs怎么记录path啊？如果path有0但最后没有1的话那这些0会被记录但应该是不需要的吧

这个不就是build post office吗？没有要记录path，要把所有经过的0都记录下来，进queue一个就记录一个。

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. }
    

复制代码

标准BFS。有可能不是完全联通的，因此要遍历所有为1的点。此外，BFS的时候还需要保存当前的路径。
如果要求最短，可以先用BFS构建一个heuristic矩阵。具体来说，就是某个点离其最近的1的距离。然后用Dijkstra搜索最短路径