題目描述
給你一個字串 s ，請你根據下面的演算法重新構造字串：
- 從 s 中選出最小的字符，將它接在結果字串的后面
- 從 s 剩余字符中選出最小的字符，且該字符比上一個添加的字符大，將它接在結果字串后面
- 重復步驟 2 ，直到你沒法從 s 中選擇字符
- 從 s 中選出最大的字符，將它接在結果字串的后面
- 從 s 剩余字符中選出最大的字符，且該字符比上一個添加的字符小，將它接在結果字串后面
- 重復步驟 5 ，直到你沒法從 s 中選擇字符
- 重復步驟 1 到 6 ，直到 s 中所有字符都已經被選過
在任何一步中，如果最小或者最大字符不止一個 ，你可以選擇其中任意一個，并將其添加到結果字串，
請你回傳將 s 中字符重新排序后的結果字串
解題思路
我們可以直接創建一個大小為 26 的桶，記錄每種字符的數量，然后重復若干輪下述操作，直到答案字串的長度與傳入的字串的長度相等，這樣就可以構造出這個字串：
- 正序遍歷桶，從未被選擇的字符中提取出最長的上升字串，將其加入答案，對應桶的計數減一
- 逆序遍歷桶，從未被選擇的字符中提取出最長的下降字串，將其加入答案，對應桶的計數減一
class Solution {
public String sortString(String s) {
int[] nums = new int[26];
for(int i = 0; i < s.length(); i++) {
nums[s.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
while(sb.length() < s.length()) {
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
sb.append((char)(i + 'a'));
nums[i]--;
}
}
for(int i = nums.length - 1; i >= 0; i--) {
if(nums[i] > 0) {
sb.append((char)(i + 'a'));
nums[i]--;
}
}
}
return sb.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/227646.html
標籤：其他