>[success] # Leetcode -- 1370上升下降字符串 * 題目描述 給你一個字符串?s?，請你根據下面的算法重新構造字符串： 從 s?中選出 最小?的字符，將它 接在?結果字符串的后面。 從 s?剩余字符中選出?最小?的字符，且該字符比上一個添加的字符大，將它 接在?結果字符串后面。 重復步驟 2 ，直到你沒法從 s?中選擇字符。 從 s?中選出 最大?的字符，將它 接在?結果字符串的后面。 從 s?剩余字符中選出?最大?的字符，且該字符比上一個添加的字符小，將它 接在?結果字符串后面。 重復步驟 5?，直到你沒法從 s?中選擇字符。 重復步驟 1 到 6 ，直到 s?中所有字符都已經被選過。 在任何一步中，如果最小或者最大字符不止一個?，你可以選擇其中任意一個，并將其添加到結果字符串。 請你返回將?s?中字符重新排序后的 結果字符串 。 ? * 示例 1： ~~~ 輸入：s = "aaaabbbbcccc" 輸出："abccbaabccba" 解釋：第一輪的步驟 1，2，3 后，結果字符串為 result = "abc" 第一輪的步驟 4，5，6 后，結果字符串為 result = "abccba" 第一輪結束，現在 s = "aabbcc" ，我們再次回到步驟 1 第二輪的步驟 1，2，3 后，結果字符串為 result = "abccbaabc" 第二輪的步驟 4，5，6 后，結果字符串為 result = "abccbaabccba" ~~~ * 示例 2： ~~~ 輸入：s = "rat" 輸出："art" 解釋：單詞 "rat" 在上述算法重排序以后變成 "art" ~~~ * 示例 3： ~~~ 輸入：s = "leetcode" 輸出："cdelotee" ~~~ * 示例 4： ~~~ 輸入：s = "ggggggg" 輸出："ggggggg" ~~~ * 示例 5： ~~~ 輸入：s = "spo" 輸出："ops" ~~~ * 提示： ~~~ 1 <= s.length <= 500 s?只包含小寫英文字母。 ~~~ 來源：力扣（LeetCode） 鏈接：https://leetcode.cn/problems/increasing-decreasing-string 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 >[danger] ##### 簡單概括 先將字符串中不重復的每一項**先升序排列**在**降序排列依**次交替組成新字符串 >[info] ## 題解 題目中提到字符串是由**小寫字母**組成，因此可以利用**ascii** 映射數組腳標思路來做字母存儲，因為在數組中存儲后，每個字母此時已經是按照升序排序好，因此只要**正序倒序** 反復從數組取值即可   >[danger] ##### js 解題 ~~~ var sortString = function (s) { // 將字符串根據ascii 映射放入對應數組腳標中 const array = new Array(26).fill(0) const ascii_a = 'a'.charCodeAt(0) for (let char of s) { // 轉換ascii 碼 const idx = char.charCodeAt(0) array[idx - ascii_a]++ } // 按升降序依次正反數組取值 let str = '' // 一直循環直到 新生成的字符串長度等于原來字符串長度 while (str.length < s.length) { // 升序排列 for (let i = 0; i < 26; i++) { if (array[i]) { str += String.fromCharCode(i + ascii_a) array[i]-- } } // 降序排列 for (let i = 25; i >= 0; i--) { if (array[i]) { str += String.fromCharCode(i + ascii_a) array[i]-- } } } return str } ~~~ >[danger] ##### java 解題 ~~~ public class Solution { public String sortString(String s) { // 創建一個26長度數組 byte[] asciiLs = new byte[26]; char asciiLs_a = 'a'; // 將字符依次保存 for(int c:s.toCharArray()){ int idx = c-asciiLs_a; asciiLs[idx]++; } // 記錄新的字符串 這種拼接比較慢可以使用數組List ans = new ArrayList<>(); String res = ""; while(res.length()<s.length()){ // 升序記錄 for(int i=0;i<26;i++){ if(asciiLs[i]!=0){ // 找到就去掉一次 asciiLs[i]--; res+=String.valueOf((char)(i+asciiLs_a)); } } // 降序 for(int i=25;i>=0;i--){ if(asciiLs[i]!=0){ // 找到就去掉一次 asciiLs[i]--; res+=String.valueOf((char)(i+asciiLs_a)); } } } return res; } } ~~~ >[info] ## 看到一個擴展思路 直接` while (--end >= 0)` 這種將計算放到**while** 條件中 ~~~ /** * @param {string} s * @return {string} */ var sortString = function(s) { // 計數法 // a-z => 97-122 // index是字母-97，值是出現的次數 let arr = Array(26).fill(0) const base = 'a'.charCodeAt() for (const char of s) { // 0-25 arr[char.charCodeAt() - base] ++ } let ans = '' while (ans.length < s.length) { let = start = -1, end = 26 while (++start < 26) { if (arr[start] !== 0) { ans += String.fromCharCode(start + base) arr[start] -- } } while (--end >= 0) { if (arr[end] !== 0) { ans += String.fromCharCode(end + base) arr[end] -- } } } return ans; }; ~~~