【道德经·第三十二章】道常无名，朴。虽小，天下莫能臣。候王若能守之，万物将自宾。天地相合，以降甘露，民莫之令而自均。
给一个数组 prerequisites，返回你为了学完所有课程所安排的学习顺序。
示例 1:
1
2
| 输入: numCourses = 2, prerequisites = [[1,0]]
输出: [0,1]
|
示例 2:
1
2
| 输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
|
示例 3:
1
2
3
| 输入: numCourses = 1, prerequisites = []
输出: [0]
解释: 总共 1 门课，直接修第一门课就可。
|
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int> > graph;
vector<int> inDegrees(numCourses, 0);
for(auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
inDegrees[pre[0]]++;
}
queue<int> q;
for(int i = 0; i < numCourses; i++) {
if(inDegrees[i] == 0) {
q.push(i);
}
}
vector<int> res;
while(!q.empty()) {
int node = q.front();
q.pop();
res.push_back(node);
for(int n : graph[node]) {
inDegrees[n]--;
if(inDegrees[n] == 0) {
q.push(n);
}
}
}
if(res.size() != numCourses) {
return {};
}
return res;
}
};
|
根据词典还原出此语言中已知的字母顺序，并按字母递增顺序排列。
示例 1：
1
2
| 输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"
|
示例 2：
1
2
| 输入：words = ["z","x"]
输出："zx"
|
示例 3：
1
2
3
| 输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。
|
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char> > graph;
unordered_map<char, int> inDegrees;
for(auto& word : words) {
for(char c : word) {
if(!graph.count(c)) {
graph[c] = {};
}
if(!inDegrees.count(c)) {
inDegrees[c] = 0;
}
}
}
for(int i = 1; i < words.size(); i++) {
int j = 0;
int minlen = min(words[i-1].size(), words[i].size());
for(; j < minlen; j++) {
char c1 = words[i-1][j];
char c2 = words[i][j];
if(c1 != c2) {
if(!graph[c1].count(c2)) {
graph[c1].insert(c2);
inDegrees[c2]++;
}
break;
}
}
if(j==minlen && words[i-1].size()>words[i].size()) {
return {};
}
}
string res;
queue<char> q;
for(auto& d : inDegrees) {
if(d.second == 0) {
q.push(d.first);
}
}
while(!q.empty()) {
char c = q.front();
q.pop();
res.push_back(c);
for(auto& c : graph[c]) {
inDegrees[c]--;
if(inDegrees[c] == 0) {
q.push(c);
}
}
}
if(res.size() != inDegrees.size()) {
return "";
}
return res;
}
};
|
请判断原始的序列 org 是否可以从序列集 seqs 中唯一地 重建 。
示例 1：
1
2
3
| 输入: org = [1,2,3], seqs = [[1,2],[1,3]]
输出: false
解释：[1,2,3] 不是可以被重建的唯一的序列，因为 [1,3,2] 也是一个合法的序列。
|
示例 2：
1
2
3
| 输入: org = [1,2,3], seqs = [[1,2]]
输出: false
解释：可以重建的序列只有 [1,2]。
|
示例 3：
1
2
3
| 输入: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
输出: true
解释：序列 [1,2], [1,3] 和 [2,3] 可以被唯一地重建为原始的序列 [1,2,3]。
|
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
unordered_map<int, unordered_set<int> > graph;
vector<int> inDegrees(org.size()+1, -1);
for(auto& seq : seqs) {
for(int& num : seq) {
if(num<1 || num>org.size()) {
return false;
}
if(!graph.count(num)) {
graph[num] = {};
}
if(inDegrees[num] == -1) {
inDegrees[num] = 0;
}
}
for(int i = 0; i < seq.size()-1; i++) {
int num1 = seq[i];
int num2 = seq[i+1];
if(!graph[num1].count(num2)) {
graph[num1].insert(num2);
inDegrees[num2]++;
}
}
}
queue<int> q;
int index = 0;
for(int i = 1; i < inDegrees.size(); i++) {
if(inDegrees[i] == 0) {
if(q.size()==0 && org[index++]==i) {
q.push(i);
} else {
return false;
}
}
}
while(!q.empty()) {
int node = q.front(); q.pop();
for(auto& next : graph[node]) {
inDegrees[next]--;
if(inDegrees[next] == 0) {
if(q.size()==0 && org[index++]==next) {
q.push(next);
} else {
return false;
}
}
}
}
return index==org.size();
}
};
|
位我上者，灿烂星空；道德律令，在我心中。