毫无保留的亚马逊面试经验分享
最近有同学面试亚麻,果不其然遇到了原题,分享一下他的面经。
LintCode 1742有序队列
LintCode 1742
有序队列
题目描述
给出了一个由小写字母组成的字符串
S
。然后,我们可以进行任意次数的移动。在每次移动中,我们选择前
K
个字母中的一个(从左侧开始),将其从原位置移除,并放置在字符串的末尾。返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。
- 1≤K≤S.length≤1000
S
只由小写字母组成。
扫码在线做题
样例1
输入:S = "cba", K = 1
输出:"acb"
解释:
在第一步中,我们将第一个字符(“c”)移动到最后,获得字符串 “bac”。
在第二步中,我们将第一个字符(“b”)移动到最后,获得最终结果 “acb”。
样例 2:
输入:S = "baaca", K = 3
输出:"aaabc"
解释:
在第一步中,我们将第一个字符(“b”)移动到最后,获得字符串 “aacab”。
在第二步中,我们将第三个字符(“c”)移动到最后,获得最终结果 “aaabc”。
解题思路
当K>1,相当于可以任意排列,所以直接返回最小值 当K==1,有S.length不同的状态,返回按字典顺序排列的最小字符串。
源代码
public class Solution {
/**
* @param S: a string
* @param K: int
* @return: the lexicographically smallest string
*/
public String orderlyQueue(String S, int K) {
// Write your code here.
if (K > 1) {
char S2[] = S.toCharArray();
Arrays.sort(S2);
return new String(S2);
}
String res = S;
for (int i = 1; i < S.length(); i++) {
String tmp = S.substring(i) + S.substring(0, i);
if (res.compareTo(tmp) > 0) res = tmp;
}
return res;
}
}
点击【阅读原文】,查看领扣原题。
阅读原文 关键词
字符串
字母
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。