C ++中的有序队列
假设有一个字符串S。S中的所有字母均为小写。然后,我们可以采取任何行动。
在这里,在每一步中,我们选择前K个字母之一,并将其删除,然后将其放在字符串的末尾。我们必须找到在任意移动之后我们可以拥有的按字典顺序最小的字符串。
因此,如果输入像“cabaa”且K=3,则输出将为“aaabc”
为了解决这个问题,我们将遵循以下步骤-
如果K>1,则-
排序数组S
返回S
ret:=S
n:=S的大小
对于初始化i:=1,当i<n时,更新(将i增加1),-
ret=S
S:=剪切S的第一个字符并将其末尾添加到S中
如果S<ret,则-
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h> using namespace std; class Solution { public: string orderlyQueue(string S, int K) { if(K > 1){ sort(S.begin(), S.end()); return S; } string ret = S; int n = S.size(); for(int i = 1; i < n; i++){ S = S.substr(1) + S.substr(0, 1); if(S < ret) ret = S; } return ret; } }; main(){ Solution ob; cout << (ob.orderlyQueue("cabaa", 3)); }
输入值
"cabaa", 3
输出结果
aaabc