关于算法-数据结构:上升下降字符串-LeetCode

112次阅读

共计 1517 个字符，预计需要花费 4 分钟才能阅读完成。

好久没刷 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();}
}