LeetCode-2612 最少翻转操作数

Table of Contents

LeetCode-2612 最少翻转操作数 #

Solution 1 #

很容易想到使用 BFS 来求最少翻转操作数. 对于 $x$ , 如果没有 banned 的限制, 假设使用 $[l, l + k - 1]$ 对其进行反转, 那么有 $0 \leq l \leq x \leq k + k - 1\leq n - 1$ , 翻转后的位置 $y = 2l + k - 1 - x, \max(0, x - k + 1) \leq l \leq \min(x, n - k)$ . $y$ 在奇数、偶数集合中的都是下标连续的. 使用两个平衡树分别维护未被访问的可行解, BFS 每次加入子节点时, 二分找到第一个可以翻转到的下标来辅助寻找后续节点.

代码如下:

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);
        vector<int> q = {p};
        for (int step = 0; !q.empty(); ++step) {
            vector<int> nq;
            for (int i: q) {
                ans[i] = step;
                // 从 mn 到 mx 的所有位置都可以翻转到
                int mn = max(i - k + 1, k - i - 1);
                int mx = min(i + k - 1, n * 2 - k - i - 1);
                auto &s = sets[mn % 2];
                for (auto it = s.lower_bound(mn); *it <= mx; it = s.erase(it))
                    nq.push_back(*it);
            }
            q = move(nq);
        }
        return ans;
    }
};

该代码来自灵神的题解 .