数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告