建立 wiki 网站,wordpress 更改ico,百度网站改版提交,鞍山招聘网最新招聘目录 一、原理 1. 引例#xff1a;207.课程表 2. 应用场景 3. 代码思路 二、代码模板 三、练习 1、210.课程表Ⅱ#x1f7e2; 2、2392.给定条件下构造举证#x1f7e1; 3、310.最小高度树 #x1f7e1; 一、原理
1. 引例#xff1a;207.课程表
就如大学课程安排一样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, vectorvectorint prerequisites) {vectorvectorint 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}vectorint order;queueint 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:vectorint findOrder(int numCourses, vectorvectorint prerequisites) {vectorvectorint 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];}vectorint order;queueint 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 : vectorint();}
};
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:vectorvectorint buildMatrix(int k, vectorvectorint rowConditions, vectorvectorint colConditions) {vectorint roworder, colorder;functionbool(vectorvectorint, vectorint) topo_sort [](vectorvectorint edge, vectorint order) - bool{vectorvectorint 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];}queueint 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;};vectorvectorint ans(k, vectorint(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:vectorint findMinHeightTrees(int n, vectorvectorint edges) {if (n 1) return {0};unordered_mapint, vectorint g;vectorint 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];} vectorint ans;queueint q;for (int i 0; i n; i) if (degree[i] 1) q.push(i);while(!q.empty()) {vectorint 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;}
};
