当前位置:网站首页>图解LeetCode——899. 有序队列(难度:困难)
图解LeetCode——899. 有序队列(难度:困难)
2022-08-04 17:48:00 【爪哇缪斯】
一、题目
给定一个字符串 s
和一个整数 k
。你可以从 s
的前 k
个字母中选择一个,并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后,字典上最小的字符串 。
二、示例
2.1> 示例 1:
【输入】s = "cba", k = 1
【输出】"acb"
【解释】在第一步中,我们将第一个字符(“c”)移动到最后,获得字符串 “bac”。在第二步中,我们将第一个字符(“b”)移动到最后,获得最终结果 “acb”。
2.2> 示例 2:
【输入】s = "baaca", k = 3
【输出】"aaabc"
【解释】在第一步中,我们将第一个字符(“b”)移动到最后,获得字符串 “aacab”。在第二步中,我们将第三个字符(“c”)移动到最后,获得最终结果 “aaabc”。
提示:
1
<= k <= S.length <=1000
s
只由小写字母组成。
三、解题思路
3.1> 思路1:根据k值是否为1去寻找规律
根据题意,我们可以知道,k值代表的就是待移动的元素范围集合,但是只能有一个元素会被移动到队尾。那么其实就可以大致分为两种情况,即:k等于1和k大于1这两种。那么我们就来一一的分析一下这两种情况所有的特性。
首先,我们来看一下k等于1的情况,当k等于1的时候,那么只需要将第一个字符移动到队尾即可,那么我们以字符串“cba”为例,当执行第一次移动时,移动后的结果为“bac”,再执行一次移动结果为“acb”,再执行一次移动后结果为“cba”。发现了没有,这个字符串一共3个字符,当k等于1时,移动了3次之后,结果还是“cba”,即:元素又“回归”为最初的字符串了。具体操作如下所示:
因此,从中我们得出了一个结论,如果k等于1的话,无论移动多少次,其实最终结果对字符的前后顺序都不会有影响,就像一个环形结构似的,不同的只是从哪个位置开始“读取”字符而已。
那么,我么再来看一下k大于1的情况。当k大于1,那么每次移动的时候,可以选择的移动元素个数就是多个了,那么也就相当于说,移动后的结果也会改变原有字符的前后顺序了。
根据题意,在多元素中会选择字符较大的移动到队尾,那么,如果我们不考虑移动次数,最终的结果会有一定的规律吗?答案是肯定的。那么规律是什么呢?其实最终的结果,就会是一个排序好的字符串。
要验证这个结论其实并不难,我们以字符串为“baaca”且k等于3为例,先尝试执行一下,看看结果是不是我们上面所总结的。首先,第一次移动时,由于k等于3,那么要求我们可以在“baa”这3个字符中选择一个字符移动到队尾,由于b是大于a的,所以,将b移动到队尾,那么字符串的结果等于“aacab”;我们继续移动,这次我们会从“aac”这3个字符中选择一个字符移动到队尾,由于c是大于a的,所以,将c移动到队尾,那么字符串的结果等于“aaabc”。通过这两次移动,我们就得到了一个字符排序好的字符串。具体操作如下所示:
为什么最终的结果会是一个排序好的字符串呢?这个其实有些类似我们排序算法中的“冒泡排序”,每次移动中,都是在一定范围内选择最大的放到队尾,那么在N次移动后,最终的结果就会变成了一个排序好的字符串了。具体代码实现,请参见:4.1> 实现1:根据k值是否为1去寻找规律
3.2> 思路2:使用StringBuilder代替String执行拼装操作
当我们采用String拼装的方式去实现新字符串的拼装之后,发现执行结果很不理想。那么有什么优化空间吗?其实我们可以尝试StringBuilder,以为当需要移动元素的时候,可以通过它所提供的deleteCharAt(...)
方法去删除待移动的元素;同样,可以通过append(...)
方法执行移动后元素的拼装。当我们将String操作都更换为StringBuilder之后,我们发现,执行耗时有了大大的缩短(根据结果,大致将执行效率提升了3倍)。具体代码实现,请参见:4.2> 实现2:使用StringBuilder代替String执行拼装操作
四、代码实现
4.1> 实现1:根据k值是否为1去寻找规律
class Solution {
public String orderlyQueue(String s, int k) {
if (k == 1) {
String result = s;
for (int i = 1; i < s.length(); i++) {
s = s.substring(1) + s.charAt(0);
if (result.compareTo(s) > 0) {
result = s;
}
}
return result;
} else {
char[] sArray = s.toCharArray();
Arrays.sort(sArray);
return new String(sArray);
}
}
}
4.2> 实现2:使用StringBuilder代替String执行拼装操作
class Solution {
public String orderlyQueue(String s, int k) {
if (k == 1) {
String result = s;
StringBuilder sb = new StringBuilder(s);
for (int i = 1; i < s.length(); i++) {
char firstChar = sb.charAt(0);
s = sb.deleteCharAt(0).append(firstChar).toString();
if (result.compareTo(s) > 0) {
result = s;
}
}
return result;
} else {
char[] sArray = s.toCharArray();
Arrays.sort(sArray);
return new String(sArray);
}
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」
题目来源:力扣(LeetCode)
边栏推荐
- 小程序学习目标
- Create Sentinel high-availability cluster current limiting middleware from -99
- 【日记】mysql基本操作
- 两个对象相同数据赋值
- 软件测试高频面试题真实分享/网上银行转账是怎么测的,设计一下测试用例。
- 集群监控——Zabbix使用
- The use of QCompleter for Qt auto-completion
- R语言ggpubr包的ggline函数可视化折线图、设置add参数为mean_se和dotplot可视化不同水平均值的折线图并为折线图添加误差线(se标准误差)和点阵图、设置折线和数据点边框颜色
- 荣耀发布开发者服务平台,智慧生态合作提速
- Codeforces积分系统介绍
猜你喜欢
从-99打造Sentinel高可用集群限流中间件
"Involution" Index Analysis Based on AHP
The second step through MySQL in four steps: MySQL index learning
】 【 LeetCode daily one problem - 540. The order of a single element of the array
CAS:474922-26-4,DSPE-PEG-NH2,DSPE-PEG-amine,磷脂-聚乙二醇-氨基供应
Understand Chisel language. 32. Chisel advanced hardware generator (1) - parameterization in Chisel
下一代 AutoAI:从模型为中心,到数据为中心
SQL优化最全总结 - MySQL(2022最新版)
CF86D Powerful array
第一章 对象和封装
随机推荐
小程序笔记3
44. 通配符匹配 ●●● & HJ71 字符串通配符 ●●
2018读书记
Cron表达式
The second step through MySQL in four steps: MySQL index learning
Codeforces积分系统介绍
Understand Chisel language. 32. Chisel advanced hardware generator (1) - parameterization in Chisel
Digital-intelligent supply chain management system for chemical manufacturing industry: build a smart supply system and empower enterprises to improve production efficiency
自定义组件,并在组件中注入自定义组件实现多种场景的下的组件切换
clickhouse 上下线表
Boost library study notes (1) Installation and configuration
八猴渲染器是什么?它能干什么?八猴软件的界面讲解
【LeetCode Daily Question】——374. Guess the size of the number
JWT主动校验Token是否过期
OpenInfra Days China 2022|SelectDB与你共享 Apache Doris 在互联网广告业务中的实践
并发编程原理学习-reentrantlock源码分析
.NET云原生应用发展论坛--8月7日邀你一起云上探索
【技术积累】JS事件循环,Promise,async/await的运行顺序
Interval greedy (interval merge)
arm交叉编译