topological sorting, DFS and BFS

LLLgoyour · Dec 26, 2023 · b6fa89d · b6fa89d
1 parent b3d277b
commit b6fa89d
Show file tree

Hide file tree

Showing 2 changed files with 83 additions and 0 deletions.
diff --git a/LeetCode/207/Solution.java b/LeetCode/207/Solution.java
@@ -0,0  1,32 @@
 // https://leetcode.com/problems/course-schedule/description/
 
 class Solution {
     public boolean canFinish(int numCourses, int[][] prerequisites) {
         int[] inDeg = new int[numCourses];
         List<List<Integer>> adjacency = new ArrayList<>();
         Queue<Integer> queue = new LinkedList<>();
         for (int i = 0; i < numCourses; i  ) {
             adjacency.add(new ArrayList<>());
         }
         for (int[] tmp : prerequisites) {
             adjacency.get(tmp[1]).add(tmp[0]);
             inDeg[tmp[0]]  ;
         }
         for (int i = 0; i < numCourses; i  ) {
             if (inDeg[i] == 0) {
                 queue.add(i);
             }
         }
         while (!queue.isEmpty()) {
             int tmp = queue.poll();
             numCourses--;
             for (int cur : adjacency.get(tmp)) {
                 inDeg[cur]--;
                 if (inDeg[cur] == 0) {
                     queue.add(cur);
                 }
             }
         }
         return numCourses-- == 0;
     }
 }
diff --git a/LeetCode/329/Solution.java b/LeetCode/329/Solution.java
@@ -0,0  1,51 @@
 // https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
 
 class Solution {
     int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
 
     public int longestIncreasingPath(int[][] matrix) {
         int m = matrix.length;
         int n = matrix[0].length;
         int[][] indegrees = new int[m][n];
         Queue<int[]> queue = new LinkedList<>(); // BFS
         for (int i = 0; i < m; i  ) {
             for (int j = 0; j < n; j  ) {
                 for (int[] dir : dirs) {
                     int nextI = i   dir[0];
                     int nextJ = j   dir[1];
                     if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n
                             && matrix[nextI][nextJ] < matrix[i][j]) {
                         indegrees[i][j]  ;
                     }
                 }
             }
         }
         for (int i = 0; i < m; i  ) {
             for (int j = 0; j < n; j  ) {
                 if (indegrees[i][j] == 0) {
                     queue.offer(new int[] { i, j });
                 }
             }
         }
         int ans = 0;
         while (!queue.isEmpty()) {
             ans  ;
             int size = queue.size();
             for (int i = 0; i < size; i  ) {
                 int[] pos = queue.poll();
                 for (int[] dir : dirs) {
                     int nextI = pos[0]   dir[0];
                     int nextJ = pos[1]   dir[1];
                     if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n
                             && matrix[nextI][nextJ] > matrix[pos[0]][pos[1]]) {
                         indegrees[nextI][nextJ]--;
                         if (indegrees[nextI][nextJ] == 0) {
                             queue.offer(new int[] { nextI, nextJ });
                         }
                     }
                 }
             }
         }
         return ans;
     }
 }