排序题 LeetCode题

墨蓝 2022-12-23 15:29 145阅读 0赞

1. [1370. 上升下降字符串][1370.]

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

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

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

**示例 1：**

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

示例2:

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

**提示：**

*  `1 <= s.length <= 500`
 *  `s` 只包含小写英文字母。

解法1:  桶排序

class Solution:
        def sortString(self, s: str) -> str:
            # 使用 桶排序算法 
            # 先弄个桶，用来装 26个字符（只包含小写）出现的次数
            tong = [0]*26
            for item in s:
                tong[ord(item) - ord('a')] += 1
            # 从 小到大，再从大到小
            result = ''
            while sum(tong) != 0:
                for i in range(26):
                    if tong[i]:
                        result += chr(i+ord('a'))
                        tong[i] -= 1
                for i in range(25, -1, -1):
                    if tong[i]:
                        result += chr(i+ord('a'))
                        tong[i] -= 1
            return result

解法2:  for循环

class Solution:
        def sortString(self, s: str) -> str:
            if not s:
                return s
            
            s = list(s)
            s = sorted(s)  # 排序
            result = ""
            # 循环 选出 最小的字符 拼接在后面，不能
            while s:
                min_s = []
                min_ss = ''
                # print(s)
                for item in s:
                    # print(item)
                    if item not in min_s:
                        min_s.append(item)
                        min_ss += item
                for item in min_ss:
                    s.remove(item)
                result += min_ss
                max_s = []
                max_ss = ''
                for item in s[::-1]:
                    if item not in max_s:
                        max_s.append(item)
                        max_ss += item
                for item in max_ss:
                    s.remove(item)
                result += max_ss
    
            return result

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