LeetCode1370.递增递减字符串上升下降字符串【Easy】【Python】【排序】问题LeetCode给定一个字符串s。您应该使用以下算法重新排序字符串：从s中选择最小的字符并将其附加到结果中。从s中选择大于最后附加到结果中的字符的最小字符并将其附加到结果中。重复步骤2直到你不能选择更多的字符。从s中选择最大的字符并将其附加到结果。从s中选择比最后附加的字符小的最大字符到结果并将其附加。重复步骤5直到你不能选择更多的字符。重复步骤1到6，直到从s中选择所有字符。在每个步骤中，如果最小或最大字符出现多次，您可以选择任何出现并将其追加到结果中。在对s排序后返回结果字符串这个算法。例1：输入：s="aaaabbbbbcccc"输出："abccbaabccba"解释：在第一次迭代的第1、2、3步之后，result="abc"在第一次迭代的第4、5、6步之后，result="abccba"完成了第一次迭代。现在s="aabbcc"我们回到步骤1在第二次迭代的步骤1、2和3之后，结果="abccbaabc"在第二次迭代的步骤4、5和6之后，结果="abccbaabccba"示例2：输入:s="rat"输出:"art"解释:"rat"这个词在用提到的算法重新排序后变成了"art"。示例3:输入:s="leetcode"输出:"cdelotee"示例4:输入：s="ggggggg"输出："ggggggg"例5：输入：s="spo"输出："ops"约束：1<=s.length<=500s只包含小写英文字母。你有一个字符串s，请按照以下算法重构字符串：从s中选出最小的字符，接在结果字符串的后面，从s的剩余字符中选出最小的字符，且该字符小于最后添加的字符更大，并将其附加到结果字符串。重复第2步，直到不能从s中选择字符。从s中选取最大的字符并将其附加到结果字符串中。从s的剩余字符中选择比最后添加的字符小的最大字符，并将其追加到结果字符串中。重复第5步，直到无法从s中选择字符。重复步骤1到6，直到s中的所有字符都被选中。在任何一步，如果有多个最小或最大字符，您可以选择任何一个并将其添加到结果字符串中。请将s中的字符重新排序后返回结果字符串。示例1：输入：s="aaaabbbbbcccc"输出："abccbaabccba"解释：经过第一轮的第1、2、3步后，结果字符串为result="abc"经过第1轮的第4、5、6步后round，结果字符串为result="abccba"第一轮结束，现在s="aabbcc"，我们在第二轮的1、2、3步之后再次回到步骤1，结果字符串为result="abccbaabc"thesecond经过4、5、6轮后，结果字符串为result="abccbaabccba"例2：输入：s="rat"输出："art"解释："rat"变成了"art"”上述算法重新排序后”例3：输入：s="leetcode"输出："cdelotee"例4：输入：s="ggggggg"输出："ggggggg"例5：输入：s="spo"输出："ops"提示：1<=s.length<=500s只包含小写英文字母，思路排序对字符串进行排序，然后递增一次，递减一次，逐渐加到res中，直到s为空。空间复杂度：O(len(s))Python3codeclass解决方案：defsortString(self,s:str)->str:ifnots:return''s=list(s)res=[]whiles:#increasing:increasingtemp_list=list(set(s))#set可以去重temp_list.sort(key=lambdac:ord(c))#ord():将ASCII字符转换成对应的数字foriintemp_list:res.append(i)s.remove(i)#decreasing:递减temp_list=list(set(s))temp_list.sort(key=lambdac:ord(c),reverse=True)foriintemp_list:res.append(i)s.remove(i)return''.join(res)代码地址GitHub链接
