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);
        }
    }
}


回到顶部