LeetCode 题解工作台
最少翻转操作数
给定一个整数 n 和一个整数 p ，它们表示一个长度为 n 且除了下标为 p 处是 1 以外，其他所有数都是 0 的数组 arr 。同时给定一个整数数组 banned ，它包含数组中的一些限制位置。在 arr 上进行下列操作： 如果单个 1 不在 banned 中的位置上，反转大小为 k 的 子数组…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
我们注意到，对于一个子数组区间 中的任意一个下标 ，翻转后的下标 $j = l + r - i$。 如果子数组向右移动一个位置，那么 $j = l + 1 + r + 1 - i = l + r - i + 2$，即 会增加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给定一个整数 n 和一个整数 p，它们表示一个长度为 n 且除了下标为 p 处是 1 以外，其他所有数都是 0 的数组 arr。同时给定一个整数数组 banned ，它包含数组中的一些限制位置。在 arr 上进行下列操作：
- 如果单个 1 不在
banned中的位置上，反转大小为k的 子数组。
返回一个包含 n 个结果的整数数组 answer，其中第 i 个结果是将 1 放到位置 i 处所需的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。
示例 1：
输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：
- 一开始 1 位于位置 0，因此我们需要在位置 0 上的操作数是 0。
- 我们不能将 1 放置在被禁止的位置上，所以位置 1 和 2 的答案是 -1。
- 执行大小为 4 的操作以反转整个数组。
- 在一次操作后，1 位于位置 3，因此位置 3 的答案是 1。
示例 2：
输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：
- 一开始 1 位于位置 0，因此我们需要在位置 0 上的操作数是 0。
- 我们不能在
[0, 2]的子数组位置上执行操作，因为位置 2 在 banned 中。 - 由于 1 不能够放置在位置 2 上，使用更多操作将 1 放置在其它位置上是不可能的。
示例 3：
输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：
执行大小为 1 的操作，且 1 永远不会改变位置。
提示：
1 <= n <= 1050 <= p <= n - 10 <= banned.length <= n - 10 <= banned[i] <= n - 11 <= k <= nbanned[i] != pbanned中的值 互不相同 。
解题思路
方法一：有序集合 + BFS
我们注意到，对于一个子数组区间 中的任意一个下标 ，翻转后的下标 。
如果子数组向右移动一个位置，那么 ，即 会增加 。
同理，如果子数组向左移动一个位置，那么 ，即 会减少 。
因此，对于一个特定的下标 ，其翻转后的所有位置构成了一个公差为 的等差数列，也即是说，翻转后的所有下标，奇偶性都是相同的。
接下来，我们考虑下标 翻转后的位置 的取值范围。
- 如果不考虑边界的情况，那么 的取值范围为 。
- 如果子数组在最左边，那么 ，因此 翻转后的下标 ，即 ，因此 的左边界 。
- 如果子数组在最右边，那么 ，因此 翻转后的下标 ，即 ，因此 的右边界 。
我们用两个有序集合分别存储所有待搜索的奇数下标和偶数下标，这里需要排除数组 中的下标，以及下标 。
接下来，我们使用 BFS 搜索，每次搜索当前下标 所有翻转后的下标 ，即 ，更新下标 的答案，并将下标 加入到待搜索的队列中，同时将下标 从对应的有序集合中移除。
当搜索结束时，即可得到所有下标的答案。
时间复杂度 ，空间复杂度 。其中 题目中给定的数组长度。
class Solution:
def minReverseOperations(
self, n: int, p: int, banned: List[int], k: int
) -> List[int]:
ans = [-1] * n
ans[p] = 0
ts = [SortedSet() for _ in range(2)]
for i in range(n):
ts[i % 2].add(i)
ts[p % 2].remove(p)
for i in banned:
ts[i % 2].remove(i)
ts[0].add(n)
ts[1].add(n)
q = deque([p])
while q:
i = q.popleft()
mi = max(i - k + 1, k - i - 1)
mx = min(i + k - 1, n * 2 - k - i - 1)
s = ts[mi % 2]
j = s.bisect_left(mi)
while s[j] <= mx:
q.append(s[j])
ans[s[j]] = ans[i] + 1
s.remove(s[j])
j = s.bisect_left(mi)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding BFS and how it guarantees minimum operations is key.
- question_mark
Watch for how the candidate handles blocked positions and restrictions.
- question_mark
Evaluate if the candidate can optimize the search process and handle edge cases efficiently.
常见陷阱
外企场景- error
Forgetting to handle banned positions correctly, leading to invalid solutions.
- error
Assuming the BFS will always find a valid path, without considering isolated or blocked positions.
- error
Not handling edge cases, such as when the starting position is the only valid position.
进阶变体
外企场景- arrow_right_alt
Change the operation size `k` to affect how the 1 can move, adding more complexity to the problem.
- arrow_right_alt
Introduce multiple 1s in the array and calculate the minimum operations to bring all 1s to every position.
- arrow_right_alt
Consider dynamic constraints where the banned positions can change during the operation sequence.