目录
一、原理
1. 引例:207.课程表
2. 应用场景
3. 代码思路
二、代码模板
三、练习
1、210.课程表Ⅱ🟢
2、2392.给定条件下构造举证🟡
3、310.最小高度树 🟡
一、原理
1. 引例:207.课程表
就如大学课程安排一样,如果要学习数据结构与算法、机器学习这类课程,肯定要先学习C语言、Python、离散数学、概率论等等,我们将类似的“推导”关系建如下有向简单图⬇️
2. 应用场景
根据节点的入度大小,拓扑排序主要用于处理先后问题(拓扑序列),以及判断图中是否有环的问题;
3. 代码思路
用大小为节点个数的数组记录每个节点的入度,用队列存放入度为0的节点,遍历这些节点,将这些节点指向的节点的入度-1,最后在记录入度减为0的节点,重复上述步骤;
①拓扑序列:在循环过程中向一数组中push入度为0的节点,排在数组前的节点即为入度先被减为0的节点;
②是否存在环:若拓扑序列数组大小等于节点总个数则说明图中无环;反之,这说明图有环
二、代码模板
/*这里用课程表一题的代码当作模板*/
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> g(numCourses);int in_degree[numCourses]; //记录节点的入度memset(in_degree, 0, sizeof(in_degree));for (auto& e : prerequisites) {int x = e[0], y = e[1]; //建图g[x].push_back(y);in_degree[y]++; // x -> y ,则y节点入度+1}vector<int> order;queue<int> q;for(int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i); //将入度为0的节点加入到队列中while (!q.empty()) {int x = q.front();q.pop();order.push_back(x); //push到拓扑序列中for (auto y : g[x]) {in_degree[y]--; //x -> y , 即将y入度-1if (in_degree[y] == 0) q.push(y);}}return order.size() == numCourses; //判断是否有环}
};
三、练习
1、210.课程表Ⅱ🟢
现在你总共有
numCourses
门课需要选,记为0
到numCourses - 1
。给你一个数组prerequisites
,其中prerequisites[i] = [ai, bi]
,表示在选修课程ai
前 必须 先选修bi
。
- 例如,想要学习课程
0
,你需要先完成课程1
,我们用一个匹配来表示:[0,1]
。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
示例:
输入:numCourses = 2, prerequisites = [[1,0]] 输出:[0,1] 解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为[0,1] 。
解题思路: 与课程表Ⅰ思路基本一样,依次取出入度为0的节点加入到答案数组中,若数组大小与总结点个数不相同,则说明图中有环,返回空数组。
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> g(numCourses);int in_degree[numCourses];memset(in_degree, 0, sizeof(in_degree));for (auto& e : prerequisites) {int x = e[1], y = e[0];g[x].push_back(y);in_degree[y]++;}vector<int> order;queue<int> q;for(int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);while (!q.empty()) {int x = q.front();q.pop();order.push_back(x);for (auto y : g[x]) {in_degree[y]--;if (in_degree[y] == 0) q.push(y);}}return order.size() == numCourses ? order : vector<int>();}
};
2、2392.给定条件下构造举证🟡
给你一个 正 整数
k
,同时给你:
- 一个大小为
n
的二维整数数组rowConditions
,其中rowConditions[i] = [abovei, belowi]
- 一个大小为
m
的二维整数数组colConditions
,其中colConditions[i] = [lefti, righti]
。两个数组里的整数都是
1
到k
之间的数字。你需要构造一个
k x k
的矩阵,1
到k
每个数字需要 恰好出现一次 。剩余的数字都是0
。矩阵还需要满足以下条件:
- 对于所有
0
到n - 1
之间的下标i
,数字abovei
所在的 行 必须在数字belowi
所在行的上面。- 对于所有
0
到m - 1
之间的下标i
,数字lefti
所在的 列 必须在数字righti
所在列的左边。返回满足上述要求的 任意 矩阵。如果不存在答案,返回一个空的矩阵。
示例:
输入:k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] 输出:[[3,0,0],[0,0,1],[0,2,0]] 解释:上图为一个符合所有条件的矩阵。 行要求如下: - 数字 1 在第 1 行,数字 2 在第 2 行,1 在 2 的上面。 - 数字 3 在第 0 行,数字 2 在第 2 行,3 在 2 的上面。 列要求如下: - 数字 2 在第 1 列,数字 1 在第 2 列,2 在 1 的左边。 - 数字 3 在第 0 列,数字 2 在第 1 列,3 在 2 的左边。 注意,可能有多种正确的答案。
解题思路:该题很明显是处理先后的问题,我们分别处理行与列,分别得到行与列拓扑序列,最后通过一个数组转换,将下标作为节点,对应的值作为该节点位于行/列的位置;
class Solution {
public:vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {vector<int> roworder, colorder;function<bool(vector<vector<int>>&, vector<int>&)> topo_sort = [&](vector<vector<int>>& edge, vector<int>& order) -> bool{vector<vector<int>> g(k);int in_deg[k];memset(left, 0, sizeof(left));for (auto& e : edge) {int x = e[0]-1, y = e[1] - 1;g[x].push_back(y);in_deg[y]++;}queue<int> q;for(int i = 0; i < k; i++) if (in_deg[i] == 0) q.push(i);while (!q.empty()) {int x = q.front();q.pop();order.push_back(x);for (auto y : g[x]) {in_deg[y]--;if (in_deg[y] == 0) q.push(y);}}return order.size() == k;};vector<vector<int>> ans(k, vector<int>(k, 0));if (!topo_sort(rowConditions, roworder) || !topo_sort(colConditions, colorder)) return {};int row[k], col[k];for (int i = 0; i < k; i++) {row[roworder[i]] = i;col[colorder[i]] = i;}for (int i = 0; i < k; i++) {ans[row[i]][col[i]] = i + 1;}return ans;}
};
3、310.最小高度树🟡
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。
给你一棵包含
n
个节点的树,标记为0
到n - 1
。给定数字n
和一个有n - 1
条无向边的edges
列表(每一个边都是一对标签),其中edges[i] = [ai, bi]
表示树中节点ai
和bi
之间存在一条无向边。可选择树中任何一个节点作为根。当选择节点
x
作为根节点时,设结果树的高度为h
。在所有可能的树中,具有最小高度的树(即,min(h)
)被称为 最小高度树 。请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例:
输入:n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 输出:[3,4]
解题思路: 本题思路较为复杂,可以大致理解为贪心,证明过程可以参考力扣官方答案。每次去掉节点入度最小的节点,到最后剩余1-2个节点即为可以作为最小高度树的根节点
class Solution {
public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {if (n == 1) return {0};unordered_map<int, vector<int>> g;vector<int> degree(n);for (auto& e : edges) {int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);degree[x]++;degree[y]++;} vector<int> ans;queue<int> q;for (int i = 0; i < n; i++) if (degree[i] == 1) q.push(i);while(!q.empty()) {vector<int> tmp;int size = q.size();while(size--) {int x = q.front();q.pop();tmp.push_back(x);for(auto y : g[x]) {if (--degree[y] == 1) q.push(y);}}ans = move(tmp);}return ans;}
};