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, ]

Arnab Chakraborty

更新于: 2020-11-19

279 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习