上升下降字符串 | LeetCode

做棵大树

发布于 2022-09-27 11:58:43

21100

代码可运行

文章被收录于专栏：代码日志代码日志

运行总次数：0

代码可运行

“好久没刷 LeetCode 了，刚打开页面，啪，每日一题就显示出来了，很快啊。 ”

今天的每日一题是字符串的easy题目，可我还是花了有一二十分钟，许久不刷题手都生了。

题目上升下降字符串

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

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

在任何一步中，如果最小或者最大字符不止一个，你可以选择其中任意一个，并将其添加到结果字符串。

请你返回将 s 中字符重新排序后的结果字符串。

示例一

输入：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"

示例二

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

思路

拿到题目后，首先到我脑海里的有一个 Map ，因为我们需要对输入中不同的字母进行标记（或者说计数）用于判断是否被拼接了；再者是一个先后顺序关系，我们可以从它提到的步骤中发现，选取最大的进行拼接，是在选取最小的进行拼接之后的，那么这个先后顺序我们就可以用于确定我们编写过程中的代码先后顺序。

之后我又想，Map 做映射确实好，但是它有个问题，是无序的；如果我们要找比当前最小大一点的字母则需要先标记当前字母，再去一一比对，这样找一个就要平均遍历 n/2 长度的字符串，时间上很不划算。

鉴于输入的有限性（只有26个英文字母），我们可以使用长度为 26 的数组 chars 来实现 Map 的功效，将 chars[i] 的值用字母出现的次数做填充，同时因为数组的有序性，我们相当于也已经对数组进行了排序操作。

分析完毕，上菜~

代码

class Solution {
    public String sortString(String s) {
        int length = s.length();      // 个人习惯，也可以直接用 s.length()
        StringBuilder sb = new StringBuilder();
        int[] chars = new int[26];      // 用于实现 Map 的作用，并对字符进行排序
        
        for(int i = 0; i < length; i++){
            chars[s.charAt(i)-'a']++;     // 将字母进行映射并统计出现次数
        }

        while(sb.length() != length){     // 循环结束条件
            for(int i = 0; i < 26; i++){    // 寻找比当前字符大的字符，根据数组特性循环即可
                if(chars[i] > 0){
                    sb.append((char)(i+'a'));
                    chars[i]--;
                }
            }

            for(int i = 25; i >= 0; i--){    // 寻找比当前字符小的字符，从尾部循环即可
                if(chars[i] > 0){
                    sb.append((char)(i+'a'));
                    chars[i]--;
                }
            }
        }

        return sb.toString();
    }
}