LeetCode每日一题--有序队列(整理最小表示法)

题目要求：

给定一个字符串 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 >= 2时，可以生成任意的字符串，比如a1 b1 S(S表示多个字符),如果交换a1 b1的位置，可以先a1 S b1, 之后 S b1 a1,最后 b1 a1 S,以此类推，任何相邻的两个字符都是可以交换的，从而任意顺序的字符串都可以有，故k>=2的情况下，直接用sort()函数排序即可。

k = 1时，应用最小表示法，首先对初始字符串s+=s,在原始字符串的后面再加一遍原字符串，目的是为了当遍历0~n-1任意一个下标元素时，以其为起点，后面在加n-1个元素，即可组成一个字符串。
接着又分为三种情况：
1.如果s[i+k]==s[j+k] k++。
2.如果s[i+k] > s[j+k] i = i + k + 1，即最小表示不可能以s[i->i+k]开头。
3.如果s[i+k] < s[j+k] j = j + k + 1，即最小表示不可能以s[j->j+k]开头。
考虑对于两个字符串A，B，他们在原字符串S的起始位置分别为i和j，且他们前面的k个字符串均相同，即 A[i……i+k-1] = B[j……j+k-1] 不防先考虑 A[i+k] > B[j+k] 的情况，我们发现起始下标 p满足 i <= p <= i+k 的字符均不能成为答案。因为对于任意一个字符串Si+p（表示以i+p为起始位置的字符串）一定存在字符串 Sj+p 比它更优。我们比较时可以跳过下标 [ i , i+k ] 直接跳到Si+k+1。

时间复杂度：

$O(N)$

代码实现：

class Solution {
public:

    int s_min(string s, int n){

        int i = 0, j = 1, k = 0;

        while(i < n && j < n){
            for(k = 0;k < n && s[i+k] == s[j+k];k ++);
            s[i+k] > s[j+k] ? i = i+k+1 : j = j+k+1;
            if(i == j) j ++;
        }

        return min(i, j);
    }

    string orderlyQueue(string s, int k) {

        int n = s.size();
        if(k >= 2){
            sort(s.begin(), s.end());   
            return s;
        } 

        s += s;
        int t = s_min(s, n);

        string c = "";
        for(int i = 0;i < n;i ++) c += s[t ++];

        return c;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

参考文献：

https://blog.csdn.net/tianyuhang123/article/details/54919715
https://blog.csdn.net/Stevenwuxu/article/details/112908995