資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究查詢字母順序，以便在 C++ 中將單詞視為已排序
假設我們有一個單詞陣列，我們必須找到英語字母表中的任何字母順序，以便給定的單詞可以被認為是按升序排序的，如果存在任何這樣的順序，否則返回“不可能”。
因此，如果輸入類似於 words = ["efgh", "wxyz"]，則輸出將為 zyxvutsrqponmlkjihgfewdcba
為了解決這個問題，我們將遵循以下步驟：
- ALPHABET := 26
- n := v 的大小
- 如果 n 等於 1，則：
- 顯示“abcdefghijklmnopqrstuvwxyz”
- 返回
- 定義一個大小為 ALPHABET 的陣列 adj
- 定義一個大小為 ALPHABET 的陣列 in 並填充 0
- pre := v[0]
- 對於初始化 i := 1，當 i < n 時，更新（將 i 增加 1），執行：
- s := v[i]
- 對於 j 在 0 到 min(pre 的大小，s 的大小) - 1 的範圍內：
- 如果 s[j] 不等於 pre[j]，則：
- 退出迴圈
- 如果 j < min(pre 的大小，s 的大小)，則：
- 在 adj[pre[j] - 'a' 的 ASCII 碼] 的末尾插入 s[j] - 'a' 的 ASCII 碼
- 將 in[s[j] - 'a' 的 ASCII 碼] 增加 1
- pre := s
- 忽略以下部分，跳到下一個迭代
- 如果 s[j] 不等於 pre[j]，則：
- 如果 pre 的大小 > s 的大小，則：
- 顯示“不可能”
- 返回
- pre := s
- 定義一個棧 my_stack
- 對於初始化 i := 0，當 i < ALPHABET 時，更新（將 i 增加 1），執行：
- 如果 in[i] 等於 0，則：
- 將 i 插入 my_stack
- 定義一個數組 out
- 如果 in[i] 等於 0，則：
- 定義一個大小為 26 的陣列 vis。填充 false
- 當 (my_stack 不為空) 時，執行：
- x := my_stack 的頂部元素
- 從 my_stack 中刪除元素
- vis[x] := true
- 在 out 的末尾插入 x + 'a' 的 ASCII 碼
- 對於初始化 i := 0，當 i < adj[x] 的大小時，更新（將 i 增加 1），執行：
- 如果 vis[adj[x, i]] 不為零，則：
- 忽略以下部分，跳到下一個迭代
- （將 in[adj[x, i]] 減少 1）
- 如果 in[adj[x, i]] 等於 0，則：
- 將 adj[x, i] 插入 my_stack
- 如果 vis[adj[x, i]] 不為零，則：
- 對於初始化 i := 0，當 i < ALPHABET 時，更新（將 i 增加 1），執行：
- 如果 vis[i] 不為零，則：
- 顯示“不可能”
- 返回
- 如果 vis[i] 不為零，則：
- 對於初始化 i := 0，當 i < out 的大小時，更新（將 i 增加 1），執行：
- 顯示 out[i]
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
#define ALPHABET 26
void search_ordering(vector<string> v) {
int n = v.size();
if (n == 1) {
cout << "abcdefghijklmnopqrstuvwxyz";
return;
}
vector<int> adj[ALPHABET];
vector<int> in(ALPHABET, 0);
string pre = v[0];
for (int i = 1; i < n; ++i) {
string s = v[i];
int j;
for (j = 0; j < min(pre.length(), s.length()); ++j)
if (s[j] != pre[j])
break;
if (j < min(pre.length(), s.length())) {
adj[pre[j] - 'a'].push_back(s[j] - 'a');
in[s[j] - 'a']++;
pre = s;
continue;
}
if (pre.length() > s.length()) {
cout << "Impossible";
return;
}
pre = s;
}
stack<int> my_stack;
for (int i = 0; i < ALPHABET; ++i)
if (in[i] == 0)
my_stack.push(i);
vector<char> out;
bool vis[26];
memset(vis, false, sizeof(vis));
while (!my_stack.empty()) {
char x = my_stack.top();
my_stack.pop();
vis[x] = true;
out.push_back(x + 'a');
for (int i = 0; i < adj[x].size(); ++i) {
if (vis[adj[x][i]])
continue;
in[adj[x][i]]--;
if (in[adj[x][i]] == 0)
my_stack.push(adj[x][i]);
}
}
for (int i = 0; i < ALPHABET; ++i)
if (!vis[i]) {
cout << "Impossible";
return;
}
for (int i = 0; i < out.size(); ++i)
cout << out[i];
}
int main() {
vector<string> v{"efgh", "wxyz"};
search_ordering(v);
}輸入
{"efgh", "wxyz"}輸出
zyxvutsrqponmlkjihgfewdcba
更新於: 2020-08-28
104 次檢視
廣告