力扣 899. 有序队列

题目来源：https://leetcode.cn/problems/orderly-queue/

大致题意：
给定一个字符串，和一个整数 k，每次将字符串前 k 个字符中的一个移到字符串末尾，求重排后的字典序最小的字符串

思路

这道题不能使用动态规划，不过有点类似贪心的思路，也需要根据给定 k 的不同选择不同的解法

1. 如果给定的 k 为 1，那么每次只能将开头的一个字符串移到末尾，对于长度为 n 的字符串，只会有 n 种结果，返回 n 种结果中字典序最小的即可

2. 如果 k 大于 1，那么每次会挑选前 k 个中的一个放入尾部

接下来讨论第二种情况

题目要求返回字典序最小的字符串，那么在前 k 个字符如何选择？

如果想要最小的，每次就需要将一个较大的字符放到末尾，因为不限制交换次数，所以一定可以将整个字符串中最小的字符放入第一个（每次在前 k 个中，把较大的放到末尾，那么这样循环下去，一定可以把最小的剩下来）

于是可以将最小的先放到末尾，再对剩下的 n-1 个字符重复这个操作，可以在剩下的 n-1 个字符中选出最小的放到开头，如此循环往复，整个字符串就可以变成字典序最小的字符串

所以，当 k 大于 1 时，字典序的最小的字符串就是这个字符串所有字符升序排序后的结果

代码：

	public String orderlyQueue(String s, int k) {
        // k 为 1
        if (k == 1) {
            int n = s.length();
            String[] strs = new String[n];
            // 获取 n 个字符的 n 中排列
            for (int i = 0; i < n; i++) {
                strs[i] = s.substring(i + 1) + s.substring(0, i + 1);
            }
            // 排序后返回最小的
            Arrays.sort(strs);
            return strs[0];
        }
        // k 大于 2
        // 转为字符数组，排序后返回字符串
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return String.valueOf(arr);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19