LeetCode 899. 有序队列

LeetCode 899. 有序队列

文章目录

​​题目描述​​​​思路​​​​代码​​​​扩展​​

题目描述

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。

返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。

思路

一开始想的比较简单，从前k个位置中，不断地将逆序对的第一个字符移动到最后的位置即可。

于是会看到这样一个用例：

“baaca”2

采用上述策略，得到的答案是：​​aacab​​​，而实际可以得到的答案是​​aaabc​​。

容易发现，当​​k >= 2​​ 时，可以将原先的字符串，进行任意的变换，也就是说能得到任意的字符串，那么当然也能得到字典序最小的字符串了。

在​​k = 2​​时，我们可以交换字符串中的任意两个相邻的字符，并保持其余字符不变

比如原字符串为​​1234ab56789​​​，我们希望交换​​ab​​

那么可以不断的把首字符移到末尾，直到​​ab​​出现在首部

​​ab567891234​​

随后我们将​​a​​​移到末尾，得到​​b567891234a​​

接着，将​​b​​​的后一位不断交换到末尾（使得​​a​​​不断往前走），得到​​ba567891234​​

再将​​ba​​​旋转到原先的位置（不断将首位字符移动到尾部），得到​​1234ba56789​​

这样就实现了交换​​ab​​两个字符。

同理，我们可以在保持其余字符位置不变的情况下，交换其他的任意两个相邻字符。

只要我们能够交换任意相邻两个字符，就能实现冒泡排序。

于是，在​​k = 2​​时，我们总是能够得到排序好的字符串，即总是能得到字典序最小的字符串。

对于​​k > 2​​，就更不用说了。

而在​​k = 1​​​时，我们每次只能将首位字符交换到尾部，能构造出的字符串，一共只有​​n​​​种情况（​​n​​​是字符串的长度，每个字符都可以充当首位，所以共​​n​​种）。

代码

思路想出来了，代码就非常好写了。这道题难点在于思路。

我们只需要分类讨论一下，​​k = 1​​​时，把字符串整个轮转一遍，找出字典序最小的即可；​​k >= 2​​时，对字符串按照字典序排序即可。

class Solution { public String orderlyQueue(String s, int k) { int n = s.length(); if (k == 1) { String ans = s; for (int i = 0; i < n; i++) { s = s.substring(1) + s.charAt(0); if (ans.compareTo(s) > 0) ans = s; } return ans; } // k = 2 char[] chars = s.toCharArray(); Arrays.sort(chars); return new String(chars); }}

在​​k = 1​​时需要开辟额外的空间来存储所有可能的字符串（因为Java中的字符串是不可变对象）

扩展

字符串的最小表示法：寻找字符串旋转能得到的最小字典序

TODO

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。