[LeetCode] 1370. Increasing Decreasing String 上升下降字符串

You are given a string s. Reorder the string using the following algorithm:

Remove the smallest character from s and append it to the result.
Remove the smallest character from s that is greater than the last appended character, and append it to the result.
Repeat step 2 until no more characters can be removed.
Remove the largest character from s and append it to the result.
Remove the largest character from s that is smaller than the last appended character, and append it to the result.
Repeat step 5 until no more characters can be removed.
Repeat steps 1 through 6 until all characters from s have been removed.

If the smallest or largest character appears more than once, you may choose any occurrence to append to the result.

Return the resulting string after reordering s using this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters.

這道題說是給了一個字符串s，讓采取下面一系列的措施：

刪除s中最小的字符并將其附加到結(jié)果中。
刪除比上次附加的字符大的s中最小的字符，并將其附加到結(jié)果中。
重復步驟2，直到不能再刪除任何字符。
刪除s中最大的字符并將其附加到結(jié)果中。
刪除比上次附加的字符小的s中最大的字符，并將其附加到結(jié)果中。
重復步驟5，直到不能再刪除任何字符。
重復步驟1到6，直到所有字符從s中被刪除。

那么實際上就是找每個狀態(tài)下s中的最大或最小的字符以及其個數(shù)，所以就需要統(tǒng)計每個字符出現(xiàn)的次數(shù)，而且最好還要能很方便的知道最大最小的字符是什么。一般來說，如果只想統(tǒng)計每個字符出現(xiàn)的個數(shù)，會用 HashMap 來做，但是這道題明確說了需要知道最大和最小的字符，則就應該用 TreeMap 或者數(shù)組來做。這里用數(shù)組來做更方便一點，因為題目中限定了字符串s中只有 26 個小寫字母，則用一個大小為 26 的數(shù)組來統(tǒng)計每個字母的出現(xiàn)次數(shù)即可，而遍歷的方向就可以決定取最大或最小的字符。由于總體步驟是要循環(huán)執(zhí)行的，所以最外層要套一個 while 循環(huán)，判定條件就是結(jié)果 res 的長度不等于原字符串s。

然后從頭開始遍歷統(tǒng)計字符個數(shù)的數(shù)組 charCnt，若某個字符個數(shù)自減1之后仍大于等于0，則說明該字符存在，并且是當前最大的字符，則將其加入結(jié)果 res 中，這樣保證了每種字符只會取一個，這樣一圈遍歷下來步驟1至3就完成了。同理，從末尾往前遍歷，若某個字符個數(shù)自減1之后仍大于等于0，則說明該字符存在，并且是當前最小的字符，則將其加入結(jié)果 res 中，這樣保證了每種字符只會取一個，這樣一圈遍歷下來步驟4至6就完成了。同時最外層的循環(huán)保證了步驟1至6可以重復執(zhí)行，最終循環(huán)退出后就得到符合要求的結(jié)果 res，參見代碼如下：

class Solution {
public:
    string sortString(string s) {
        string res;
        vector<int> charCnt(26);
        for (char c : s) {
            ++charCnt[c - 'a'];
        }
        while (s.size() != res.size()) {
            for (int i = 0; i < 26; ++i) {
                if (--charCnt[i] >= 0) {
                    res += (i + 'a');
                }
            }
            for (int i = 25; i >= 0; --i) {
                if (--charCnt[i] >= 0) {
                    res += (i + 'a');
                }
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1370

參考資料：

https://leetcode.com/problems/increasing-decreasing-string

https://leetcode.com/problems/increasing-decreasing-string/solutions/533002/c-counts/

LeetCode All in One 題目講解匯總(持續(xù)更新中...)