Find Permutation,LeetCode,484

题目描述：

在 LeetCode 上，第 484 题的标题是 “Find Permutation”，中文可以翻译为“寻找排列”。题目描述如下：

给定一个由若干个 “I”（表示上升）和 “D”（表示下降）组成的字符串 s，你需要构造一个长度为 n 的排列 p，其中 n 是字符串 s 的长度加 1。排列 p 需要满足以下条件：

• p 是一个从 1 到 n 的整数排列。
• 对于每个 i（0 ≤ i < n - 1），如果 s[i] 是 “I”，则 p[i] < p[i+1]；如果 s[i] 是 “D”，则 p[i] > p[i+1]。

你需要返回所有符合条件的排列 p。

示例：

输入: "IDID" 输出: [1,4,3,2,5]

解题思路：

1. 初始化： 创建一个长度为 n 的数组 p，初始值为 1 到 n 的顺序排列。
2. 处理 “D” 区间： 遍历字符串 s，找到连续的 “D” 区间，将这些区间内的数字进行逆序排列，以满足下降的要求。
3. 返回结果： 经过处理后的数组 p 即为符合条件的排列。

详细代码实现：

class Solution: def findPermutation(self, s: str) -> List[int]: n = len(s) + 1 p = list(range(1, n + 1)) # 初始化排列

    i = 0
    while i < len(s):
        if s[i] == 'D':
            start = i
            # 找到连续的 'D' 区间
            while i < len(s) and s[i] == 'D':
                i += 1
            # 将区间 [start, i] 的数字逆序
            p[start:i+1] = reversed(p[start:i+1])
        else:
            i += 1

    return p

解释：

1. 初始化排列： p = list(range(1, n + 1)) 创建一个从 1 到 n 的顺序排列。
2. 遍历字符串 s：
   • 如果遇到 “D”，记录起始位置 start，继续遍历直到 “D” 结束的位置 i。
   • 使用 reversed(p[start:i+1]) 将区间 [start, i] 的数字逆序，以满足下降的要求。
3. 返回结果： 经过处理后的 p 即为符合条件的排列。

复杂度分析：

• 时间复杂度： O(n)，其中 n 是字符串 s 的长度。我们需要遍历字符串 s 并对某些区间进行逆序操作，逆序操作的复杂度为 O(k)，k 是区间的长度，总和不超过 n。
• 空间复杂度： O(n)，用于存储排列 p。

这个解法简洁且高效，能够满足题目要求，生成符合条件的排列。希望这个详细的解释对你有所帮助！如果有任何进一步的问题，欢迎继续提问。