0899：有序队列（2096 分）

2018-09-02 约 467 字预计阅读 1 分钟次阅读

力扣第 100 场周赛第 4 题

题目

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

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

示例 1：

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

示例 2：

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

提示：

1 <= k <= S.length <= 1000
s 只由小写字母组成。

分析

#1

脑筋急转弯
当 k>1 时，可以任意交换两个字符的位置，相当于对 s 排序
k = 1 时，穷举即可

1
2
3
4
5


class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k>1:
            return ''.join(sorted(s))
        return min(s[i:]+s[:i] for i in range(len(s))) 

0 ms

#2

还可以用最小表示法优化 k=1 的时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k>1:
            return ''.join(sorted(s))
        n = len(s)
        i,j,a = 0,1,0
        while i<n and j<n and a<n:
            x,y = s[(i+a)%n],s[(j+a)%n]
            if x==y:
                a += 1
            else:
                i,j = (i+a+1,j) if x>y else (i,j+a+1)
                if i==j:
                    i += 1
                a = 0
        i = min(i, j)
        return s[i:]+s[:i]

0 ms

目录

0899：有序队列（2096 分）

题目

分析

#1

#2

解答