200. 岛屿数量
695. 岛屿的最大面积
注意深度优先遍历，对一格陆地（=='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，请看这个题解里的说明图
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（条件要 && res，res 一有 false 就可以停了），当 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;
}
}
标签：return,int,dfs,访问,grid,visited,LeetCode From： https://www.cnblogs.com/suBlog/p/17357752.html