Hard
题目描述
给你一个整数 n 和一个整数 p，表示一个长度为 n 的数组 arr，其中除了位置 p 被设置为 1 之外，所有元素都被设置为 0。同时给你一个整数数组 banned，包含被限制的位置。
在 arr 上执行以下操作：
- 如果唯一的 1 不在
banned位置上，则反转大小为k的子数组。
返回一个长度为 n 的整数数组 answer，其中第 i 个结果是将唯一的 1 移动到数组中位置 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 <= 10^50 <= p <= n - 10 <= banned.length <= n - 10 <= banned[i] <= n - 11 <= k <= nbanned[i] != pbanned中的所有值都是唯一的
解题思路
这是一个图论问题，可以用 BFS 求最短路径。关键在于理解反转操作的本质：
核心思想：
- 当前位置为
pos，反转长度为k的子数组后，1 会到达新位置 - 对于位置
pos，可能的反转区间是[l, l+k-1]，其中l的范围需要满足：l <= pos <= l+k-1（pos 在反转区间内）0 <= l <= n-k（区间合法）
- 反转后，位置
pos会变成l + (l+k-1) - pos = 2*l + k - 1 - pos
算法步骤：
- 使用 BFS，从起始位置
p开始 - 对每个当前位置，计算所有可能的目标位置
- 跳过被禁止的位置和已访问的位置
- 使用 set 优化，避免重复计算已访问位置
优化要点：
- 使用两个 set 分别存储奇偶位置的未访问节点，因为反转操作具有奇偶性质
- 每次访问后立即从 set 中移除，避免重复访问
代码实现
class Solution {
public:
vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
vector<int> answer(n, -1);
unordered_set<int> ban(banned.begin(), banned.end());
// 分别存储奇偶位置的未访问节点
set<int> odd, even;
for (int i = 0; i < n; i++) {
if (ban.find(i) == ban.end()) {
if (i % 2 == 0) even.insert(i);
else odd.insert(i);
}
}
queue<int> q;
q.push(p);
answer[p] = 0;
if (p % 2 == 0) even.erase(p);
else odd.erase(p);
while (!q.empty()) {
int pos = q.front();
q.pop();
// 计算可能的反转区间起始位置范围
int minL = max(0, max(pos - k + 1, pos + k - n));
int maxL = min(n - k, pos);
// 计算目标位置范围
int minTarget = 2 * minL + k - 1 - pos;
int maxTarget = 2 * maxL + k - 1 - pos;
// 选择对应的set（奇偶性相同）
set<int>& candidates = (minTarget % 2 == 0) ? even : odd;
// 找到范围内的所有未访问位置
auto it = candidates.lower_bound(minTarget);
vector<int> toRemove;
while (it != candidates.end() && *it <= maxTarget) {
int target = *it;
answer[target] = answer[pos] + 1;
q.push(target);
toRemove.push_back(target);
it++;
}
// 移除已访问的位置
for (int target : toRemove) {
candidates.erase(target);
}
}
return answer;
}
};
class Solution:
def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
answer = [-1] * n
ban = set(banned)
# 分别存储奇偶位置的未访问节点
odd = set()
even = set()
for i in range(n):
if i not in ban:
if i % 2 == 0:
even.add(i)
else:
odd.add(i)
from collections import deque
q = deque([p])
answer[p] = 0
if p % 2 == 0:
even.discard(p)
else:
odd.discard(p)
while q:
pos = q.popleft()
# 计算可能的反转区间起始位置范围
min_l = max(0, max(pos - k + 1, pos + k - n))
max_l = min(n - k, pos)
# 计算目标位置范围
min_target = 2 * min_l + k - 1 - pos
max_target = 2 * max_l + k - 1 - pos
# 选择对应的set（奇偶性相同）
candidates = even if min_target % 2 == 0 else odd
# 找到范围内的所有未访问位置
to_remove = []
for target in list(candidates):
if min_target <= target <= max_target:
answer[target] = answer[pos] + 1
q.append(target)
to_remove.append(target)
# 移除已访问的位置
for target in to_remove:
candidates.discard(target)
return answer
public class Solution {
public int[] MinReverseOperations(int n, int p, int[] banned, int k) {
int[] answer = new int[n];
Array.Fill(answer, -1);
HashSet<int> ban = new HashSet<int>(banned);
// 分别存储奇偶位置的未访问节点
SortedSet<int> odd = new SortedSet<int>();
SortedSet<int> even = new SortedSet<int>();
for (int i = 0; i < n; i++) {
if (!ban.Contains(i)) {
if (i % 2 == 0) even.Add(i);
else odd.Add(i);
}
}
Queue<int> q = new Queue<int>();
q.Enqueue(p);
answer[p] = 0;
if (p % 2 == 0) even.Remove(p);
else odd.Remove(p);
while (q.Count > 0) {
int pos = q.Dequeue();
// 计算可能的反转区间起始位置范围
int minL = Math.Max(0, Math.Max(pos - k + 1, pos + k - n));
int maxL = Math.Min(n - k, pos);
// 计算目标位置范围
int minTarget = 2 * minL + k - 1 - pos;
int maxTarget = 2 * maxL + k - 1 - pos;
// 选择对应的set（奇偶性相同）
SortedSet<int> candidates = (minTarget % 2 == 0) ? even : odd;
// 找到范围内的所有未访问位置
List<int> toRemove = new List<int>();
var view = candidates.GetViewBetween(minTarget, maxTarget);
foreach (int target in view.ToList()) {
answer[target] = answer[pos] + 1;
q.Enqueue(target);
toRemove.Add(target);
}
// 移除已访问的位置
foreach (int target in toRemove) {
candidates.Remove(target);
}
}
return answer;
}
}
var minReverseOperations = function(n, p, banned, k) {
const result = new Array(n).fill(-1);
const bannedSet = new Set(banned);
const queue = [p];
const visited = new Set([p]);
result[p] = 0;
let operations = 0;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const pos = queue.shift();
// Find all possible positions after one operation
for (let start = Math.max(0, pos - k + 1); start <= Math.min(n - k, pos); start++) {
const end = start + k - 1;
const newPos = start + end - pos;
if (newPos >= 0 && newPos < n && !visited.has(newPos) && !bannedSet.has(newPos)) {
visited.add(newPos);
result[newPos] = operations + 1;
queue.push(newPos);
}
}
}
operations++;
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | BFS 访问每个节点一次，set 操作为 O(log n) |
| 空间复杂度 | O(n) | 存储 set 和队列所需的空间 |