上升下降字符串.md

上升下降字符串

给你一个字符串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"

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

题解

/**
 * @param {string} s
 * @return {string}
 */
var sortString = function(s) {
    let hashTable = Object.create(null);
    let base = "a".charCodeAt();
    for(let i=0;i<26;++i) hashTable[String.fromCharCode(base+i)] = 0;
    Array.prototype.forEach.call(s, v => hashTable[v]++);
    let target = "";
    while(target.length < s.length){
        for(let i=0;i<26;++i) {
            let key = String.fromCharCode(base+i);
            if(hashTable[key]){
                target += key;
                hashTable[key]--;
            }
        }
        for(let i=25;i>=0;--i) {
            let key = String.fromCharCode(base+i);
            if(hashTable[key]){
                target += key;
                hashTable[key]--;
            }
        }
    }
    return target;
};

思路

题目挺长的，其实就是普通的字符串的操作，并且由于题目中说明了是纯小写字母，也就是总量是确定的，那么就可以不使用排序去统计数量，之后的操作正好也是顺序遍历与逆序遍历即可完成的操作，拼接字符串返回即可。首先定义一个纯对象作为哈希表来记录字符串每种字符的个数，之后定义小写字符的基准数值a的ASCII码值，之后构建一个26个小写字母的循环，将初始哈希表的键对应的值定义为0，循环字符串，将统计相应字母出现的次数，定义目标字符串，如果目标字符串与给定的字符串长度相等则退出循环，之后定义一个26字母正向循环，如果在哈希表中这个字母的值大于0则将其拼接到目标字符串并将该值减1，之后定义一个26字母的逆向循环，按照同样的规则将字符拼接，之后完成循环并返回目标字符串即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/increasing-decreasing-string/