Subject: Ordered Queue

题目：有序队列

题意：给定一个字符串 s 和一个整数 k .你可以从 s 的前 k 个字母中选择一个,并把它加到字符串的末尾.

返回 在应用上述步骤的任意数量的移动后,字典上最小的字符串 .

示例 1：

输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中,我们将第一个字符（“c”）移动到最后,获得字符串 “bac”.
在第二步中,我们将第一个字符（“b”）移动到最后,获得最终结果 “acb”.

示例 2：

输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中,我们将第一个字符（“b”）移动到最后,获得字符串 “aacab”.
在第二步中,我们将第三个字符（“c”）移动到最后,获得最终结果 “aaabc”.

题解：

当 K = 1 时, You can only move each element in a loop,The relative position cannot be changed.Therefore, only the sequence with the smallest lexicographical order in the circular movement process needs to be obtained.
当 K > 1 时, An arbitrary sequence of the current string can be generated,（有点像冒泡排序）.Therefore, sorting the original strings produces the sequence with the smallest lexicographical order.

解释：

如：s = "bdeca", k = 2;
1、	经过若干次移动,sThe first bit can be changed to 'e',It is not necessary to keep the first position at this time,The second place moves all the way to the end,until the second digit is a character'd',
	So the first two characters can be sorted by character;（Of course the first one is'd',第二位为'e',也没问题,In the past anywaykSelect any one of the bits to the end）
	in the first two lieutenants'd'移动到字符串末尾,随后将'e'移动到字符串末尾;Now there is sorting "de";
	字符串sThe first two digits are freed again to move characters;
	
2、	Move over a period of time,There can be characters'c'移动到第一位,The second bit is then used to move other characters,直到字符'd'reach second place,
	这时候字符'd'The position after that is the character'e';
	将字符'c'移动到末尾,Then the character'd'移动到末尾,Last character'e'移动到末尾;
	This forms the order again"cde"

3、如此反复,Must be able to form strings in ascending order"abcde";

具体步骤演示：

	原始：			s = "bdeca", k = 2;
	第一次：			s = "decab";	//注意此时din the first place,Then don't moved了,又刚好ein the first two;那么将d,eMove to the end respectively;
	第二次：			s = "ecabd";	
	第三次：			s = "cabde";	//看到了吗,The last two are already in ascending order"de"; 接下来将c移动到第一位,然后想办法将deMove to second,第三位;
								//这里cExactly the first;
	第四次：			s = "cbdea";	
	第五次：			s = "cdeab";	//就是这样,然后分别将c,d,e移动到最后;
	第六次：			s = "deabc";	
	第七次：			s = "eabcd";
	第八次：			s = "abcde";	//看,The last three are in ascending order again,"cde";
									//接下来依次类推
	
	第九次：			s = "bcdea";	//bfollowed by the first letter of the substringcin the first two,Then prepare to generate larger ordered substrings!
	第十次：			s = "cdeab";
	第十一次：		s = "deabc";
	第十二次：		s = "eabcd";
	第十三次：		s = "abcde";	//最终结果;

当然 k=2 can successfully turn an unordered string into an ordered one,k>2It's no problem;
So all we need to judge is k=1 以及 k>1 的情况即可;
附上leetcode官方代码：

class Solution {
    
public:
    string orderlyQueue(string s, int k) {
    
        if (k == 1) {
    
            string smallest = s;
            int n = s.size();
            for (int i = 1; i < n; i++) {
    
                char c = s[0];
                //这一步是将sbecomes a substring of itself,从下标从1开始,直到末尾
                s = s.substr(1);
                s.push_back(c);
                if (s < smallest) {
    
                    smallest = s;
                }
            }
            return smallest;
        } else {
    
            sort(s.begin(), s.end());
            return s;
        }
    }
};