题目链接:https://leetcode-cn.com/problems/increasing-decreasing-string/
题意:给你一个包含26个字母的字符串让你构造一个新的字符串,规则是先提出最小的字符(这些字符间不能相同)放进新字符串,再从剩下的字符里提出最大的字符(也不能相同)放进新字符串。不断执行这个过程直到所有字符都放进新字符串。
分析:一开始想动态的处理,就是每次提出来一个字符后就将原字符串中的该字符删掉重新处理,发现这样不行。。。。最后注意到字符串只包含26个字母,就用一个book数组存一下每个字母出现了多少次,每次执行先从a-z,再从z-a即可。
class Solution { public: string sortString(string s) { string ans=""; int book[26]; memset(book,0,sizeof(book)); for(int i=0;i<s.length();i++){ book[s[i]-'a']++; } int len=s.length(); while(len){ int cnt=0; for(int i=0;i<26;i++){ if(book[i]){ ans+=char(i+'a'); cnt++; book[i]--; } } for(int i=25;i>=0;i--){ if(book[i]){ ans+=char(i+'a'); cnt++; book[i]--; } } len-=cnt; } return ans; } };