ORID42

今天终于突破了100题大关，自己也成为了战斗力100的渣渣。

[1370] Increasing Decreasing String 解题报告

用什么算法

dp
这道题给出了步骤，你实际上要做的就是实现他想要的排序就可以了。
他要先从小到大把s这个string里面的字母排序（第二个字母要比第一个字母大）
然后再反过来
比如"abcabc", 按照题目要求排过序之后应该是"abccba"。
这道题的要点就在记住每个字母的出现频率，然后直接按照从小到大取就可以了
比如"abcabc", a出现了两次，你开一个int[26]的数组，0代表a，25代表z，然后每个数组记录的就是这个字母出现了多少次，然后从小到大取一个。再从大到小取一个（就是按照题目要求做）
就完成了！

代码实现

public String sortString(String s) {
        char[] ss = s.toCharArray();
        int n = ss.length, min = Integer.MAX_VALUE;
        StringBuilder sb = new StringBuilder(n);
        int[] freq = new int[26];
        for (int i = 0; i < n; i++) {
            freq[ss[i] - 'a']++; //important of how to count frequency from given string 
        }
        //proceed to the question 
        int count = 0;
        while (count < n) {
            //increasing order
            for (int i = 0; i < 26; i++) {
                if (freq[i] > 0) {
                    sb.append((char) (i + 'a'));
                    freq[i]--;
                    count++;
                } else {
                    continue;
                }                
            }
            //decreasing order
            for (int i = 25; i >= 0; i--) {
                if (freq[i] > 0) {
                    sb.append((char) (i + 'a'));
                    freq[i]--;
                    count++;
                } else {
                    continue;
                }
            }
        }
        return sb.toString();
    }

注意这里

       for (int i = 0; i < n; i++) {
            freq[ss[i] - 'a']++; //important of how to count frequency from given string 
        }

才是关键，我也标注了。因为从0到s.length这个for loop是在记录每个字母出现了多少次（frequency），然后之后的while loop就是在实现题目要求。每次从小到大，只要这个字母当前计数大于0（也就是还能提取出来），那就放到stringbuilder里面去，最后return stringbuilder就好了。