赞
踩
在数据结构中我们学过 拓扑排序以及图的相关知识,在这里我们进行简单的复习↓
我们下文要解的算法题,都可以用这种关系图来表示。
在数据结构中我们学过:
由于拓扑排序是用于找到一系列事件执行的先后顺序,实际上结果并不一定唯一。我们只需要从某个起点开始进行搜索,每次删掉搜索位置,直至最后看图是否有环。
如何进行排序?
简单来说,我们提供的方法:借助队列,进行一次BFS
我们通过下面一道题加深对拓扑排序的理解,以及代码的编写。
示例:
思路
我们知道,对于任意的有向图,都可以用相应的邻接表 / 邻接矩阵表示,当我们要用代码作图,只需要利用邻接矩阵 + 容器即可。
根据前面提到的实现思路 + 代码思路 ,以及上面的作图方法,就可以着手写代码了
代码
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { // 0. 初始化 unordered_map<int, vector<int>> AList; // 哈希表作邻接表 表示图 vector<int> inDegree(numCourses); // 记录每个点的入度 // 1. 建图 for(auto e : prerequisites) { int a = e[0], b = e[1]; // 提取一条边: b->a AList[b].push_back(a); inDegree[a]++; // 更新入度 } // 拓扑排序 // (1) 将所有入度为0的点加入到队列 queue<int> q; for(int i = 0; i < numCourses; ++i) { if(inDegree[i] == 0) q.push(i); } // (2) 进行bfs while(q.size()) { int t = q.front(); q.pop(); // 对邻接表的行t进行: for(int x : AList[t]) { inDegree[x]--; if(inDegree[x] == 0) q.push(x); } } // 3. 判断此时表是否有环 for(int i = 0; i < inDegree.size(); ++i) if(inDegree[i]) return false; // in[i] 如果!=0 则入度不为0,依然有元素(成环) return true; }
思路
题意分析:这道题的思路与上一道题一模一样!唯一的区别就是本题要求返回任意一种存在的顺序即可。
解法:拓扑排序 + bfs
vector<vector<int>>
进行邻接表的创建代码
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> AList(numCourses); // 邻接表 vector<int> inD(numCourses), ret; // inD用于记录入度 // 1. 建图 for(auto e : prerequisites) { int a = e[0], b = e[1]; inD[a]++; AList[b].push_back(a); } // 2. 将入度为0的点入队 queue<int> q; for(int i = 0; i < inD.size(); ++i) if(inD[i] == 0) q.push(i); // 3. 拓扑排序 // (1) bfs while(q.size()) { int t = q.front(); q.pop(); ret.push_back(t); for(int x : AList[t]) { inD[x]--; if(inD[x] == 0) q.push(x); } } // 存在环,返回空数组 if(ret.size() != numCourses) return {}; return ret; }
思路
hash<type, hash<type>>
hash<char, int>
代码
class Solution { public: // 定义全局变量,在写功能函数时不用多余传参 unordered_map<char, unordered_set<char>> AList; // 邻接表建图 unordered_map<char, int> inD; // 统计入度 bool Illegal; // 用于标记比较是否合法 string alienOrder(vector<string>& words) { // 初始化入度哈希表 + 建图 for(string &s : words) for(char ch : s) inD[ch] = 0; // 初始化入度哈希表 for(int i = 0; i < words.size(); ++i) for(int j = i + 1; j < words.size(); ++j) { compare(words[i], words[j]); if(Illegal) return ""; } // 拓扑排序 queue<char> q; for(auto [a, b] : inD) // 将入度为0的字母加入到队列 if(b == 0) q.push(a); string ret = ""; while(q.size()) { char t = q.front(); q.pop(); ret += t; for(char ch : AList[t]) { if(--inD[ch] == 0) q.push(ch); } } // 判断结果 for(auto [a, b] : inD) if(b != 0) return ""; return ret; } void compare(string &s1, string &s2) { int minLen = min(s1.size(), s2.size()); int i = 0; // 循环外也需要i,定义到循环外 for(; i < minLen; ++i) { if(s1[i] != s2[i]) { char a = s1[i], b = s2[i]; // 如果邻接哈希表没有a / 邻接表没有a->b if(!AList.count(a) || !AList[a].count(b)){ AList[a].insert(b); // 加上关系 a->b inD[b]++; } break; } } // 特殊情况:abc ab if(i == minLen && s1.size() > s2.size()) Illegal = true; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。