[LeetCode] 1370. Increasing Decreasing String
wengle 人气:0
### 1. 原题链接：https://leetcode.com/problems/increasing-decreasing-string/
### 2. 解题思路
1. 直观的想法是：用有序map\记录字母和字母出现的次数
2. 按照题目描述的方式，先顺序遍历map，再反序遍历map，直到map中的所有字母出现次数都为0为止
### 3. 算法
1. 遍历字符串s，通过有序map\记录字母和字母出现的次数
2. 设置标志forward表示当前是正向遍历map，还是反向遍历map
3. 遍历map的过程中，如果字母X的出现次数不为0，则将该字母加入结果字符串中，并将该字母的出现次数减一；否则，字母X的出现次数是0，表示该字母已经都被遍历了，并且已经都加入到结果字符串中
4. 如果在某一次遍历完map后，所有的字母出现次数都是0，表示整个字符串已经被遍历完了，此时可以退出循环，返回结果字符串（PS：其实退出条件也可以是：当结果字符串的长度和原字符串长度相同时，可以退出循环）
### 4. 实现
```C++
class Solution {
public:
string sortString(string s) {
map 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::iterator begin = table.begin();
map::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::reverse_iterator begin = table.rbegin();
map::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;
}
};
```
```C++
//巧妙解法
//该解法有个限制条件：s中出现的字符排序规则必须跟map对这些字符的排序规则保持一致
class Solution {
public:
string sortString(string s) {
string ans;
map 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;
}
};
```
加载全部内容