LeetCode 题解工作台
构建字典序最大的可行序列
给你一个整数 n ，请你找到满足下面条件的一个序列： 整数 1 在序列中只出现一次。 2 到 n 之间每个整数都恰好出现两次。 对于每个 2 到 n 之间的整数 i ，两个 i 之间出现的距离恰好为 i 。 序列里面两个数 a[i] 和 a[j] 之间的 距离 ，我们定义为它们下标绝对值之差 |j …
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
class Solution: def constructDistancedSequence(self, n: int) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给你一个整数 n ，请你找到满足下面条件的一个序列：
- 整数
1在序列中只出现一次。 2到n之间每个整数都恰好出现两次。- 对于每个
2到n之间的整数i，两个i之间出现的距离恰好为i。
序列里面两个数 a[i] 和 a[j] 之间的 距离 ，我们定义为它们下标绝对值之差 |j - i| 。
请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下，一定存在解。
一个序列 a 被认为比序列 b （两者长度相同）字典序更大的条件是： a 和 b 中第一个不一样的数字处，a 序列的数字比 b 序列的数字大。比方说，[0,1,9,0] 比 [0,1,5,6] 字典序更大，因为第一个不同的位置是第三个数字，且 9 比 5 大。
示例 1：
输入：n = 3 输出：[3,1,2,3,2] 解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。
示例 2：
输入：n = 5 输出：[5,3,1,4,3,5,2,4,2]
提示：
1 <= n <= 20
解题思路
方法一
class Solution:
def constructDistancedSequence(self, n: int) -> List[int]:
def dfs(u):
if u == n * 2:
return True
if path[u]:
return dfs(u + 1)
for i in range(n, 1, -1):
if cnt[i] and u + i < n * 2 and path[u + i] == 0:
cnt[i] = 0
path[u] = path[u + i] = i
if dfs(u + 1):
return True
path[u] = path[u + i] = 0
cnt[i] = 2
if cnt[1]:
cnt[1], path[u] = 0, 1
if dfs(u + 1):
return True
path[u], cnt[1] = 0, 1
return False
path = [0] * (n * 2)
cnt = [2] * (n * 2)
cnt[1] = 1
dfs(1)
return path[1:]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n!) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates understanding of backtracking algorithms and pruning techniques.
- question_mark
Candidate is able to optimize the search space by prioritizing lexicographical order.
- question_mark
Candidate can handle recursive exploration with attention to efficiency.
常见陷阱
外企场景- error
Not pruning invalid sequences early enough, leading to excessive computation.
- error
Failing to optimize the sequence construction for lexicographical order, which may result in incorrect or suboptimal solutions.
- error
Overcomplicating the backtracking process without utilizing pruning to reduce the search space.
进阶变体
外企场景- arrow_right_alt
Use of a heuristic algorithm to improve efficiency when n is large.
- arrow_right_alt
Modification to generate the smallest valid lexicographical sequence.
- arrow_right_alt
Exploring dynamic programming or memoization for optimizing repeated subproblems in backtracking.