题目链接：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)\)。