列表

详情


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”。

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: string orderlyQueue(string s, int k) { } };

javascript 解法, 执行用时: 72 ms, 内存消耗: 42.2 MB, 提交时间: 2023-06-12 16:21:10

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var orderlyQueue = function(s, k) {
    if (k === 1) {
        let ans = s;
        for (let i = 0; i < s.length - 1; ++i) {
            const n = s.length;
            s = s.substring(1, n) + s[0];
            ans = ans < s ? ans : s;
        }
        return ans;
    }
    return [...s].sort().join('');
};

golang 解法, 执行用时: 0 ms, 内存消耗: 3.3 MB, 提交时间: 2023-06-12 16:20:49

func orderlyQueue(s string, k int) string {
    if k == 1 {
        ans := s
        for i := 1; i < len(s); i++ {
            s = s[1:] + s[:1]
            if s < ans {
                ans = s
            }
        }
        return ans
    }
    t := []byte(s)
    sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
    return string(t)
}

java 解法, 执行用时: 2 ms, 内存消耗: 41.4 MB, 提交时间: 2023-06-12 16:20:34

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k == 1) {
            String smallest = s;
            StringBuilder sb = new StringBuilder(s);
            int n = s.length();
            for (int i = 1; i < n; i++) {
                char c = sb.charAt(0);
                sb.deleteCharAt(0);
                sb.append(c);
                if (sb.toString().compareTo(smallest) < 0) {
                    smallest = sb.toString();
                }
            }
            return smallest;
        } else {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            return new String(arr);
        }
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-12 16:20:15

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

cpp 解法, 执行用时: 4 ms, 内存消耗: 6.1 MB, 提交时间: 2023-06-12 16:18:57

/**
 * 当k==1时,相当于将一个环切开,使字典序最小,直接模拟即可,无需多言
 * 当k>=2时,可以证明,经过有限次的操作,一定可以变成升序,所以直接sort返回即可
 **/ 
class Solution {
public:
    string orderlyQueue(string s, int k) {
        if(k==1)//k==1,模拟
        {
            string ans = s;
            for (int i = 1; i <= s.size()-1; ++i)//比较n-1次即可
            {
                s+=s[0];//添加到尾部
                s.erase(0,1);//删除头部
                ans = min(ans,s);
            }
            return ans;
        }
        sort(s.begin(),s.end());//k>=2,排序返回
        return s;
    }
};

上一题