LeetCode 3470. 全排列 IV — Python3 实现解题思路与 Java 版本一致采用 组合计数 DP 逐位构造1. DP 状态dp[o][e][p] 表示剩余 o 个奇数、e 个偶数且上一个数字的奇偶性为 p0偶, 1奇时后续能构成的合法交替排列数。2. 防溢出虽然 Python 的 int 是任意精度但为减少大数运算开销仍将 DP 值上限截断为 k 1。3. 字典序构造从小到大枚举每一位可选数字利用 DP 值判断第 k 个排列所在分支。---完整代码pythonclass Solution:def permute(self, n: int, k: int) - list[int]:odd_count (n 1) // 2 # 1, 3, 5, ... 的个数even_count n // 2 # 2, 4, 6, ... 的个数LIMIT k 1# dp[o][e][p]# 剩余 o 个奇数、e 个偶数上一个数字奇偶性为 p0偶, 1奇dp [[[0] * 2 for _ in range(even_count 1)] for _ in range(odd_count 1)]dp[0][0][0] 1dp[0][0][1] 1for o in range(odd_count 1):for e in range(even_count 1):if o 0 and e 0:continue# 上一个为偶数下一个需要奇数if o 0:dp[o][e][0] min(LIMIT, o * dp[o - 1][e][1])# 上一个为奇数下一个需要偶数if e 0:dp[o][e][1] min(LIMIT, e * dp[o][e - 1][0])# 计算总方案数total 0if odd_count 0:total odd_count * dp[odd_count - 1][even_count][1]if even_count 0:total even_count * dp[odd_count][even_count - 1][0]total min(LIMIT, total)# 有效排列不足 k 个if k total:return []res []used [False] * (n 1)remaining_odd odd_countremaining_even even_countlast_parity -1 # -1 表示还没有放任何数字for _ in range(n):found Falsefor num in range(1, n 1):if used[num]:continueparity num 1 # 1奇数, 0偶数# 必须奇偶交替if last_parity ! -1 and parity last_parity:continue# 计算选择当前数字后剩余位置的方案数if parity 1:count dp[remaining_odd - 1][remaining_even][1]else:count dp[remaining_odd][remaining_even - 1][0]if k count:k - count # 第 k 个不在当前分支跳过else:# 第 k 个在当前分支res.append(num)used[num] Trueif parity 1:remaining_odd - 1last_parity 1else:remaining_even - 1last_parity 0found Truebreakif not found:return []return res---复杂度分析- 时间复杂度O(n²)。DP 填充为 O(n²)构造过程每层最多枚举 n 个数字。- 空间复杂度O(n²)。DP 数组大小约为 (n/2)² × 2。 Python 的 int 支持任意精度因此无需像 Java 那样显式处理 long 溢出但截断到 LIMIT 仍能显著减少大数运算开销。
LeetCode 3470. 全排列 IV — Python3 实现解题思路与 Java 版本一致采用 组合计数 DP 逐位构造1. DP 状态dp[o][e][p] 表示剩余 o 个奇数、e 个偶数且上一个数字的奇偶性为 p0偶, 1奇时后续能构成的合法交替排列数。2. 防溢出虽然 Python 的 int 是任意精度但为减少大数运算开销仍将 DP 值上限截断为 k 1。3. 字典序构造从小到大枚举每一位可选数字利用 DP 值判断第 k 个排列所在分支。---完整代码pythonclass Solution:def permute(self, n: int, k: int) - list[int]:odd_count (n 1) // 2 # 1, 3, 5, ... 的个数even_count n // 2 # 2, 4, 6, ... 的个数LIMIT k 1# dp[o][e][p]# 剩余 o 个奇数、e 个偶数上一个数字奇偶性为 p0偶, 1奇dp [[[0] * 2 for _ in range(even_count 1)] for _ in range(odd_count 1)]dp[0][0][0] 1dp[0][0][1] 1for o in range(odd_count 1):for e in range(even_count 1):if o 0 and e 0:continue# 上一个为偶数下一个需要奇数if o 0:dp[o][e][0] min(LIMIT, o * dp[o - 1][e][1])# 上一个为奇数下一个需要偶数if e 0:dp[o][e][1] min(LIMIT, e * dp[o][e - 1][0])# 计算总方案数total 0if odd_count 0:total odd_count * dp[odd_count - 1][even_count][1]if even_count 0:total even_count * dp[odd_count][even_count - 1][0]total min(LIMIT, total)# 有效排列不足 k 个if k total:return []res []used [False] * (n 1)remaining_odd odd_countremaining_even even_countlast_parity -1 # -1 表示还没有放任何数字for _ in range(n):found Falsefor num in range(1, n 1):if used[num]:continueparity num 1 # 1奇数, 0偶数# 必须奇偶交替if last_parity ! -1 and parity last_parity:continue# 计算选择当前数字后剩余位置的方案数if parity 1:count dp[remaining_odd - 1][remaining_even][1]else:count dp[remaining_odd][remaining_even - 1][0]if k count:k - count # 第 k 个不在当前分支跳过else:# 第 k 个在当前分支res.append(num)used[num] Trueif parity 1:remaining_odd - 1last_parity 1else:remaining_even - 1last_parity 0found Truebreakif not found:return []return res---复杂度分析- 时间复杂度O(n²)。DP 填充为 O(n²)构造过程每层最多枚举 n 个数字。- 空间复杂度O(n²)。DP 数组大小约为 (n/2)² × 2。 Python 的 int 支持任意精度因此无需像 Java 那样显式处理 long 溢出但截断到 LIMIT 仍能显著减少大数运算开销。
 分析与实战)
