课程顺序
题目
现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。
给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。
请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。
可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
链接
拓扑排序题解
思路：很经典的拓扑排序题目了，记录课程的依赖关系为入度和出度，BFS遍历得到拓扑排序序列，判断序列长度是否==所有课程数目，是则给返回拓扑排序结果，否则返回空数组
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//拓扑排序
vector<int>indegree(numCourses,0);
vector<vector<int>>outnodes(numCourses);
for(auto courses: prerequisites){
indegree[courses[0]]++;//修0需要先修1
outnodes[courses[1]].emplace_back(courses[0]);
}
queue<int>q;
for(int i=0;i<numCourses;i++){
if(indegree[i]==0){
q.push(i);
}
}
vector<int>ans;
while(!q.empty()){
int size=q.size();
for(int i=0;i<size;i++){
int u=q.front();
q.pop();
ans.emplace_back(u);
for(auto v:outnodes[u]){
indegree[v]--;
if(indegree[v]==0){
q.push(v);
}
}
}
}
if(ans.size()!=numCourses){
return {};
}
return ans;
}
};
外星文字典
题目
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
链接
拓扑排序题解
思路：本质上和上一题一样，但是需要自己构建有向图；
需要注意的主要是特判的情况：
- 当出现字典中["abc","ab"]的时候，明显字典本身语法有问题，返回""
- 当出现回路比如["x","z","x"]，在构建的
graph中即存在graph[i][j]和graph[i][j]同时为'true'，即双向箭头，明显不合理，返"" - 回路的另一个判别为indegree<0,说明反复走回来一个节点，返回""
class Solution {
public:
string alienOrder(vector<string>& words) {
//根据这个词典构建一个入度和出度表，最后给出拓扑排序的序列
int n=words.size();
vector<int>indegree(26,-1);
vector<vector<char>>outnodes(26);
//初始化
int cnt=0;
for(int i=0;i<n;i++){
for(auto w:words[i]){
if(indegree[w-'a']!=0){
cnt++;
indegree[w-'a']=0;
}
}
}
//构建先后关系的图
vector<vector<bool>>graph(26,vector<bool>(26,false));
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
bool flag=false;
for(int k=0;k<min(words[i].length(),words[j].length());k++){
if(words[i][k]!=words[j][k]){
graph[words[i][k]-'a'][words[j][k]-'a']=true;
flag=true;
break;
}
}
if(flag){
break;
}else if(words[i].length()>words[j].length()){//特判：字典中比如"abc","ab"这种序列表明自带语法错误
return "";
}
}
}
//遍历有向图
for(int i=0;i<26;i++){
for(int j=i+1;j<26;j++){
if(graph[i][j]&&graph[j][i]){
return "";
}else if(graph[i][j]){
//i->j
// if(indegree[j]==-1){
// indegree[j]=1;
// }else{
indegree[j]++;
// }
// if(indegree[i]==-1){
// indegree[i]=0;
// }
outnodes[i].emplace_back(j);
}else if(graph[j][i]){
//j->i
// if(indegree[i]==-1){
// indegree[i]=1;
// }else{
indegree[i]++;
// }
// if(indegree[j]==-1){
// indegree[j]=0;
// }
outnodes[j].emplace_back(i);
}
}
}
queue<int>q;
for(int i=0;i<26;i++){
if(indegree[i]==0){
q.push(i);
}
}
string ans="";
while(!q.empty()){
int size=q.size();
for(int i=0;i<size;i++){
int u=q.front();
q.pop();
ans+=('a'+u);
for(auto v:outnodes[u]){
indegree[v]--;
if(indegree[v]==0){
q.push(v);
}
if(indegree[v]<0){
// printf("???");
return "";
}
}
}
}
if(ans.length()!=cnt){
return "";
}
return ans;
}
};