【题目】
给你一个字符串 s ，请你根据下面的算法重新构造字符串：
从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
重复步骤 2 ，直到你没法从 s 中选择字符。
从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
重复步骤 5 ，直到你没法从 s 中选择字符。
重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串 。
题目链接
思路
用桶计数的方法，设置一个长度为26的列表，列表中每一个位置的值对应了每个字母在字符串中出现的次数，遍历这个数组：
- 第一次从前向后遍历，若值不为0，那么将对应的字母加入最终返回的字符串，并且列表中该位置的值-1
- 第二次从后向前遍历，若值不为0，那么将对应的字母加入最终返回的字符串，并且列表中该位置的值-1
- 当列表中每个值都为0时结束遍历
class Solution(object):def sortString(self, s):""":type s: str:rtype: str"""result = ''numlist = [0]*26flag = 1for key in s:numlist[ord(key)-ord('a')] += 1while flag == 1: flag = 0for i in range(len(numlist)):if numlist[i]>0:result += chr(i + ord('a'))numlist[i] -= 1flag = 1for i in range(len(numlist)-1,-1,-1):if numlist[i]>0:result += chr(i + ord('a'))numlist[i] -= 1return result
知识点
- ord(str)可以返回字母str的asc码，可以用来进行字母之间的加减
- chr(asc)可以将asc码转换为字母