上升下降字符串

• • 1.題目要求
  • 2.題目示例
  • 3.提示
  • 4.解題
  • • 4.1 解題思路
    • 4.2 業(yè)務(wù)代碼
    • 4.3 運行結(jié)果
  • 5.優(yōu)化
  • • 5.1 優(yōu)化思路
    • 5.2 優(yōu)化業(yè)務(wù)代碼
    • 5.3 優(yōu)化結(jié)果
  • 6.總結(jié)

1.題目要求

給你一個字符串 s ，請你根據(jù)下面的算法重新構(gòu)造字符串：

從 s 中選出 最小 的字符，將它 接在 結(jié)果字符串的后面。

從 s 剩余字符中選出 最小 的字符，且該字符比上一個添加的字符大，將它 接在 結(jié)果字符串后面。

重復(fù)步驟 2 ，直到你沒法從 s 中選擇字符。

從 s 中選出 最大 的字符，將它 接在 結(jié)果字符串的后面。

從 s 剩余字符中選出 最大 的字符，且該字符比上一個添加的字符小，將它 接在 結(jié)果字符串后面。

重復(fù)步驟 5 ，直到你沒法從 s 中選擇字符。

重復(fù)步驟 1 到 6 ，直到 s 中所有字符都已經(jīng)被選過。

在任何一步中，如果最小或者最大字符不止一個 ，你可以選擇其中任意一個，并將其添加到結(jié)果字符串。
請你返回將 s 中字符重新排序后的 結(jié)果字符串 。

2.題目示例

• 示例 1：

輸入：s = "aaaabbbbcccc" 輸出："abccbaabccba" 解釋：第一輪的步驟 1，2，3 后，結(jié)果字符串為 result = "abc" 第一輪的步驟 4，5，6 后，結(jié)果字符串為 result = "abccba" 第一輪結(jié)束，現(xiàn)在 s = "aabbcc" ，我們再次回到步驟 1 第二輪的步驟 1，2，3 后，結(jié)果字符串為 result = "abccbaabc" 第二輪的步驟 4，5，6 后，結(jié)果字符串為 result = "abccbaabccba"

• 示例 2：

輸入：s = "rat" 輸出："art" 解釋：單詞 "rat" 在上述算法重排序以后變成 "art"

• 示例 3：

輸入：s = "leetcode" 輸出："cdelotee"

• 示例 4：

輸入：s = "ggggggg" 輸出："ggggggg"

• 示例 5：

輸入：s = "spo" 輸出："ops"

3.提示

• 1 <= s.length <= 500
• s 只包含小寫英文字母。
• Count the frequency of each character.
  計算每個字符的頻率。
• Loop over all character from ‘a(chǎn)’ to ‘z’ and append the character if it exists and decrease frequency by 1. Do the same from ‘z’ to ‘a(chǎn)’.
  循環(huán)遍歷從“a”到“z”的所有字符，如果該字符存在，則追加該字符，并將頻率降低1。從“z”到“a”做同樣的事情。
• Keep repeating until the frequency of all characters is zero.
  一直重復(fù)，直到所有字符的頻率為零。

4.解題

4.1 解題思路

在看完題目過后：

• 提取關(guān)鍵信息

每個字符只能使用一次

每一輪都會在返回字符串后增加一個先升后降的字符串

處理數(shù)據(jù)時，無需關(guān)注數(shù)據(jù)在原字符串中的位置

• 具體思路

創(chuàng)建一個容量為26的int數(shù)組每個數(shù)組的位置對應(yīng)一個字母，其后把傳入的string變?yōu)閏har類型循環(huán)遍歷，得到一個記錄著每個字母有多少個的“映射”int數(shù)組

使用 StringBuilder 來存放拼接的返回字符串

使用while循環(huán)，循環(huán)里包含兩個for循環(huán)，前一個用來拼接升的字符串，后一個用來拼接降的字符串，每使用一個字母就在“映射”數(shù)組對應(yīng)的位置，把計數(shù)減一，直到 StringBuilder 的長度和傳入的字符串的長度相等

4.2 業(yè)務(wù)代碼

class Solution {public String sortString(String s) {int[] num = new int[26];for (int i = 0; i < s.length(); i++) {num[s.charAt(i) - 'a']++;}StringBuffer sb = new StringBuffer();while (sb.length() < s.length()) {for (int i = 0; i < 26; i++) {if (num[i] > 0) {sb.append((char) (i + 'a'));num[i]--;}}for (int i = 25; i >= 0; i--) {if (num[i] > 0) {sb.append((char) (i + 'a'));num[i]--;}}}return sb.toString();} }

4.3 運行結(jié)果

5.優(yōu)化

5.1 優(yōu)化思路

不使用 StringBuilder 而是使用char類型的數(shù)組來存儲會不會有奇效
但是使用數(shù)組來作為存儲媒介的話while的判斷就需要另外的值來表示char已經(jīng)插入了多少數(shù)據(jù)

5.2 優(yōu)化業(yè)務(wù)代碼

class Solution {public String sortString(String s) {int[] num = new int[26];for (int i = 0; i < s.length(); i++) {num[s.charAt(i) - 'a']++;}char[] res = new char[s.length()];int index = 0;while (index < s.length()) {for (int i = 0; i < 26; i++) {if (num[i] != 0) {res[index++] = (char) (i + 'a');num[i]--;}}for (int i = 25; i >= 0; i--) {if (num[i] != 0) {res[index++] = (char) (i + 'a');num[i]--;}}}return new String(res);} }

5.3 優(yōu)化結(jié)果

6.總結(jié)

作為力扣系列的第一天，到最后也只是優(yōu)化了0.2MB的內(nèi)存空間出來，還是有點小傷心的。如果大家有更好的解決方案可以直接在下面留言。

總結(jié)

以上是生活随笔為你收集整理的Java LeetCode每日一题-从易到难带你领略算法的魅力（一）：上升下降字符串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。