Java 从易到难带你领略算法的魅力：上升下降字符串

程序员文章站 2022-06-19 16:12:31

上升下降字符串1.题目要求2.题目示例3.提示4.解题4.1 解题思路4.2 业务代码4.3 运行结果5.优化5.1 优化思路5.2 优化业务代码5.3 优化结果6.总结1.题目要求给你一个字符串 s ，请你根据下面的算法重新构造字符串：从 s 中选出最小的字符，将它接在结果字符串的后面。从 s 剩余字符中选出最小的字符，且该字符比上一个添加的字符大，将它接在结果字符串后面。重复步骤 2 ，直到你没法从 s 中选择字符。从 s 中选出最大的字符，将它接在结果字符串的后面...

上升下降字符串

1.题目要求

给你一个字符串 s ，请你根据下面的算法重新构造字符串：

从 s 中选出最小的字符，将它接在结果字符串的后面。
从 s 剩余字符中选出最小的字符，且该字符比上一个添加的字符大，将它接在结果字符串后面。
重复步骤 2 ，直到你没法从 s 中选择字符。
从 s 中选出最大的字符，将它接在结果字符串的后面。
从 s 剩余字符中选出最大的字符，且该字符比上一个添加的字符小，将它接在结果字符串后面。
重复步骤 5 ，直到你没法从 s 中选择字符。
重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。

在任何一步中，如果最小或者最大字符不止一个，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。

2.题目示例

示例 1：

输入：s = "aaaabbbbcccc"
输出："abccbaabccba"
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"

示例 2：

输入：s = "rat"
输出："art"
解释：单词 "rat" 在上述算法重排序以后变成 "art"

示例 3：

输入：s = "leetcode"
输出："cdelotee"

示例 4：

输入：s = "ggggggg"
输出："ggggggg"

示例 5：

输入：s = "spo"
输出："ops"

3.提示

1 <= s.length <= 500
s 只包含小写英文字母。
Count the frequency of each character.
计算每个字符的频率。
Loop over all character from ‘a’ to ‘z’ and append the character if it exists and decrease frequency by 1. Do the same from ‘z’ to ‘a’.
循环遍历从“a”到“z”的所有字符，如果该字符存在，则追加该字符，并将频率降低1。从“z”到“a”做同样的事情。
Keep repeating until the frequency of all characters is zero.
一直重复，直到所有字符的频率为零。

4.解题

4.1 解题思路

在看完题目过后：

提取关键信息

每个字符只能使用一次
每一轮都会在返回字符串后增加一个先升后降的字符串
处理数据时，无需关注数据在原字符串中的位置

具体思路

创建一个容量为26的int数组每个数组的位置对应一个字母，其后把传入的string变为char类型循环遍历，得到一个记录着每个字母有多少个的“映射”int数组
使用 StringBuilder 来存放拼接的返回字符串
使用while循环，循环里包含两个for循环，前一个用来拼接升的字符串，后一个用来拼接降的字符串，每使用一个字母就在“映射”数组对应的位置，把计数减一，直到 StringBuilder 的长度和传入的字符串的长度相等

4.2 业务代码

class Solution {
    public String sortString(String s) {
    
        int[] num = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            num[s.charAt(i) - 'a']++;
        }

        StringBuffer sb = new StringBuffer();
        
        while (sb.length() < s.length()) {
            for (int i = 0; i < 26; i++) {
                if (num[i] > 0) {
                    sb.append((char) (i + 'a'));
                    num[i]--;
                }
            }
            for (int i = 25; i >= 0; i--) {
                if (num[i] > 0) {
                    sb.append((char) (i + 'a'));
                    num[i]--;
                }
            }
        }
        return sb.toString();
    }
}

4.3 运行结果

Java 从易到难带你领略算法的魅力：上升下降字符串

5.优化

5.1 优化思路

不使用 StringBuilder 而是使用char类型的数组来存储会不会有奇效
但是使用数组来作为存储媒介的话while的判断就需要另外的值来表示char已经插入了多少数据

5.2 优化业务代码

class Solution {
    public String sortString(String s) {
    
        int[] num = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            num[s.charAt(i) - 'a']++;
        }
        
        char[] res = new char[s.length()];
        int index = 0;
        
        while (index < s.length()) {
            for (int i = 0; i < 26; i++) {
                if (num[i] != 0) {
                    res[index++] = (char) (i + 'a');
                    num[i]--;
                }
            }
            for (int i = 25; i >= 0; i--) {
                if (num[i] != 0) {
                    res[index++] = (char) (i + 'a');
                    num[i]--;
                }
            }
        }
        return new String(res);
    }
}