广西上林县住房城乡建设网站/重庆疫情最新情况

题目在此：力扣

 首先，先祝福自己本周周赛过了三题。耶耶耶耶耶耶！虽然第一题因为脑子不好使想了半天，还WA了一次。衷心祈祷今年力扣能上1800分！！！

这道题，我看了一些通过人数，感觉不像是我等凡人能做出来，所以就退缩了。刚才看了题解，有点明白了，在这里记录一下。

1.i能翻转到哪些位置->i的对称点有哪些？

首先，我们考虑这样一个问题：对于数组中的元素i，从左右两个方向考虑，他最远的对称点的下标是什么？

我们先考虑特殊的情况，也是最简单的情况：i作为区间的左右端点，它的对称点分别是什么？

写到这里，我发现，有个ipad也挺好的，我就可以直接在ipad上画完放到博客里，而不用在纸上画完，再在白板上画了，忧桑~

 是不是很简单呢？现在我们算一下复杂的。

如果我们想反转一个数组，就要确认一下i所在区间中左右两个端点最远的下标，现在我们来讨论一下i能对称的最左边的下标：

然后讨论一下i可以对称到的最右边的下标：

那么现在给定一个下标i，我们可以求出通过i可以翻转得到的所有位置的边界了，也就得到了这些位置和i之间的距离的边界，即：

 求出这个又能怎么样呢？这就意味着对于i，当我们求出l和r这两个边界之后，i+l与i+r之间的值我们都可以翻转得到。

诶，等等，都可以得到吗？我看未必吧。

为什么未必呢，因为i可以与之进行翻转的位置，好像不是完全连续的序列，而是一个公差为2的数列啊？

我们举个例子看看：

 也就是说，i的对称点构成的数列，是一个公差为2的等差数列，则在不同的区间中i的对称点为：

那既然公差为2，说明奇数和奇数在一个数列中，偶数和偶数在一个数列中，我们就把数组中所有的元素按照奇偶性进行划分好了。

2.怎么求出所有可以访问到的点

我们已经求出了对于某个i所有可以反转到的位置，那么这个i我们怎么得到呢？我们回头再看一下题目：ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数。

仔细思考一下，从i可以翻转到很多其他的位置，从其他的位置又可以接着翻转，求的又是最少的操作次数，怎么这么像bfs的经典题型啊！

没错，就是bfs。我们把每个可以翻转得到的下标入队，然后枚举队中的每个元素，再看看他们能够翻转的下标。直到队中没有元素了，此时我们已经对所有可以反转的位置都访问过了。

好了，既然如此，上代码吧。

class Solution {
public:vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {vector<int>res(n, -1);if(k == 1){  //特殊情况res[p] = 0;return res;}unordered_set<int>ban;for(int i = 0; i < banned.size(); i++) ban.insert(banned[i]);//因为i的对称点是按照公差为2进行枚举的，所以我们按照奇偶性把他们放到不同的集合中//用这两个集合枚举我们还没有跳到的位置set<int>st[2];for(int i = 0; i < n; i++){if(i != p && ban.count(i) == 0){st[i % 2].insert(i);}}queue<int>q;q.push(p);res[p] = 0;while(q.size()){int cur = q.front();q.pop();int l = max(k - 1 - 2 * cur, -(k - 1));int r = min(2 * n - 2 * cur - k - 1, k - 1);//判断一下是去奇数还是偶数的集合中查找元素int x = (cur + k - 1) % 2;  //观察一下确定奇偶性，cur肯定对应这个点，那么根据这个点的奇偶性就可以判断这个序列的奇偶性auto it = (st[x].lower_bound(cur + l)); //找到第一个大于等于cur+l的位置（其实就是这个数列的第一个元素），然后开始枚举后面连续的位置（在已经确定好奇偶性的集合，其实就是连续的奇数或者连续的偶数）while(it != st[x].end()){//如果遇到了第一个大于cur+r的位置，就停止枚举if(*it > cur + r) break;//集合中的元素都是没被访问过的，可以从cur一步跳过来//更新答案，从集合中去掉已经访问的元素res[*it] = res[cur] + 1; q.push(*it);it = st[x].erase(it);}}return res;}
};

剩下的小细节也在注释中标明了。今天的题解就写到这里，放上我的参考题解：

力扣 LeetCode 灵神的直播讲解，但是我进的迟了，没听。

力扣 好像也是广受好评的大神的题解，我主要看了这个。

就写到这里吧，说好了下午要看看java，结果看了一下午这道题，好想逃避科研，逃避找工作啊！！！