题目描述
给你一个整数 n
和一个在范围 [0, n - 1]
以内的整数 p
,它们表示一个长度为 n
且下标从 0 开始的数组 arr
,数组中除了下标为 p
处是 1
以外,其他所有数都是 0
。
同时给你一个整数数组 banned
,它包含数组中的一些位置。banned
中第 i
个位置表示 arr[banned[i]] = 0
,题目保证 banned[i] != p
。
你可以对 arr
进行 若干次 操作。一次操作中,你选择大小为 k
的一个 子数组,并将它 翻转。在任何一次翻转操作后,你都需要确保 arr
中唯一的 1
不会到达任何 banned
中的位置。换句话说,arr[banned[i]]
始终 保持 0
。
请你返回一个数组 ans
,对于 [0, n - 1]
之间的任意下标 i
,ans[i]
是将 1
放到位置 i
处的 最少 翻转操作次数,如果无法放到位置 i
处,此数为 -1
。
- 子数组 指的是一个数组里一段连续 非空 的元素序列。
- 对于所有的
i
,ans[i]
相互之间独立计算。 - 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序。
样例
输入:n = 4, p = 0, banned = [1,2], k = 4
输出:[0,-1,-1,1]
解释:k = 4,所以只有一种可行的翻转操作,就是将整个数组翻转。
一开始 1 在位置 0 处,所以将它翻转到位置 0 处需要的操作数为 0。
我们不能将 1 翻转到 banned 中的位置,所以位置 1 和 2 处的答案都是 -1。
通过一次翻转操作,可以将 1 放到位置 3 处,所以位置 3 的答案是 1。
输入:n = 5, p = 0, banned = [2,4], k = 3
输出:[0,-1,-1,-1,-1]
解释:这个例子中 1 一开始在位置 0 处,所以此下标的答案为 0。
翻转的子数组长度为 k = 3,1 此时在位置 0 处,所以我们可以翻转子数组 [0, 2],
但翻转后的下标 2 在 banned 中,所以不能执行此操作。
由于 1 没法离开位置 0,所以其他位置的答案都是 -1。
输入:n = 4, p = 2, banned = [0,1,3], k = 1
输出:[-1,-1,0,-1]
解释:这个例子中,我们只能对长度为 1 的子数组执行翻转操作,所以 1 无法离开初始位置。
限制
1 <= n <= 10^5
0 <= p <= n - 1
0 <= banned.length <= n - 1
0 <= banned[i] <= n - 1
1 <= k <= n
banned[i] != p
banned
中的值 互不相同。
算法1
(宽度优先遍历) $O(n \log n)$
- 考虑使用宽度优先遍历,找到从 $p$ 点开始的单源最短路。
- 由于每个点最多会有 $k/2$ 条转移,所以总边数达到了 $O(nk)$ 级别,不能直接暴力。
- 考虑到这是边权为 $1$ 的宽搜,所以每个点只会被访问一次;另外每个点能到达的点的范围是个区间,所以可以维护一个未访问点的有序集,在有序集上二分找到对应的区间,把区间内的点依次入队即可。
- 对于点 $u \in [0, n - 1]$,其可以转移到的点的区间为 $[u + L, u + R]$,其中 $L = \max(-(k - 1), k - 1 - 2u)$,$R = \min(k - 1, 2n - 2u - k - 1)$。
时间复杂度
- 每个点最多进队一次,拓展是在有序集上二分的时间复杂度为 $O(\log n)$,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储队列和有序集。
C++ 代码
class Solution {
public:
vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
vector<bool> banned_map(n, false);
for (int x : banned)
banned_map[x] = true;
set<int> s[2];
for (int i = 0; i < n; i++) {
if (banned_map[i] || i == p)
continue;
s[i & 1].insert(i);
}
vector<int> d(n, -1);
d[p] = 0;
queue<int> q;
q.push(p);
while (!q.empty()) {
int u = q.front();
q.pop();
int l = max(-k + 1, k - 1 - 2 * u);
int r = min(k - 1, -k - 2 * u + 2 * n - 1);
set<int> &t = s[((u ^ k) & 1) ^ 1];
auto it = t.lower_bound(u + l);
vector<int> tbd;
while (it != t.end() && *it <= u + r) {
tbd.push_back(*it);
d[*it] = d[u] + 1;
q.push(*it);
++it;
}
for (int v : tbd)
t.erase(v);
}
return d;
}
};
算法2
(宽度优先遍历,并查集) $O(n)$
- 在算法 1 的基础上,使用并查集替代有序集,即采用并查集的父亲节点,记录下一个有效的位置。
时间复杂度
- 每个点最多进队一次,并查集单次操作的时间复杂度近似为常数,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储队列和并查集的父节点。
C++ 代码
class Solution {
private:
int find(vector<int> &f, int x) {
return f[x] == x ? x : f[x] = find(f, f[x]);
}
public:
vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
vector<bool> banned_map(n, false);
for (int x : banned)
banned_map[x] = true;
vector<vector<int>> nxt(2, vector<int>(n + 2));
for (int i = 0; i <= n + 1; i++) {
if ((i < n && banned_map[i]) || i == p) nxt[i & 1][i] = i + 2;
else nxt[i & 1][i] = i;
}
vector<int> d(n, -1);
d[p] = 0;
queue<int> q;
q.push(p);
while (!q.empty()) {
int u = q.front();
q.pop();
int l = max(-k + 1, k - 1 - 2 * u);
int r = min(k - 1, -k - 2 * u + 2 * n - 1);
vector<int> &f = nxt[((u ^ k) & 1) ^ 1];
for (int i = find(f, u + l); i <= u + r; i = find(f, i + 2)) {
d[i] = d[u] + 1;
q.push(i);
f[i] = find(f, i + 2);
}
}
return d;
}
};