题目描述

leetcode899. 有序队列

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

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

 

示例 1：

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

示例 2：

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

 

提示：

  • 1 <= k <= S.length <= 1000
  • s 只由小写字母组成。

题解——脑筋急转弯——直观证明

思路

当k==1时，相当于将一个环切开，使字典序最小，直接模拟即可，无需多言
当k>=2时，可以证明，经过有限次的操作，一定可以变成升序，所以直接sort返回即可
下面证明之，分为两步

  • 一、可以交换任意两个相邻的字符
    我们总是可以把要交换的两个字符移到最前面，然后先移动第二个，再移动第一个，接着复原，就达成了交换的目的。
    举个例子，例如bdcae,我们希望交换c和a，依次执行如下操作
    • 将bd移到后面，使ca移到最前面，得到caebd
    • 先移动a，再移动c，实现交换，得到ebdac
    • 其他位置复原，即将e移动到后面，得到bdace，完成交换
  • 二、通过不断交换两个相邻字符，可以排列成升序
    类似于冒泡排序的思想，不断地比较并交换相邻的字符，可以依次地将最大的、次大的、第三大的……移到后面，完成升序排列。

综上，我们就证明了当k>=2时，一定可以得到有序字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string orderlyQueue(string s, int k) {
        if(k==1)//k==1,模拟
        {
            string ans = s;
            for (int i = 1; i <= s.size()-1; ++i)//比较n-1次即可
            {
                s+=s[0];//添加到尾部
                s.erase(0,1);//删除头部
                ans = min(ans,s);
            }
            return ans;
        }
        sort(s.begin(),s.end());//k>=2,排序返回
        return s;
    }
};