LeetCode 899. Orderly Queue

一时失言乱红尘 2021-11-29 12:48 97阅读 0赞

899. Orderly Queue(有序队列)

题目：

给出了一个由小写字母组成的字符串 `S`。然后，我们可以进行任意次数的*移动*。

在每次移动中，我们选择前 `K` 个字母中的一个（从左侧开始），将其从原位置移除，并放置在字符串的末尾。

返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。

示例 1：

输入：S = "cba", K = 1
    　　输出："acb"
    　　解释：
    　　在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
    　　在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。

示例 2：

输入：S = "baaca", K = 3
    　　输出："aaabc"
    　　解释：
    　　在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
    　　在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

提示：

1.  1.  `　　1 <= K <= S.length <= 1000`
    2.  `　　S` 只由小写字母组成。

思路：

这题的设定其实有点迷，当K==1时，就代表前后次序（相对位置）并没有改变，只是在开头的可以移到后端。当K！=1时，就代表可以随意组合，直接计算字典最小的序列即可。

直接分类讨论，=1时，新建S=S+S，从前往后取len位比较即可；！=1时，拆为数组，排序，组合即可。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public static String orderlyQueue(String S, int K) 
     2     {
     3         int len = S.length();
     4         
     5         if(K==1)
     6         {
     7             String word = S;
     8             S = S + S;
     9             for(int i = 0;i < len;i++)
    10             {
    11                 if(word.compareTo(S.substring(i,i+len))>0)
    12                     word = S.substring(i,i+len);
    13             }
    14             return word;
    15         }
    16         else 
    17         {
    18             char [] word = S.toCharArray();
    19             Arrays.sort(word);
    20             StringBuilder sb=new StringBuilder();
    21             for(int i=0;i<S.length();i++)
    22                 sb.append(word[i]);
    23             return sb.toString();
    24         }
    25     }

转载于:https://www.cnblogs.com/blogxjc/p/10936318.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/f6d29bc3df7d456987d0c400e51c3ce6.png