Leedcode【899】. 有序队列——Java解法

Problem: 899. 有序队列

1. 题目
2. 思路
3. 解题方法
4. 复杂度
5. Code
6. 效果

题目

1. 有序队列
   已解答
   困难

给定一个字符串 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 只由小写字母组成。

思路

参考：https://mp.weixin.qq.com/s/ywVShtqw_ikxyPyf1d6yNQ

解题方法

k > 1 字符串排序
k == 1 最小表示法

复杂度

时间复杂度:

O(n)

空间复杂度:

添加空间复杂度, 示例： O(n)

Code

Java

class Solution {
    public String orderlyQueue(String s, int k) {
        char[] cs = s.toCharArray();
        if(k == 1){
            int i = 0, j = 1, m = 0, n = cs.length;
            while(i < n && j < n && m < n){
                char a = cs[(i+m) % n], b = cs[(j+m)%n];
                if(a == b) m++;
                else {
                    if(a > b) i += m+1;
                    else j += m+1;
                    if(i == j) i++;
                    m = 0;
                }
            }
            i = Math.min(i, j);
            return s.substring(i) + s.substring(0, i);
        } else {
            Arrays.sort(cs);
            return String.valueOf(cs);
        }
    }
}

效果