There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where $\text{prerequisites}[i] = [a_i, b_i]$ indicates that you must take course $b_i$ first if you want to take course $a_i$.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
queue为空时, 若list包含所有vertex, 说明图中无环, list即为一个topologically sorted order
该算法的时间复杂度为$O(v + e)$(v为vertex数, e为edge数)
classSolution { publicbooleancanFinish(int numCourses, int[][] prerequisites) { List<Integer>[] nodes = newList[numCourses]; for (inti=0; i < numCourses; i++) { nodes[i] = newArrayList<>(); } int[] indegrees = newint[numCourses]; for (int[] p: prerequisites) { if (p[0] == p[1]) returnfalse; indegrees[p[0]]++; nodes[p[1]].add(p[0]); } Queue<Integer> q = newLinkedList<>(); for (inti=0; i < numCourses; i++) { if (indegrees[i] == 0) { q.offer(i); } } intcnt=0; while (!q.isEmpty()) { inti= q.poll(); for (int j: nodes[i]) { if (--indegrees[j] == 0) { q.offer(j); } } cnt++; } return cnt == numCourses; } }
329. Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].
classSolution { publicintlongestIncreasingPath(int[][] matrix) { intm= matrix.length, n = matrix[0].length; List<Integer>[] edges = newList[m * n]; for (inti=0; i < m * n; i++) { edges[i] = newArrayList<>(); } int[] indegrees = newint[m * n]; int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}}; for (inti=0; i < m; i++) { for (intj=0; j < n; j++) { for (int[] dir: dirs) { intx= i + dir[0], y = j + dir[1]; if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue; indegrees[x * n + y]++; edges[i * n + j].add(x * n + y); } } } Queue<int[]> q = newLinkedList<>(); for (inti=0; i < m * n; i++) { if (indegrees[i] == 0) q.offer(newint[]{i, 1}); } int[] path = newint[m * n]; intres=0; while (!q.isEmpty()) { int[] t = q.poll(); res = Math.max(res, t[1]); for (int j: edges[t[0]]) { if (--indegrees[j] == 0) { path[j] = Math.max(path[j], t[1]+1); q.offer(newint[]{j, path[j]}); } } } return res; } }
1632. Rank Transform of a Matrix
Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].
The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:
The rank is an integer starting from 1.
If two elements p and q are in the same row or column, then:
If p < q then rank(p) < rank(q)
If p == q then rank(p) == rank(q)
If p > q then rank(p) > rank(q)
The rank should be as small as possible.
Example 1:
Input: matrix = [[1,2],[3,4]] Output: [[1,2],[2,3]] Explanation: The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column. The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1. The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1. The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
privatevoidunion(int i, int j) { i = find(i); j = find(j); if (i == j) return; if (ranks[i] <= ranks[j]) { parents[i] = j; if (ranks[i] == ranks[j]) ranks[j]++; } else { parents[j] = i; } } }
2246. Longest Path With Different Adjacent Characters
You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.
You are also given a string s of length n, where s[i] is the character assigned to node i.
Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "abacbe" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned. It can be proven that there is no longer path that satisfies the conditions.
classSolution { publicintlongestPath(int[] parent, String s) { intn= s.length(), res = 0; int[][] path = newint[n][2]; int[] indegrees = newint[n]; for (inti=0; i < n; i++) { if (parent[i] < 0) continue; indegrees[parent[i]]++; } Queue<Integer> q = newLinkedList<>(); for (inti=0; i < n; i++) { if (indegrees[i] == 0) { q.offer(i); } } while (!q.isEmpty()) { inti= q.poll(), j = parent[i]; res = Math.max(res, 1 + path[i][0] + path[i][1]); // longest path for current node if (j == -1) continue; if (--indegrees[j] == 0) { q.offer(j); } if (s.charAt(i) == s.charAt(j)) continue; intp=1 + Math.max(path[i][0], path[i][1]); // longest path for parent node if (p > path[j][0]) { // update longest path path[j][1] = path[j][0]; path[j][0] = p; } elseif (p > path[j][1]) { // update second longest path path[j][1] = p; } } return res; } }
2127. Maximum Employees to Be Invited to a Meeting
A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees.
The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.
Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the $i^{th}$ employee, return the maximum number of employees that can be invited to the meeting.
Example 1:
Input: favorite = [2,2,1,2] Output: 3 Explanation: The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table. All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously. Note that the company can also invite employees 1, 2, and 3, and give them their desired seats. The maximum number of employees that can be invited to the meeting is 3.