JZTXT

LeetCode 图

发布时间 2023-07-03 22:27:58作者: archaique

200. 岛屿数量

695. 岛屿的最大面积

精品题解 https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

注意深度优先遍历，对一格陆地（=='1'）遍历, 就会把与它连通的所有陆地遍历到，全部标记为2, 完成一个岛屿。从而这一次标记到的作为一个岛屿数量 +1

for (int i=0; i<grid.length;i++) {
            for (int j=0;j<grid[0].length;j++) {
                // 深度优先遍历，对一格陆地（=='1'）遍历,
                // 就会把与它连通的所有陆地遍历到，全部标记为2。从而这一次标记到的作为一个岛屿数量 +1
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    islandNum++;
                }
            }
        }

岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        int islandNum = 0;
        for (int i=0; i<grid.length;i++) {
            for (int j=0;j<grid[0].length;j++) {
                // 深度优先遍历，对一格陆地（=='1'）遍历,
                // 就会把与它连通的所有陆地遍历到，全部标记为2。从而这一次标记到的作为一个岛屿数量 +1
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    islandNum++;
                }
            }
        }
        return islandNum;
    }

    private void dfs(char[][] grid, int x, int y) {
        if (!isInGrid(grid, x, y)) {
            return;
        }
        if (grid[x][y] != '1') {
            return;
        }
        // 访问过的标记为2，不再重复访问
        grid[x][y] = '2';
        // 对这个格子的上下左右分别dfs
        // 上
        dfs(grid, x, y+1);
        // 下
        dfs(grid, x, y-1);
        // 左
        dfs(grid, x-1, y);
        // 右
        dfs(grid, x+1, y);
    }

   // 判断这个格子是否已经超出了 grid 的范围
    private boolean isInGrid(char[][] grid, int x, int y) {
        // 注意是 >= 0 不是 >0
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
}

岛屿的最大面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxAreaOfIsland = 0;
        for (int i=0;i<grid.length;i++) {
            for (int j=0;j<grid[0].length;j++) {
                // 每次 dfs 完的都是一整块岛屿
                if (grid[i][j] == 1) {
                    int thisIslandArea = dfs(grid, i, j);
                    maxAreaOfIsland = Math.max(maxAreaOfIsland, thisIslandArea);
                }
            }
        }
        return maxAreaOfIsland;
    }

    private int dfs(int[][] grid, int x, int y) {
        if (!isInGrid(grid, x, y)) {
            return 0;
        }
        if (grid[x][y] != 1) {
            return 0;
        }
        grid[x][y] = 2;

        // 自己1 + 上下左右
        return 1 + dfs(grid, x, y+1)
                + dfs(grid, x, y-1)
                + dfs(grid, x-1, y)
                + dfs(grid, x+1, y);
    }

    private boolean isInGrid(int[][] grid, int x, int y) {
        return x>=0 && x<grid.length && y>=0 && y<grid[0].length;
    }
}

 

 

207. 课程表

DFS 解法

关于 dfs，请看这个题解里的说明图

https://leetcode.cn/problems/number-of-islands/solution/number-of-islands-shen-du-you-xian-bian-li-dfs-or-/

1、怎么样的有向图可以有一个拓扑排序？即怎样的有向图可以学完所有课程？

　　没有环的有向图都可以有一个拓扑排序

　　只要有环，就没法得到一个拓扑排序（因为环里一定存在相互依赖的两个课程，A 需要先学完 B 才能学，B 又需要先学完 A 才能学）

2、怎么表示图？

用 List<List<Integer>> graph 表示，index 是起始节点的课程的标志 

graph.get(index) 这个 List 就是这个起始课程可以指向的课程

用 prerequisites 初始化这个 graph ，[ai, bi] 学习 ai 必须要先学课程 bi，即有一条从 bi (prerequisites[i][1]) 指向 ai (prerequisites[i][0]) 的有向边

3、visited 访问数组有什么用？visited = new int[numCourses];

  • visited = [0] 这个课程节点还未被访问过，可以进行 dfs 访问
  • visited = [1] dfs 刚进来置为 1。表示正在被本轮 dfs 访问，如果在一轮 dfs 中访问到了 visited 为 1 的，说明它在一轮中被访问了两次，说明图里存在环，将结果置为 false ，并返回
  • visited = [2] dfs 末尾置为 2（图解里为-1）。本轮 dfs 访问完了置为 2，之后的 dfs 访问到，就表示它已经被别的轮次的 dfs 访问过，不必再重复访问。

4、整个过程是怎么样的？

先初始化好邻接表

从 0 开始遍历 numCourses，当 visited[0] 时进行 dfs，表示对以每个没访问过的课程节点为起点，开始进行 dfs

在 dfs 里面：

  • 一进来，先将 visited 置为 1
  • 对每个分支进行 dfs，在这里即为对当前节点邻接表里的所有边进行 dfs
    • 如果 visited = 0 ，可以进行 dfs
    • 如果 visited = 1，表示有环，结果置为 false 并返回
    • 如果 visited = 2，表示已经被别的轮次的 dfs 访问过了，不必再访问，什么都不用做 
  • dfs 结束，将 visited 置为 2 ，本轮次已经结束。
class Solution {

      // 邻接表
    List<List<Integer>> graph;
    // 表示是否访问过？
    int[] visited;
    boolean res;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph = new ArrayList();
        visited = new int[numCourses];
        // 只有这个有向图存在环，就不存在拓扑排序（因为有相互依赖的）
        // 只有这个有向图没有环，就存在拓扑排序
        // 所以默认为 true，只在判断存在环的地方改为 false
        res = true;

        // 初始化邻接表
        for(int i=0;i<numCourses;i++) {
            visited[i] = 0;
            List<Integer> courseList = new ArrayList();
            graph.add(courseList);
        }
        for(int[] link: prerequisites) {
            // [ai, bi] 学习 ai 必须要先学课程 bi
            // 即有一条从 bi (prerequisites[i][1])指向 ai (prerequisites[i][0]) 的有向边
            graph.get(link[1]).add(link[0]);
        }
        
        // 只要有一个环，结果就为 false，不用再继续遍历了。所以要加上条件 && res
        // 以所有课程为起点，进行 dfs
        for(int i=0;i<numCourses && res;i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return res;
    }

    private void dfs(int nowCourse) {
        // 被当前轮次的 dfs 访问这个节点
        visited[nowCourse] = 1;
        List<Integer> nextCourseList = graph.get(nowCourse);
        // 对于一个节点所有的分支进行 dfs，这里是对以这个节点为起点的所有有向边进行 dfs
        for (int i=0;i<nextCourseList.size();i++) {
            int nextCourse = nextCourseList.get(i);
            // 访问那些没有访问过的
            if (visited[nextCourse] == 0) {
                dfs(nextCourse);
            }
            else if (visited[nextCourse] == 1) {
                // 这个节点被当前轮次的 dfs 访问了两次，存在环，直接返回
                // 只有这个有向图存在环，就不存在拓扑排序（因为有相互依赖的）
                // 只有这个有向图没有环，就存在拓扑排序
                res = false;
                return;
            }
            // 对于 visited[i] == 2，被别的轮次的 dfs 访问过的，不必重复访问
        }
        // 只有一次DFS完整结束了，才能执行到这一步，这个 dfs 轮次已经结束。改为 2表示被别的轮次的 dfs 访问过了
        visited[nowCourse] = 2;
    }
}