資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 外星詞典
假設存在一種新的外星語言，它使用拉丁字母表。但是，字母之間的順序是未知的。我們有一份來自詞典的非空單詞列表，這些單詞按照這種新語言的規則按字典順序排序。我們必須找到這種語言中字母的順序。
因此，如果輸入類似於 ["wrt","wrf","er", "ett", "rftt" ]，則輸出將為 "wertf"
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 degree 的對映
定義一個名為 graph 的對映
n := 單詞的數量
對於初始化 i := 0，當 i < 單詞的數量 時，更新（i 增加 1），執行：
對於初始化 j := 0，當 j < words[i] 的大小 時，更新（j 增加 1），執行：
degree[words[i, j]] := 0
對於初始化 i := 0，當 i < n - 1 時，更新（i 增加 1），執行：
l := words[i] 的大小和 words[i + 1] 的大小的最小值
對於初始化 j := 0，當 j < l 時，更新（j 增加 1），執行：
x := words[i, j]
y := words[i + 1, j]
如果 x 不等於 y，則：
將 y 插入到 graph[x] 的末尾
（degree[y] 增加 1）
退出迴圈
ret := 空字串
定義一個佇列 q
對於 degree 中的每個鍵值對 it，執行：
如果 it 的值為 0，則：
將 it 的鍵插入到 q 中
當 (q 不為空) 時，執行：
x := q 的第一個元素
從 q 中刪除元素
ret := ret + x
對於 graph 中的每個元素 sit，執行：
degree[sit] 減 1
如果 degree[sit] 等於 0，則：
將 sit 插入到 q 中
（sit 增加 1）
返回（如果 ret 的大小等於 degree 的大小，則返回 ret，否則返回空字串）
示例
讓我們看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string alienOrder(vector<string>& words) {
map<char, int> degree;
map<char, vector<char> > graph;
int n = words.size();
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
degree[words[i][j]] = 0;
}
}
for (int i = 0; i < n - 1; i++) {
int l = min((int)words[i].size(), (int)words[i + 1].size());
for (int j = 0; j < l; j++) {
char x = words[i][j];
char y = words[i + 1][j];
if (x != y) {
graph[x].push_back(y);
degree[y]++;
break;
}
}
}
string ret = "";
queue<char> q;
map<char, int>::iterator it = degree.begin();
while (it != degree.end()) {
if (it->second == 0) {
q.push(it->first);
}
it++;
}
while (!q.empty()) {
char x = q.front();
q.pop();
ret += x;
vector<char>::iterator sit = graph[x].begin();
while (sit != graph[x].end()) {
degree[*sit]--;
if (degree[*sit] == 0) {
q.push(*sit);
}
sit++;
}
}
return ret.size() == degree.size() ? ret : "";
}
};
main(){
Solution ob;
vector<string> v = {"wrt","wrf","er","ett","rftt"};
cout <<(ob.alienOrder(v));
}輸入
{"wrt","wrf","er","ett","rftt"}輸出
wertf
455 次瀏覽
