描述

您将在[0，n -1]范围内给您一个整数n和整数P。表示所有位置设置为0的长度n的0个索引阵列arr，除了设置为1。

您还为您提供了一个整数阵列，其中包含来自数组的一些位置。对于禁止的ITH位置，arr [banned [i]] = 0，并禁止[i]！= p。

您可以在ARR上执行多个操作。在操作中，您可以选择具有K大小的子阵列并逆转子阵列。但是，ARR中的1个绝不应涉及被禁止的任何位置。换句话说，在每个操作后，ARR [i] [i]保留0。

返回一个数组ANS，其中每个i从[0，n -1]中的每个i，ans [i]是将1将1带到ARR中的最小反向操作数量，如果不可能，则为i（如果不可能）。

一个子阵列是阵列中元素的连续非空序列。

ans [i]的值是所有我独立的。
数组的反面是一个数组，该数组包含相反顺序的值。

示例1 ：
输入：n = 4，p = 0，禁止= [1,2]，k = 4
输出：[0，-1，-1,1]
说明：在这种情况下，k = 4，因此我们只能执行一个可能的反向操作，这逆转了整个数组。最初，将1放置在位置0，因此位置0所需的操作量为0。我们永远无法将1放在被禁止的位置上，因此位置1和2的答案为-1。最后，通过一个反向操作，我们可以将1带到索引3，因此位置3的答案为1。

示例2 ：
输入：n = 5，p = 0，禁止= [2,4]，k = 3
输出：[0，-1，-1，-1，-1]
说明：在这种情况下，1最初位于位置0，因此该位置的答案为0。我们可以执行尺寸3的反向操作。1当前位于位置0，因此我们需要逆转子阵列[0， 2]为了让它离开该职位，但是逆转该子阵列使位置2具有1，这不应该发生。因此，我们无法将1从位置0移动，从而为所有其他位置-1带来结果。

示例3 ：
输入：n = 4，p = 2，禁止= [0,1,3]，k = 1
输出：[-1，-1,0，-1]
说明：在这种情况下，我们只能执行大小1的反向操作。因此1永远不会改变其位置。

约束：

1 <= n <= 10^5
0 <= p <= n -1
0 <= banned.length <= n -1
0 <= banned [i] <= n -1
1 <= k <= n
禁止[i]！= p
禁止的所有值都是唯一的

方法

该算法遵循广度优先搜索（BFS）的方法，以确定将1个位置带到数组中每个位置所需的最小反操作数量。

为了加快算法的速度，我们将禁止位置标记为-2，而不是使用集合查找。这种优化可降低恒定系数并提高算法的速度，但仍可能导致超过时间限制（tle）误差。

对于每个访问的位置，可能会通过反向操作来达到目标​​位置。为了避免在所有这些潜在位置上迭代的乘法成本，我们更新NextNatode2s数组。该数组最初将其指向2，但我们动态更新它，以指向每个访问位置考虑的所有目标位置。这种优化有助于提高算法的效率并避免不必要的计算。

复杂

时间复杂性：o（n+k）
空间复杂性：o（n）

代码（Swift）

class Solution {
    func minReverseOperations(_ n: Int, _ p: Int, _ banned: [Int], _ k: Int) -> [Int] {
        var out = Array(repeating: -1, count: n)

        for node in banned {
            out[node] = -2
        }

        var nodes = [p]
        var depth = 0
        out[p] = depth
        let step = k - 1
        var nextNode2s = Array(0...(n - 1)).map { $0 + 2 }

        while !nodes.isEmpty {
            depth += 1
            var newNodes = [Int]()

            for node1 in nodes {
                let loReverseStart = max(node1 - step, 0)
                let hiReverseStart = min(node1, n - k)
                let loNode2 = 2 * loReverseStart + k - 1 - node1
                let hiNode2 = 2 * hiReverseStart + k - 1 - node1

                let postHiNode2 = hiNode2 + 2
                var node2 = loNode2

                while node2 <= hiNode2 {
                    let nextNode2 = nextNode2s[node2]
                    nextNode2s[node2] = postHiNode2

                    if node2 >= 0 && node2 < n && out[node2] == -1 {
                        newNodes.append(node2)
                        out[node2] = depth
                    }

                    node2 = nextNode2
                }
            }

            nodes = newNodes
        }

        for i in 0..<n {
            if out[i] == -2 {
                out[i] = -1
            }
        }

        return out
    }
}

来源：Github

联系人
我明确专注于上市时间，而没有优先考虑技术债务。我作为系统建筑师，移动（ios-swift，android-kotlin），前端（react-typescript）和后端（nodejs-.net-.net-php-php-php-php-kafka-sql）参加了系统架构师的预售/RFX活动。 -nosql）。我还通过知识转移到成功交付的知识转移，成立了预售作为CTO的工作。