【C/C++】899. 有序队列

---

题目链接：899. 有序队列

题目描述

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

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

提示:

• 1⩽k ⩽S.length ⩽10001 \leqslant k \leqslant S.length \leqslant 10001⩽k ⩽S.length ⩽1000
• s 只由小写字母组成。

示例 1：

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

示例 2：

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

整理题意

题目给定一个字符串 s 和一个整数 k，我们可以任取字符串 s 的前 k 个字符中的任意一个字符放到字符串 s 的末尾。可以无限次操作，要求返回操作后字典序最小的字符串。

解题思路分析

分类讨论

• 当 k = 1 时：我们只能对字符串 s 进行轮转，模拟 n - 1 次轮转取字典序最小的即可。
• 当 k = 2 时：我们将字符串的第一个位置 s[0] 单独拎出来，剩下的位置形成一个轮盘： 通过不断将 s[1] 放到字符串 s 的末尾，可以实现 [1, n - 1] 的轮转：
  • 那么我们可以在适当的时候将 s[0] 插入转盘（也就是将 s[0] 放到队尾）
  • 我们也可看作在适当的时候将 s[1] 拎出来放到 s[0]。
  根据以上思维我们可以得知：我们可以将任意元素放到 s[0] 位置，也可以将 s[0] 位置元素插入到转盘中任意位置，也就是可以将 s[0] 和 字符串中 [1, n - 1] 上任意一个元素进行交换。那么我们即可对 s 进行排序，所以字典序最小即为对 s 字符串进行升序排序即为答案。
• 当 k > 2 时：我们可以将其看作 k = 2 进行处理即可。

综上核心思想：当 k > 1 时将 [1, n - 1] 看作一个轮转转盘，s[0] 可以和轮盘上任意一个元素进行位置交换，那么即可对字符串 s 进行排序。

具体实现

1. 首先处理 k = 1 的情况：暴力遍历轮转的所有情况，取字典序最小即可。
2. 当 k > 1 时：因为证明当 k > 1 时我们总能通过有限次操作将字符串 s 进行排序，所以直接返回升序排序后的字符串 s 即可。

复杂度分析

• 时间复杂度：O(n2)O(n^2)O(n2)，其中 n 是字符串 s 的长度。当 k = 1 时需要遍历 n 个可能的字符串，每个字符串需要 O(n)O(n)O(n) 的时间生成和判断是否字典序最小，时间复杂度是 O(n2)O(n^2)O(n2)；当 k > 1 时需要对字符串排序，时间复杂度是 O(nlog⁡n)O(n \log n)O(nlogn)。最坏情况下时间复杂度是 O(n2)O(n^2)O(n2)。
• 空间复杂度：O(n)O(n)O(n)，其中 n 是字符串 s 的长度。

代码实现

class Solution {
public:
    string orderlyQueue(string s, int k) {
        // 分类讨论
        if(k == 1){
            // ans 记录字典序最小的字符串
            string ans = s;
            int n = s.length();
            // 不断将第一个元素放到末尾取字典序最小
            // 注意仅需 n - 1 次即可，n 次又回到 s 串本身
            for(int i = 0; i < n - 1; i++){
                char c = s[0];
                s = s.substr(1) + c;
                if(s < ans) ans = s;
            }
            return ans;
        }
        else{
            // 当 k > 1 时我们总能通过有限次操作将 s 串按照升序排序 
            sort(s.begin(), s.end());
            return s;
        }
    }
};

总结

• 该题的核心思想在于 当 k > 1 时将 [1, n - 1] 看作一个轮转转盘，s[0] 可以和轮盘上任意一个元素进行位置交换。
• 该题的难点在于考虑 k > 1 的情况，因为可以无限次操作，所以很容易猜到是对字符串 s 进行排序，但是需要认真考虑为什么能够对字符串进行排序。
• 上述做法在 k = 1 时寻找字典序最小的字符串需要 O(n2)O(n^2)O(n2) 的时间。如果使用最小表示法，则可以将时间复杂度降低到 O(n)O(n)O(n)。由于最小表示法超出了面试的范围，因此这里不具体讲解，感兴趣的读者可以参考 最小表示法。
• 测试结果：

结束语

有了爱好的人生，每一天都是有趣的。绘画、写作、插花、做手工、听音乐，只要你愿意用心探索，就会发现生活中藏着无穷的乐趣。不管到了什么样的年龄，愿我们都能心有所爱、眼有山河，对一切都保持着少年般的热枕。新的一天，加油！