1. 原題鏈接：https://leetcode.com/problems/increasing-decreasing-string/
2. 解題思路
- 直觀的想法是：用有序map<char, int>記錄字母和字母出現的次數
- 按照題目描述的方式，先順序遍歷map，再反序遍歷map，直到map中的所有字母出現次數都為0為止
3. 演算法
- 遍歷字串s，通過有序map<char, int>記錄字母和字母出現的次數
- 設定標志forward表示當前是正向遍歷map，還是反向遍歷map
- 遍歷map的程序中，如果字母X的出現次數不為0，則將該字母加入結果字串中，并將該字母的出現次數減一；否則，字母X的出現次數是0，表示該字母已經都被遍歷了，并且已經都加入到結果字串中
- 如果在某一次遍歷完map后，所有的字母出現次數都是0，表示整個字串已經被遍歷完了，此時可以退出回圈，回傳結果字串（PS：其實退出條件也可以是：當結果字串的長度和原字串長度相同時，可以退出回圈）
4. 實作
class Solution {
public:
string sortString(string s) {
map<char, int> table;
for(auto c : s){
table[c] = table[c] + 1;
}
string res;
bool forward = 1;
while(table.size() != 0){
bool finish = true;
if(forward){
map<char, int>::iterator begin = table.begin();
map<char, int>::iterator end = table.end();
forward = 0;
for(; begin != end; begin++){
if(begin->second == 0){
continue;
}
finish = false;
res += begin->first;
begin->second = begin->second - 1;
}
}else{
map<char, int>::reverse_iterator begin = table.rbegin();
map<char, int>::reverse_iterator end = table.rend();
forward = 1;
for(; begin != end; begin++){
if(begin->second == 0){
continue;
}
finish = false;
res += begin->first;
begin->second = begin->second - 1;
}
}
if(finish)
break;
//if(res.size() == s.size()) //另一種退出條件
// break;
}
return res;
}
};
//巧妙解法
//該解法有個限制條件：s中出現的字符排序規則必須跟map對這些字符的排序規則保持一致
class Solution {
public:
string sortString(string s) {
string ans;
map<char,int > cnt;
for(auto item:s)cnt[item]++;
while(1){
for(char ch='a';ch<='z';++ch)
if(cnt[ch]!=0)cnt[ch]--,ans.push_back(ch);
for(char ch='z';ch>='a';--ch)
if(cnt[ch]!=0)cnt[ch]--,ans.push_back(ch);
if(ans.size()==s.size())break;
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/77838.html
標籤：其他
上一篇：高精度“-”演算法
下一篇：鏈堆疊操作