图
200. 岛屿数量
-
思路
- 遍历二维数组，遇到等于1的进行计算。同时修改同岛的位置为0，避免重复计算
- 遍历同岛的位置，可以采用dfs深度优先搜索
-
代码
char[][] g; public int numIslands(char[][] grid) { int sum = 0; g = grid; for(int i = 0; i < grid.length; i ++){ for(int j = 0; j < grid[0].length; j++){ if(grid[i][j] == '1'){ sink(i,j); sum ++; } } } return sum; } // dfs 检查同岛的位置 public void sink(int i, int j){ if(i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == '0') return; g[i][j] = '0'; // 注意点一 sink(i + 1, j); sink(i, j + 1); sink(i - 1, j); sink(i, j - 1); } -
注意点
- 注意点一：已经计数过的岛屿，要将为0/2，避免重复计算
-
扩展
-
相似的dfs可以用来计算岛的面积
-
public int maxAreaOfIsland(int[][] grid) { int res = 0; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == 1) { int a = area(grid, r, c); res = Math.max(res, a); } } } return res; } // 计算面积 int area(int[][] grid, int r, int c) { if (!inArea(grid, r, c)) { return 0; } if (grid[r][c] != 1) { return 0; } grid[r][c] = 2; return 1 + area(grid, r - 1, c) + area(grid, r + 1, c) + area(grid, r, c - 1) + area(grid, r, c + 1); } // 判断是否在网格内 boolean inArea(int[][] grid, int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length; } -
参考题解
-
207. 课程表
- 思路
- 遍历每一个课程，使用dfs检查每一个课程是否有成环
- dfs检查课程，需要借助一个flags数组存储每个课程被学习的情况，区分出课程是否被学习、是否在当前课程的学习路线上
- 0。未学习
- -1。在其他课程学习路线上学习了。
- 1。当前课程学习路线上
- 代码
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 将关联的课程放在一起
Map<Integer,List<Integer>> relatedMap = new HashMap<>();
for(int i = 0; i < prerequisites.length; i ++){
List<Integer> related = relatedMap.getOrDefault(prerequisites[i][1],new ArrayList<>());
related.add(prerequisites[i][0]);
relatedMap.put(prerequisites[i][1],related);
}
int[] flags = new int[numCourses];
// 判断每个课程的学习会不会成环
for(int i = 0; i < numCourses; i++){
if(!dfs(relatedMap,flags,i)){
return false;
}
}
return true;
}
public boolean dfs(Map<Integer,List<Integer>> relatedMap, int[] flags, int num){
if(flags[num] == 1){ //注意点一
return false;
}
if(flags[num] == -1){
return true;
}
flags[num] = 1;
if(relatedMap.containsKey(num)){
for(Integer related : relatedMap.get(num)){
if(!dfs(relatedMap,flags,related)){
return false;
}
}
}
flags[num] = -1;
return true;
}
- 注意点
- 注意点一。学习路线上遇到1的课程，说明已经学习路线成环了
210. 课程表 II
-
思路
-
使用拓扑排序算法。可以讲图的依赖路线转化成二维数组
-
需要借助两个数据结构
- 入度数组。每个节点的前驱节点个数。为0说明当前节点依赖项
- 邻接表。每个节点的后继节点。
-
从入度为0的节点开始检查，为0可以加入到结果中，根据领接表找到后继节点，入度-1。循环检查入度为0的节点
-
-
代码
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 构建入度数组和邻接表
HashSet<Integer>[] relations = new HashSet[numCourses];
int[] inDegree = new int[numCourses];
for(int i = 0; i < numCourses; i++){
relations[i] = new HashSet<>();
}
for(int[] realtion : prerequisites){
int front = realtion[1];
int end = realtion[0];
relations[front].add(end);
inDegree[end] ++;
}
int[] res = new int[numCourses];
int count = 0;
// 循环处理入度0的节点
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(inDegree[i] == 0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
Integer curr = queue.poll();
res[count++] = curr;
for(Integer relation : relations[curr]){
// 扣除后继节点的入度后，为0继续加入到队列
inDegree[relation]--;
if(inDegree[relation] == 0){
queue.offer(relation);
}
}
}
if(count == numCourses){
return res;
}
return new int[0];
}