在 C++ 中查找排列
c++server side programmingprogramming更新于 2025/3/8 13:37:17
假设我们有一个由字符"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 <= size of 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, ]
