侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【分类讨论, 模拟, 排序, 字符串】有序队列

GabrielxD
2022-08-03 / 0 评论 / 0 点赞 / 61 阅读 / 548 字 / 正在检测是否收录...

题目

899. 有序队列


给定一个字符串 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 只由小写字母组成。

解题

方法一:字符串 分类讨论 模拟 排序

思路

分类讨论:

  • k = 1 时,由题意循环把字符向后挪 n - 1 次,包括源字符串(s)在内的 n 个字符串(当字符串中有重复字符时可能小于 n)就是字符串 s 可以变换成的所有字符串,找出它们中最小的一个返回即可。
  • k > 1 时,相当于 s 中的字符可以随意排列组合成一个字符串,直接利用 STL 把该字符串排序返回即可。

代码

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k == 1) {
            int n = s.length();
            String min = s;
            for (int i = 1; i < n; i++) {
                s = new StringBuilder(s.substring(1)).append(s.charAt(0)).toString();
                if (s.compareTo(min) < 0) min = s;
            }
            return min;
        } else {
            char[] chs = s.toCharArray();
            Arrays.sort(chs);
            return String.valueOf(chs);
        }
    }
}
class Solution {
public:
    string orderlyQueue(string s, int k) {
        if (k == 1) {
            int n = s.length();
            string mn(s);
            for (int i = 1; i < n; ++i) {
                s = s.substr(1) + s[0];
                if (s < mn) mn = s;
            }
            return mn;
        } else {
            sort(s.begin(), s.end());
            return s;
        }
    }
};
0

评论区