Leetcode 2612

Link:

2612. 最少翻转操作数 - 给定一个整数 n 和一个整数 p，它们表示一个长度为 n 且除了下标为 p 处是 1 以外，其他所有数都是 0 的数组 arr。同时给定一个整数数组 banned ，它包含数组中的一些限制位置。在 arr 上进行下列操作： * 如果单个 1 不在 banned 中的位置上，反转大小为 k 的子数组。返回一个包含 n 个结果的整数数组 answer，其中第 i 个结果是将 1 放到位置 i 处所需的最少翻转操作次数，如果无法放到位置 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 <= 105 * 0 <= p <= n - 1 * 0 <= banned.length <= n - 1 * 0 <= banned[i] <= n - 1 * 1 <= k <= n * banned[i] != p * banned 中的值互不相同。

https://leetcode.cn/problems/minimum-reverse-operations/description/

题目要求

给你一个整数 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] 相互之间独立计算。
将一个数组中的元素翻转指的是将数组中的值变成 相反顺序 。

核心算法和原理

BFS的想法：把数组看成一堆节点，从一个节点开始，可以翻到的节点是一个固定的范围

翻到的那个节点的ans即为所有能翻到这个点的节点中ans最小的 + 1

由于出发点唯一，所以转换成了「从p开始到所有节点的最短路」，路权为1所以直接用BFS解决

判断任意节点i翻转后可达的范围：分别考虑左右边界，画图确定左边界和右边界的可能取值（max(lb1, lb2), min(rb1, rb2)），是一个step = 2的序列

banned数组中的元素看作不可达即可

分别用有序集合和并查集的源码见下

代码

BFS + 有序集合（std::set)


class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        /*
        *   indices: 不包含banned的 未访问到的偶数节点和奇数节点集合
        *   维护两个有序集合的原因：为了排除banned节点 并 使用二分查找优化在set中查找下边界，因为每次翻转后可到达的点要么奇要么偶
        */
        unordered_set<int> banSet{banned.begin(), banned.end()};
        set<int> indices[2];
        for (int i = 0; i < n; i++) {
            if (i != p && !banSet.contains(i)) {
                indices[i & 1 == 1].insert(i);
            }
        }

        // 插入一个不可能访问到的哨兵结点，这样下面set的迭代过程无需判断it != st.end()
        indices[0].insert(n);
        indices[1].insert(n);
        

        vector<int> ans(n, -1);
        ans[p] = 0;

        queue<int> q;
        q.push(p);

        while (!q.empty()) {
            int u = q.front();
            // cout << u << endl;
            q.pop();

            // 考虑越界问题后，算出来的「u节点翻转后可达的左右边界」
            int lb = max(u - k + 1, k - u - 1);
            int rb = min(u + k - 1, 2 * n - k - u - 1);

            auto& st = indices[lb & 1 == 1];

            // essential: it = st.erase(it)可以迭代it至下一个元素
            for (auto it = st.lower_bound(lb); *it <= rb; it = st.erase(it)) {
                ans[*it] = ans[u] + 1;
                q.push(*it);
            }
        }
        return ans;
    }
};

BFS + 并查集


class UnionSet {
private:
    vector<int> fa;

public:
    UnionSet(int n) : fa(n) { iota(fa.begin(), fa.end(), 0); }

    int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    void merge(int from, int to) { fa[find(from)] = fa[to]; }
};

class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        UnionSet indices(n + 2);
        indices.merge(p, p + 2);
        for (int i: banned) {
            // 此之谓 删除操作
            // 之后每次通过find寻找i时，自动找到>= i的 未被删除元素
            indices.merge(i, i + 2);
        }

        vector<int> ans(n, -1);
        ans[p] = 0;

        queue<int> q;
        q.push(p);

        while (!q.empty()) {
            int u = q.front();
            // cout << u << endl;
            q.pop();

            // 考虑越界问题后，算出来的「u节点翻转后可达的左右边界」
            int lb = max(u - k + 1, k - u - 1);
            int rb = min(u + k - 1, 2 * n - k - u - 1);

            for (int j = indices.find(lb); j <= rb; j = indices.find(j + 2)) {
                // 因为[lb, rb]中符合条件的最终都会merge到rb + 2
                indices.merge(j, rb + 2);
                ans[j] = ans[u] + 1;
                q.push(j);
            }
        }
        return ans;
    }
};