LeetCode.2612最少翻转次数C++

题目链接：2612. 最少翻转操作数 - 力扣（LeetCode）

【题目描述】

一个长度为n的数字arr，该数组中除了下标为p的位置为1，其他位置均为0。

一个banned数组，它的内容表示arr数组中的位置，也就是满足所有的arr[banned[i]]=0，其中banned[i]！=p。

返回一个大小为n的数组ans，其中ans[i]表示：数组arr经过多少次翻转可以让i位置出现1。

如果不能实现，则ans[i]=-1。

" 翻转大小为k的子数组，是指将该子数组逆序。"

【思路】

1，首先知道arr数组中p位置的值为1，即arr[p]=1，其余位置为0。目标是翻转大小为k的子数组，使得其他位置也出现1，求每个位置的翻转次数。

那么ans[p]=0，因为p位置不用翻转，本来就是1，所以翻转次数为0。

假设现在i位置的值为1。假设下标i经过一次翻转后的下标为j，这个下标j肯定不是一个特定的下标，它代表翻转后的所有可能的下标。那么我们可以将i和j看成用一条边连接，这条边的边权为1，表示从i位置翻转到j位置的翻转次数。可以理解为求最短路径的过程。

即已经知道了ans[i]的值，arr[i]=1。i位置经过一次翻转后的下标为j，将i和j看成是用一条边连接，这条边的边权为1，代表翻转次数。那么就可以得到ans[j]=asn[i]+1。下次再从j位置开始扩展。

可以看出这是一个BFS的过程。下面的问题是怎么求 i 翻转后的下标 j ？？？

2，对于一个 子数组【L，R】

我们对于这整个区间翻转的话，可以得到：

下标L翻转后的下标为R。

下标L+1翻转后的下标为R-1。

下标L+2翻转后的下标为R-2。

下标L+3翻转后的下标为R-3。

..............

下标R翻转后的下标为L。

可以得出，翻转前后的下标之和始终为L+R。所以于下标i，翻转后的下标j=L+R-i。

再者，对于区间【L，R】，可以左移，L+1，R+1。也可以右移L-1，R-1。

而对于翻转后的下标j=L+R-i而言，就是+2或者-2。

所以翻转后的下标j=L+R-i，其实是一个公差为2的等差数列，要么都是偶数，要么都是奇数。

3，下标i翻转后的下标j的范围。

对于下标i，当它在子数组的最右侧时，可以得到翻转后的下标j=i-k+1，为最小值。

对于下标i，当它在子数组的最左侧时，可以得到翻转后的下标j=i+k-1，为最大值。

还有一些特殊情况：

当i<k-1时，i不可能在子数组的右端点。当i>n-k时，i不可能在子数组的左端点。

例如 对于k=4，长度为4的子数组，右端点最小是k-1=3，当i=0,1,2，i不可能是数组的右端点；左端点最大是n-k，当i>n-k，i不可能在子数组的左端点。

i<k-1的情况，当子数组在整个数组的最左边时，L=0，R=k-1。i翻转后的下标j=L+R-1=k-1-i。小于k-i-1的下标无法翻转得到。

i>n-k的情况，当子数组在整个数组的最右边时，L=n-k，R=n-1。翻转后的下标为j=L+R-i=2*n-k-i-1。大于2*n-k-i-1的下标无法翻转得到。

综上所述：

i翻转后的最小值为max(i-k+1，k-1-i）。

i翻转后的最大值为min(i+k-1，2*n-k-i-1)。

【算法实现】

BFS+有序集合

由于翻转后的下标是一个公差为2的等差数列，要么都是奇数，要么都是偶数。

我们和可以用两个有序集合来维护没有访问过的奇数下标和偶数下标。

这些下标不能在banned数组中出现过，banned数组是限制数组。

还有下标p也不需要出现在集合中，因为刚开始初始化ans[p]=0，已经访问过了。

接下来BFS模拟。

翻转后的下标访问过后，要从有序集合中删除，避免重复访问。

删除时可以直接使用C++标准库中的方法。删除一个迭代器后，会返回下一个迭代器。

不会造成迭代器失效问题。

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> index[2];//维护没有访问过的偶数下标和奇数下标
        for(int i=0;i<n;i++)
        if(i!=p&&!ban.count(i))//p是起点，已经访问过了
        index[i%2].insert(i);
        
        //BFS
        queue<int> q;
        q.push(p);
        vector<int> ans(n,-1);
        ans[p]=0;
        //BFS遍历，边权为1,找最短路径
        while(q.size())
        {
            int i=q.front();
            q.pop();
            //找出可翻转的区间
            int mn=max(i-k+1,k-i-1);
            int mx=min(i+k-1,2*n-k-i-1);
            auto& st=index[mn%2];
            for(auto it=st.lower_bound(mn);it!=st.end()&&*it<=mx;it=st.erase(it))
            {
                ans[*it]=ans[i]+1;
                q.push(*it);
            }
        }
        return ans;
    }
};