class Solution {
public:
string orderlyQueue(string s, int k) {
}
};
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
只由小写字母组成。原站题解
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; } };