資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中查詢排列
假設我們有一個由字元 'D' 和 'I' 組成的秘密簽名。'D' 表示兩個數字之間的遞減關係，'I' 表示兩個數字之間的遞增關係。這個秘密簽名是由一個特殊的整數陣列構造的，該陣列包含從 1 到 n 的所有不同數字。
例如，秘密簽名 "DI" 可以由陣列 [2,1,3] 或 [3,1,2] 構造，但不能由陣列 [3,2,4] 或 [2,1,3,4] 構造，因為這兩個陣列都是非法的，無法構造出表示 "DI" 秘密簽名的特殊字串。
現在我們需要找到 [1, 2, ... n] 的字典序最小的排列，該排列可以對應輸入的給定秘密簽名。
因此，如果輸入為 "DI"，則輸出將為 [2,1,3]。我們知道 [3,1,2] 也可以構造秘密簽名 "DI"，但由於我們希望找到字典序最小的排列，因此我們需要輸出 [2,1,3]。
為了解決這個問題，我們將遵循以下步驟：
定義一個棧 st
cnt := 2
定義一個數組 ret
初始化 i := 1，當 i <= s 的大小，更新（i 增加 1），執行：
如果 s[i - 1] 等於 'D'，則：
將 i 插入 st
否則
將 i 插入 ret 的末尾
當 (st 不為空) 時，執行：
將 st 的頂部元素插入 ret 的末尾
從 st 中刪除元素
將 s 的大小插入 st
當 (st 不為空) 時，執行：
將 st 的頂部元素插入 ret 的末尾
從 st 中刪除元素
返回 ret
示例
讓我們看一下以下實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int< findPermutation(string s) {
stack <int< st;
int cnt = 2;
vector <int< ret;
for(int i = 1; i <= s.size(); i++){
if(s[i - 1] == 'D'){
st.push(i);
}
else{
ret.push_back(i);
while(!st.empty()){
ret.push_back(st.top());
st.pop();
}
}
}
st.push(s.size() + 1);
while(!st.empty()){
ret.push_back(st.top());
st.pop();
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findPermutation("DIID"));
}輸入
"DIID"
輸出
[2, 1, 3, 5, 4, ]
更新於: 2020-11-19
279 次瀏覽
廣告