2023-09-16：用 go 语言，给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1

作者：福大大架构师每日一题

2023-09-16
北京
本文字数：1822 字
阅读完需：约 6 分钟

2023-09-16：用 go 语言，给你一个整数 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] 相互之间独立计算。

将一个数组中的元素翻转指的是将数组中的值变成相反顺序。

输入：n = 4, p = 0, banned = [1,2], k = 4。

输出：[0,-1,-1,1]。

来自左程云。

答案 2023-09-16：

步骤如下：

1.创建一个奇数集合（oddSet）和一个偶数集合（evenSet）。

2.将所有奇数（除了 p 和 banned 中的位置）添加到 oddSet 中。

3.将所有偶数（除了 p 和 banned 中的位置）添加到 evenSet 中。

4.创建一个长度为 n 的数组 ans，初始化全部为-1。

5.创建一个队列 queue 和两个指针 l 和 r，初始化 r=0。

6.将 p 放入队列 queue 中，r 加 1。

7.初始化 level=0。

8.当 l < r 时，执行以下步骤：

取出队列头部元素 cur。
将 level 赋值给 ans[cur]。
计算 cur 左边和右边的范围，分别为 left 和 right。
根据 left 的奇偶性，选择对应的集合 curSet（如果 left 是偶数，则 curSet 为 evenSet；否则为 oddSet）。
在 curSet 中查找大于等于 left 的最小元素，并将其加入队列 queue 中，r 加 1。
从 curSet 中移除该元素。
重复以上步骤，直到 curSet 中没有大于等于 left 的元素。
l 加 1。

9.更新 level，重复步骤 8 直到 l < r 不成立。

10.返回 ans。

时间复杂度：假设 n 为数组长度，遍历数组需要 O(n)的时间复杂度，每次操作需要在集合中查找和移除元素，集合的查找和移除操作的时间复杂度为 O(log n)。总体时间复杂度为 O(n log n)。

空间复杂度：创建两个集合，集合的空间复杂度为 O(n)，创建一个队列，队列的空间复杂度为 O(n)，创建一个数组，数组的空间复杂度为 O(n)，总体空间复杂度为 O(n)。

go 完整代码如下：

package main
import (  "fmt"
  "github.com/emirpasic/gods/sets/treeset")
func minReverseOperations(n int, p int, banned []int, k int) []int {  oddSet := treeset.NewWithIntComparator()  evenSet := treeset.NewWithIntComparator()
  for i := 1; i < n; i += 2 {    oddSet.Add(i)  }  for i := 0; i < n; i += 2 {    evenSet.Add(i)  }
  for _, ban := range banned {    oddSet.Remove(ban)    evenSet.Remove(ban)  }
  oddSet.Remove(p)  evenSet.Remove(p)
  ans := make([]int, n)  for i := range ans {    ans[i] = -1  }
  queue := make([]int, n)  l := 0  r := 0  queue[r] = p  r++
  level := 0  for l < r {    end := r    for l < end {      cur := queue[l]      ans[cur] = level
      left := max(cur-k+1, k-cur-1)      right := min(cur+k-1, n*2-k-cur-1)
      curSet := oddSet      if (left & 1) == 0 {        curSet = evenSet      }
      _, ceiling := curSet.Find(func(index int, value interface{}) bool {        if value.(int) >= left {          return true        } else {          return false        }      })
      for ceiling != nil && ceiling.(int) <= right {        queue[r] = ceiling.(int)        r++        curSet.Remove(ceiling)        _, ceiling = curSet.Find(func(index int, value interface{}) bool {          if value.(int) >= left {            return true          } else {            return false          }        })      }
      l++    }    level++  }
  return ans}
func max(a, b int) int {  if a > b {    return a  }  return b}
func min(a, b int) int {  if a < b {    return a  }  return b}
func main() {  n := 4  p := 0  banned := []int{1, 2}  k := 4
  result := minReverseOperations(n, p, banned, k)  fmt.Println(result)}