【LeetCode】899. Orderly Queue 解题报告(Python)
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址: https://leetcode.com/problems/orderly-queue/description/
题目描述:
A string S of lowercase letters is given. Then, we may make any number of moves.
In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.
Return the lexicographically smallest string we could have after any number of moves.
Example 1:
Input: S = "cba", K = 1
Output: "acb"
Explanation:
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".
Example 2:
Input: S = "baaca", K = 3
Output: "aaabc"
Explanation:
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".
Note:
- 1 <= K <= S.length <= 1000
- S consists of lowercase letters only.
题目大意
给了一个字符串和一个数字K,每次操作可以把字符串的前K个数字中任意抽取一个放到最后,可以做很多次操作。问,经过很多次操作之后,能构成的字母序最小的字符串是什么?
解题方法
这是一道智商题。
当
K == 1
的时候,没有什么好说的,每次只能把每个开头的字母放到最后去,进行S.length
次操作之后求字母序最小的字符串。这个操作是把字符串进行了旋转。12345 -> 23451 -> 34512 -> 45123 -> 51234
当
K > 1
的时候,我们可以:
1). 把字符串进行旋转(相当于K == 1
)
2). 把字符串除了第一个字符的其余部分进行旋转012345 -> 023451 -> 034512 -> 045123 -> 051234
所以,我们可以使用步骤1里面的操作,把整个字符串最小的数字放到最前面去。然后对字符串后面的部分再旋转使后面部分最小的数字放到前面……以此类推,我们可以得到任何字符串升序排列。
当k > 1的时候,这个过程相当于冒泡排序,所以,我们可以直接排序得到结果。
时间复杂度是O(N ^ 2),空间复杂度是O(N)。
class Solution(object):
def orderlyQueue(self, S, K):
"""
:type S: str
:type K: int
:rtype: str
"""
if K == 1:
res = S
for i in range(len(S)):
res = min(res, S[i:] + S[:i])
else:
res = "".join(sorted(list(S)))
return res
参考资料:
日期
2018 年 10 月 4 日 —— 一个很不容易察觉的小错误,需要总结一下坑了!
最新文章
- [WinForm]WinForm跨线程UI操作常用控件类大全
- CentOS安装gitlab,gerrit,jenkins并配置ci流程
- DGV换行操作
- Sharepoint学习笔记—习题系列--70-576习题解析 -(Q21-Q24)
- [Json.net]忽略不需要的字段
- java, poi, excel
- How Tomcat Works读书笔记之升级架构
- ListView滑动删除效果实现
- swift系统学习第二章
- MyReport:DataGrid的打印和打印预览
- C++: byte 和 int 的相互转化
- 学习使用GitHub(一)--之入门
- Wakelock API详解
- C#山寨版本拨号客户端
- Grunt之watch详解
- 从密码到token, 一个授权的故事 auth2.0
- js中的数值转换
- AI 支持向量机
- CentOS6.8下MySQL数据库版本信息查看
- 无法读取配置节“oracle.manageddataaccess.client”,因为它缺少节声明