面试问到了一个算法题。记录一下。
题意是 给你一个字典，字典中包含各个词的先后顺序。 要你跟据词的先后顺序，给出字符的拓扑大小关系。（输入好像保证拓扑结构是一条链？）
我回答的思路是： 对于第i个字符串和第i+1个字符串，然后找到第一个不相同的字符，连一条有向边。最终构建一个DAG，然后做一个拓扑排序。
思路应该基本回答出来了。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<string> book = {"AB", "AC", "B"};
//vector<int> next(26, -1);
vector<int> edge[26];
vector<int> in_cnt(26, -1);
int head = -1;
for(int i = 1; i < book.size(); ++i) {
auto& s1 = book[i-1];
auto& s2 = book[i];
for(int k = 0; k < s1.length() && k < s2.length(); ++k) {
if(s1[k] == s2[k]) continue;
edge[s1[k] - 'A'].push_back(s2[k] - 'A');
if(in_cnt[s1[k] - 'A'] == -1) in_cnt[s1[k] - 'A'] = 0;
if(in_cnt[s2[k] - 'A'] == -1) in_cnt[s2[k] - 'A'] = 0;
++ in_cnt[s2[k] - 'A'];
break;
}
}
int u = -1;
for(int i = 0; i < 26; ++i) {
if(in_cnt[i] == 0) {
u = i;
// TODO: check invalid
break;
}
}
queue<int> que;
que.push(u);
in_cnt[u] = -1;
vector<int> path;
while(!que.empty()) {
u = que.front(); que.pop();
path.push_back(u);
for(auto& v : edge[u]) {
-- in_cnt[v];
}
for(int v = 0; v < 26; ++v) {
if(in_cnt[v] == 0) {
que.push(v);
in_cnt[v] = -1;
// TODO: check invalid
}
}
}
for(auto& u : path) {
cout << (char)(u + 'A') << " --> ";
}
cout << "END" << endl;
return 0;
}
全部评论
(3) 回帖