有序队列-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
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)的排序算法，找到最小的字符串。有兴趣的同学可以百度一下“后缀数组”，一百行代码左右，这里就不展示了

代码：

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

该分类下的相关小册推荐：

编程之道-算法面试(下)

数据结构与算法(下)

业务开发实用算法精讲

编程之道-算法面试(上)

数据结构与算法之美

数据结构与算法(上)

算法面试通关 50 讲