leetcode题目

[keyfall]

排序

1528.重新排列字符串 给你一个字符串 s 和一个 长度相同 的整数数组 indices 。 请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。 返回重新排列后的字符串。

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        #sortindices = indices.sort()
        n = len(indices)
        result = [""] * n
        dicts = dict.fromkeys(indices)
        for i in range(n):
            result[indices[i]] = s[i]
        return "".join(result)

我的做法是把数组和字符串中的每个字母一一对应组成字典，然后通过键升序排列进行字符的位置排列， 官方是新建一个字符串列表，对应位置放入对应的字母（result[indices[i]] = s[i]）

[keyfall]

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

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

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

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

官方答案：

class Solution:
    def sortString(self, s: str) -> str:
        num = [0] * 26
        for ch in s:
            num[ord(ch) - ord('a')] += 1

        ret = list()
        while len(ret) < len(s):
            for i in range(26):
                if num[i]:
                    ret.append(chr(i + ord('a')))
                    num[i] -= 1
            for i in range(25, -1, -1):
                if num[i]:
                    ret.append(chr(i + ord('a')))
                    num[i] -= 1

        return "".join(ret)

先做一个26长度每个值为0的一个数组num， 把传过来的字符串进行分析，遍历字符串，对应的字母就在数组num对应的位置加1 新建一个列表ret用来存储新的字符串，因为每个字母只会被调用一次，所以如果新列表的长度小于字符串长度，那么就一直进行下面的运算，所以使用while len(ret) < len(s) 首先从小到大获取字符串：for循环range(26)，去进行查看数组num中对应的位置是否有值，如果有值，那么新列表ret就加上这个字母 然后从大到小获取字符串，for循环range(25,-1,-1),从25开始-1，直到0，和上面一样，查看数组num中对应的位置是否有值 最后通过"".join(ret)把列表拼接成字符串

[keyfall]

922. 按奇偶排序数组 II 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

输入：[4,2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

我的答案：

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        dnums = []
        jnums = []
        new_nums = []
        for l in nums:
            if l % 2==0:
                dnums.append(l)
            else:
                jnums.append(l)
        x,c = 0,0
        for i in range(len(nums)):
            if i%2 == 0:
                new_nums.append(dnums[x])
                x+=1
            else:
                new_nums.append(jnums[c])
                c+=1
        return new_nums

最快答案：

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        ev, od = 0, 1
        N = len(nums)
        if N == 0:
            return nums
        for ev in range(0, N, 2):
            if nums[ev]%2==1:
                while nums[od]%2==1:
                    od += 2
                nums[ev], nums[od] = nums[od], nums[ev]
                if od==N-1: return nums
        return nums