再开下一个坑，图论专题居然以前都刷过了，三道Medium也没什么好说的，直接过
994. Rotting Oranges[Medium]
发现一个很神奇的事，这一题我再5年前的时候做，还是个Easy，现在已经涨到Medium了。看来随着通货膨胀，连Leetcode的题难度也跟着一起膨胀了
看了一下，原先的思路是拆分成三个函数，check用来检测好橘子的数量，legal用于判断是否搜索到边界，grow用于进行新的一天的搜索。
算一下时间复杂度，假设区域大小为 ，最终需要
天搜索完。单次grow需要往四个方向扩展，加一次原图恢复，总计
的复杂度，单次check复杂度为
，每天的判断包含一次grow和两次check，总计
，再加一次初始化的check。整个流程的总复杂度为
LeetCodeGOGOGO刷题记06——夯实基础（预处理）_Rotting Oranges-CSDN博客
接下来开始我的表演，直接bfs
先算一下时间复杂度，假设包含 个新鲜的橘子和
个坏掉的橘子，
。一次初始化的
，加上搜索节点
，总计
。明显快多了
200. Number of Islands[Medium]
思路：典型的dfs，和之前的回溯专题极其类似，那就不多说了，直接上代码
/*
Author Owen_Q
*/
public class IslandsNumbers {
public static int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private static void dfs(char[][] grid, int i, int j) {
int n = grid.length;
int m = grid[0].length;
if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
207. Course Schedule[Medium]
思路：这就是个典型的拓扑排序判环问题。那么经典的BFS和DFS，刚好都来试一下
BFS
BFS就是经典队列问题，用一个队列来维护入度为0的节点。遍历队列中的点，将每个点的后继节点入度减一，并将入度减为0的节点放入队列中。若拓扑中存在环，则环上点永远不会进入队列，也不会度数降到1，因此只要判断是否存在入度不为0的点即可。
/*
Author Owen_Q
*/
public class CourseScheduler {
public static boolean canFinishBfs(int numCourses, int[][] prerequisites) {
List<List<Integer>> nextCourses = new java.util.ArrayList<>();
for (int i = 0; i < numCourses; i++) {
nextCourses.add(new java.util.ArrayList<>());
}
int[] inDegrees = new int[numCourses];
Queue<Integer> processingCourses = new java.util.LinkedList<>();
for (int[] prerequisite : prerequisites) {
int course = prerequisite[0];
int preCourse = prerequisite[1];
nextCourses.get(preCourse).add(course);
inDegrees[course]++;
}
for (int i = 0; i < numCourses; i++) {
if (inDegrees[i] == 0) {
processingCourses.offer(i);
}
}
while (!processingCourses.isEmpty()) {
Integer course = processingCourses.poll();
numCourses--;
for (Integer nextCourse : nextCourses.get(course)) {
inDegrees[nextCourse]--;
if (inDegrees[nextCourse] == 0) {
processingCourses.offer(nextCourse);
}
}
}
return numCourses == 0;
}
}
DFS
DFS其实就是经典的递归问题，需要用一个数组来记录每个点的访问情况。这里可以维护一个点的状态机。包含未访问，访问中和访问完成三种状态，访问中和访问完成分别对应dfs的入口和出口处。由于递归是个回溯问题，因此需要从后往前递推，当回溯到访问中的节点时即表示出现环，否则则表示顺利访问。于是遍历每个节点看能否顺利访问完所有节点即可
/*
Author Owen_Q
*/
public class CourseScheduler {
public static boolean canFinishDfs(int numCourses, int[][] prerequisites) {
int[] visited = new int[numCourses];
List<List<Integer>> preCourses = new java.util.ArrayList<>();
for (int i = 0; i < numCourses; i++) {
preCourses.add(new java.util.ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
int course = prerequisite[0];
int preCourse = prerequisite[1];
preCourses.get(course).add(preCourse);
}
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
if (canNotFinishDfs(i, visited, preCourses)) {
return false;
}
}
}
return true;
}
private static boolean canNotFinishDfs(int course, int[] visited, List<List<Integer>> preCourses) {
if (visited[course] == 0) {
visited[course] = 1;
for (Integer preCourse : preCourses.get(course)) {
if (canNotFinishDfs(preCourse, visited, preCourses)) {
return true;
}
}
} else if (visited[course] == 1) {
return true;
}
visited[course] = 2;
return false;
}
}
完结撒花
