最少翻转操作数

难度: Hard

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

示例 1：

输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。
我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。
通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。

示例 2：

输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。
翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。
由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。

示例 3：

输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。

提示：

1 <= n <= 10⁵
0 <= p <= n - 1
0 <= banned.length <= n - 1
0 <= banned[i] <= n - 1
1 <= k <= n
banned[i] != p
banned 中的值 互不相同 。

Submission

运行时间: 594 ms

内存: 37.2 MB

from collections import deque
from bisect import bisect_left


class UnionFind:
    def __init__(self, number):
        self.parents = [i for i in range(number)]

    def find(self, index):
        if self.parents[index] != index:
            self.parents[index] = self.find(self.parents[index])
        return self.parents[index]

    def union(self, index1, index2):
        parent1 = self.find(index1)
        parent2 = self.find(index2)
        if parent1 != parent2:
            self.parents[parent1] = parent2


class Solution:
    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
        ans = [-1] * n
        ans[p] = 0
        if k == 1:
            return ans
        used = set(banned)
        used.add(p)
        unused_odd = []
        unused_even = []
        for i in range(n):
            if i in used:
                continue
            if i % 2 == 1:
                unused_odd.append(i)
            else:
                unused_even.append(i)
        unused_odd.append(n)
        unused_even.append(n)
        num_odd, num_even = len(unused_odd), len(unused_even)
        unionfind_odd = UnionFind(num_odd)
        unionfind_even = UnionFind(num_even)
        queue = deque([p])
        while queue:
            cur = queue.popleft()
            left_start = max(0, cur - k + 1)
            right_start = min(n - k, cur)
            left = 2 * left_start - cur + k - 1
            right = 2 * right_start - cur + k - 1
            if left % 2 == 1:
                unused, num, unionfind = unused_odd, num_odd, unionfind_odd
            else:
                unused, num, unionfind = unused_even, num_even, unionfind_even
            index = bisect_left(unused, left)
            while index < num:
                nxt_index = unionfind.find(index)
                nxt = unused[nxt_index]
                if nxt > right:
                    break
                ans[nxt] = ans[cur] + 1
                queue.append(nxt)
                unionfind.union(nxt_index, nxt_index + 1)
                index = nxt_index + 1
        return ans

Explain

本题解采用了广度优先搜索（BFS）的方法，结合并查集和双数组分离的技术来优化搜索过程。首先，初始化答案数组ans所有值为-1，除了起始位置p设置为0，表示从p到p不需要翻转。如果翻转子数组的长度k为1，那么1的位置不会变，直接返回结果。将banned位置和起始位置p标记为已使用，接着将所有未使用位置按奇偶性分开存放。这是为了处理长度为k的子数组翻转后，元素位置的奇偶性只会在两个集合间切换，不会在同一奇偶集合内移动。之后使用两个并查集分别管理奇数和偶数索引的连通性，用于优化寻找下一个可用位置的过程。对于当前队列中的每个位置，计算出可以到达的奇数和偶数索引范围，并利用二分搜索和并查集快速寻找和更新下一步的位置。通过这种方法，确保在每次操作中只考虑有效的和允许的位置，从而达到最少的翻转操作次数。

时间复杂度: O(n log n)

空间复杂度: O(n)

from collections import deque
from bisect import bisect_left


class UnionFind:
    def __init__(self, number):
        self.parents = [i for i in range(number)]  # 初始化父节点指向自身

    def find(self, index):
        if self.parents[index] != index:
            self.parents[index] = self.find(self.parents[index])  # 路径压缩
        return self.parents[index]

    def union(self, index1, index2):
        parent1 = self.find(index1)
        parent2 = self.find(index2)
        if parent1 != parent2:
            self.parents[parent1] = parent2  # 合并集合


class Solution:
    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
        ans = [-1] * n  # 初始化答案数组
        ans[p] = 0  # 起始位置的翻转次数为0
        if k == 1:
            return ans  # 如果翻转长度为1，则不需要任何操作
        used = set(banned)  # 创建禁止使用的位置集合
        used.add(p)  # 加入初始位置
        unused_odd = []  # 未使用的奇数索引集合
        unused_even = []  # 未使用的偶数索引集合
        for i in range(n):
            if i in used:
                continue  # 跳过已使用位置
            if i % 2 == 1:
                unused_odd.append(i)
            else:
                unused_even.append(i)
        unused_odd.append(n)
        unused_even.append(n)
        num_odd, num_even = len(unused_odd), len(unused_even)
        unionfind_odd = UnionFind(num_odd)  # 奇数索引并查集
        unionfind_even = UnionFind(num_even)  # 偶数索引并查集
        queue = deque([p])  # BFS队列初始化
        while queue:
            cur = queue.popleft()
            left_start = max(0, cur - k + 1)
            right_start = min(n - k, cur)
            left = 2 * left_start - cur + k - 1
            right = 2 * right_start - cur + k - 1
            if left % 2 == 1:
                unused, num, unionfind = unused_odd, num_odd, unionfind_odd
            else:
                unused, num, unionfind = unused_even, num_even, unionfind_even
            index = bisect_left(unused, left)
            while index < num:
                nxt_index = unionfind.find(index)
                nxt = unused[nxt_index]
                if nxt > right:
                    break  # 如果超出范围则中断
                ans[nxt] = ans[cur] + 1  # 更新答案数组
                queue.append(nxt)  # 加入下一个位置到队列
                unionfind.union(nxt_index, nxt_index + 1)  # 更新并查集
                index = nxt_index + 1
        return ans  # 返回最终结果

Explore

在算法中，将答案数组中未知位置的值设为-1是一种常见的初始化方式，用以区分那些尚未被访问或处理过的位置。在本题中，-1代表该位置尚未通过翻转达到，这有助于我们在后续的广度优先搜索中快速识别哪些位置是新的，需要被处理的目标位置。使用-1而非其他数字，主要是因为它在此上下文中通常表示“不存在”或“无效”，这使得逻辑判断更为直观和清晰。

在本题解中，所有被标记为banned的位置以及起始位置p在算法初期就已经被加入到一个名为`used`的集合中。在进行位置选择和翻转操作时，算法会跳过这些已使用的位置。具体实现中，通过将这些位置从未使用的奇数和偶数索引集合中排除，确保它们不会被选为翻转的目标。这样，任何翻转操作都不会将1放置在banned的位置上。

在本题中，并查集主要用于管理和优化搜索过程中的位置连通性。通过将奇数和偶数索引分别纳入两个独立的并查集，算法能够快速判断和更新可用位置。在执行翻转操作后，可以通过并查集快速找到下一个可用的最小索引位置，从而避免重复的遍历和检查。并查集通过其路径压缩和合并优化功能，大大提高了查找和合并操作的效率，这对于广度优先搜索中的快速状态更新至关重要。

在本题的翻转操作中，一个子数组的翻转会导致元素的奇偶性发生变化。使用两个并查集分别管理奇数和偶数索引的优势在于，它允许算法更精确地控制和追踪奇偶索引的翻转动态。这种分离管理方式不仅使得翻转后的位置查找更为高效，也简化了连通性的管理，因为每次翻转后，元素位置只会从一个集合跳转到另一个集合，而不会在同一集合内移动。这种设计有效降低了问题的复杂性，提高了操作的效率。