Skip to content

899. Orderly Queue

899. Orderly Queue

题目: https://leetcode.com/problems/orderly-queue/

难度: Hard

题意：

  1. 给定一个字符串S和一个数K
  2. 每一轮可以选择字符串的前K个数的其中一个，把它移到放在最后面
  3. 无限次数后，问生成的最小字符串是什么

思路：

  • 不要考虑暴力了，由于是无限次数，连暴力搜索都无从下手，除非出动启发式搜索
  • 这是个脑筋急转弯的题目，分为两种情况
  • 当K=1时，由于每次只能取第一个放在最后面，这种情况是暴力搜索，时间复杂度是o(nk)，k是字符串的长度
  • 当K>=2时，我们拿K=2出来考虑，证明当K=2时，可以生成任一字符串。
  • 固定第一个数，不断的把第二个数放在最后面，这种做法可以使第一个数插入到队列的任一位置
  • 假设队列A1-Ak有序，我们要把第A(k+1)插入到Ak的后面，只需要把A(k+1)固定在第一个数，重复第一个做法即可
  • 根据数据归纳法，当K=2时，可以生成任一字符串
  • 因此当K>=2时，只需要排序字符串里面的字符即可

拓展：

  • 这道题有o(nlogn)的解法，当k=1时，可以用o(nlogn)的排序算法，找到最小的字符串。有兴趣的同学可以百度一下“后缀数组”，一百行代码左右，这里就不展示了

代码：

class Solution {
    public String orderlyQueue(String S, int K) {
        if (K == 1) {
            String min = S;
            for (int i = 0;i < S.length();i++) {
                S = S.substring(1, S.length()) + S.charAt(0);
                if (min.compareTo(S) > 0) {
                    min = S;
                }
            }
            return min;
        } else {
            char[] c = S.toCharArray();
            Arrays.sort(c);
            return new String(c);
        }
    }
}
回到顶部