题目链接:2612. 最少翻转操作数
方法:BFS + AVLTree
解题思路
先不考虑被 \(ban\) 的位置:
- 假设当前 \(1\) 的位置在下标 \(i\) 上,那么将其按照包含 \(i\) 且长度为 \(k\) 的数组反转一次所能得到的对应下标的可能结果是一个从 \(i - k + 1\) 起始到 \(i + k - 1\) 结束的公差为 \(2\) 的等差数列。
- 由于数组下标范围为 \([0, n - 1]\),因此为了防止反转后的下标越界,应该确定反转后的下标最小值和最大值(也就是最左、右端点),观察可以发现:
- 最左端点的选取:
- 要么是反转数组 \([0, k - 1]\) \(=>\) 新下标:\(k - i - 1\);
- 要是是反转数组 \([i - k + 1 ,i]\) \(=>\) 新下标:\(i - k + 1\);
- 最左端点应该选择两者之间的最大值,防止越界。
- 最右端点的选取:
- 要么是反转数组 \([n - k, n - 1]\) \(=>\) 新下标:\(2n - k - i - 1\);
- 要么是反转数组 \([i, i + k - 1]\) \(=>\) 新下标:\(i + k - 1\);
- 最右端点应该选择两者之间的最小值,防止越界。
- 本题要求:最少翻转操作数,考虑 \(BFS\) 求权重为 \(1\) 的"最短路"。从上述可知,反转一次到新的位置之后,再在当前新的位置按照上述规律进行反转,一层层向下一个位置遍历,直到遍历所有位置,同时要考虑被 \(ban\) 的位置不能使用,其中的层数就是最小的反转数,因此可以使用 \(BFS\)。
- BFS
- 初始化队列,将 \(1\) 的起始位置 \(p\) 入队,初始化当前层数 \(level = 0\),并将该位置的答案初始化为 \(level\);
- 当队列不为空时,取出队首元素,然后遍历其下一个能到达的除被 \(ban\) 的且未到过的所有位置,并入队,将该位置的答案置为 \(level + 1\);
- 重复上述操作直到队列为空;
- 但这样写法会
TLE
,因为这样的时间复杂度为 \(O(nk)\),入队的个数为 \(O(n)\),每个队内的元素遍历其下一个位置为 \(O(k)\),因为访问过的下标一直存在,只要存在就会查看其是否遍历,若将遍历过的下标删除,则没有该冗余。
- 平衡树优化 \((set)\)
- 维护下标,删除已经访问过的;
- 技巧:维护两个平衡树,一个存放奇数下标,一个存放偶数下标,因为序列的公差为 \(2\)。
代码
class Solution {
public:
vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
unordered_set<int> ban{banned.begin(), banned.end()};
set<int> sets[2];
for (int i = 0; i < n; i ++ ) {
if (i != p && !ban.count(i)) {
sets[i % 2].insert(i);
}
}
sets[0].insert(n); // 哨兵
sets[1].insert(n);
vector<int> ans(n, -1);
queue<int> q;
q.push(p);
ans[p] = 0;
while (!q.empty()) {
int i = q.front(), level = ans[i];
q.pop();
int mn = max(i - k + 1, k - i - 1);
int mx = min(i + k - 1, 2 * n - k - i - 1);
auto &s = sets[mn % 2];
// 找到第一个mn的位置,哨兵防止it为空
for (auto it = s.lower_bound(mn); *it <= mx; it = s.erase(it)) {
ans[*it] = level + 1;
q.push(*it);
}
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(nlogn)\);
空间复杂度:\(O(n)\)。