## 无向图中连通分量的数目 ```java class Solution { public int countComponents(int n, int[][] edges) { // construct adjacency list Map> adjacencyList = new HashMap<>(); // 解决孤点 for (int i = 0; i < n; i++) { adjacencyList.put(i, new ArrayList<>()); } for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; adjacencyList.get(u).add(v); adjacencyList.get(v).add(u); } // marked boolean[] visited = new boolean[n]; int count = 0; // start traversal for (int item : adjacencyList.keySet()) { if (!visited[item]) { dfs(adjacencyList, visited, item); count++; } } return count; } private void dfs(Map> adjacencyList, boolean[] visited, int start) { // marked visited[start] = true; // DFS traversal for (int item : adjacencyList.get(start)) { if (!visited[item]) { dfs(adjacencyList, visited, item); } } } } ``` ## 以图判树 ```java class Solution { public boolean validTree(int n, int[][] edges) { // Ideas: tree => edges == nodeNumbers - 1 && 连通分量 == 1 if (n < 1) { return false; } if (edges.length != n - 1) { return false; } // construct adjacency list Map> adjacencyList = new HashMap<>(); for (int i = 0; i < n; i++) { adjacencyList.put(i, new ArrayList<>()); } for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; adjacencyList.get(u).add(v); adjacencyList.get(v).add(u); } // marked boolean[] visited = new boolean[n]; int count = 0; for (int item : adjacencyList.keySet()) { if (!visited[item]) { dfs(adjacencyList, visited, item); count++; } } return count == 1; } private void dfs(Map> adjacencyList, boolean[] visited, int start) { visited[start] = true; for (int item : adjacencyList.get(start)) { if (!visited[item]) { dfs(adjacencyList, visited, item); } } } } ``` ## 迷宫 ```java public class Solution { public boolean hasPath(int[][] maze, int[] start, int[] destination) { // Ideas: 二维矩阵 DFS => 球在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动 // check input if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0 || start == null || start.length == 0 || destination == null || destination.length == 0) { return false; } boolean[][] visited = new boolean[maze.length][maze[0].length]; return dfs(maze, start, destination, visited); } private boolean dfs(int[][] maze, int[] start, int[] destination, boolean[][] visited) { // pruning if (visited[start[0]][start[1]]) { return false; } // exit recursion if (start[0] == destination[0] && start[1] == destination[1]) { return true; } // marked visited[start[0]][start[1]] = true; // move int[] dx = {0, 1, -1, 0}; int[] dy = {1, 0, 0, -1}; for (int i = 0; i < 4; i++) { // 球在遇到墙壁前不会停止滚动 int newX = start[0]; int newY = start[1]; while (checkRange(maze, newX + dx[i], newY + dy[i]) && maze[newX + dx[i]][newY + dy[i]] == 0) { newX += dx[i]; newY += dy[i]; } // 撞到墙了，退一步 boolean result = dfs(maze, new int[]{newX, newY}, destination, visited); if (result) { return true; } } return false; } private boolean checkRange(int[][] maze, int x, int y) { return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length; } } ``` ## 迷宫 II ### BFS ```java class Solution { private final int[] dx = {-1, 0, 1, 0}; private final int[] dy = {0, -1, 0, 1}; public int shortestDistance(int[][] maze, int[] start, int[] destination) { // check input if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0 || start == null || start.length != 2 || destination == null || destination.length != 2) { return -1; } // construct memo search => start 到 memo[i][j] 的最短距离 int[][] memo = new int[maze.length][maze[0].length]; for (int[] item : memo) { Arrays.fill(item, Integer.MAX_VALUE); } // queue Queue queue = new LinkedList<>(); // offer & marked queue.offer(start); memo[start[0]][start[1]] = 0; // traversal while (!queue.isEmpty()) { int[] point = queue.poll(); for (int i = 0; i < 4; i++) { int newX = point[0]; int newY = point[1]; int moveSteps = 0; while (checkRange(maze, newX + dx[i], newY + dy[i]) && maze[newX + dx[i]][newY + dy[i]] == 0) { newX += dx[i]; newY += dy[i]; moveSteps++; } // offer & marked if (memo[newX][newY] > memo[point[0]][point[1]] + moveSteps) { memo[newX][newY] = memo[point[0]][point[1]] + moveSteps; queue.offer(new int[]{newX, newY}); } } } return memo[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : memo[destination[0]][destination[1]]; } private boolean checkRange(int[][] maze, int x, int y) { return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length; } } ``` ### DFS ```java class Solution { private final int[] dx = {-1, 0, 1, 0}; private final int[] dy = {0, -1, 0, 1}; public int shortestDistance(int[][] maze, int[] start, int[] destination) { // Ideas: DFS 二维问题 // check input if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0 || start == null || start.length == 0 || destination == null || destination.length == 0) { return -1; } // search memo int[][] memo = new int[maze.length][maze[0].length]; for (int[] item : memo) { Arrays.fill(item, Integer.MAX_VALUE); } memo[start[0]][start[1]] = 0; dfs(maze, memo, start); return memo[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : memo[destination[0]][destination[1]]; } private void dfs(int[][] maze, int[][] memo, int[] start) { // move for (int i = 0; i < 4; i++) { int newX = start[0]; int newY = start[1]; int moveStep = 0; while (checkRange(maze, newX + dx[i], newY + dy[i]) && maze[newX + dx[i]][newY + dy[i]] == 0) { newX += dx[i]; newY += dy[i]; moveStep++; } if (memo[newX][newY] > memo[start[0]][start[1]] + moveStep) { memo[newX][newY] = memo[start[0]][start[1]] + moveStep; dfs(maze, memo, new int[]{newX, newY}); } } } private boolean checkRange(int[][] maze, int x, int y) { return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length; } } ```

算法班 第六周 Leetcode 付费题目题解

算法班第六周 Leetcode 付费题目题解