2023-09-16：用go語言，給你一個整數(shù) n 和一個在范圍 [0, n - 1] 以內(nèi)的整數(shù) p ，

它們表示一個長度為 n 且下標(biāo)從 0 開始的數(shù)組 arr ，

數(shù)組中除了下標(biāo)為 p 處是 1 以外，其他所有數(shù)都是 0 。

同時給你一個整數(shù)數(shù)組 banned ，它包含數(shù)組中的一些位置。

banned 中第 i 個位置表示 arr[banned[i]] = 0 ，題目保證 banned[i] != p 。

你可以對 arr 進(jìn)行 若干次 操作。一次操作中，你選擇大小為 k 的一個 子數(shù)組

并將它 翻轉(zhuǎn) 。在任何一次翻轉(zhuǎn)操作后，

你都需要確保 arr 中唯一的 1 不會到達(dá)任何 banned 中的位置。

換句話說，arr[banned[i]] 始終 保持 0 。

請你返回一個數(shù)組 ans ，對于 [0, n - 1] 之間的任意下標(biāo) i ，

ans[i] 是將 1 放到位置 i 處的 最少 翻轉(zhuǎn)操作次數(shù)，

如果無法放到位置 i 處，此數(shù)為 -1 。

子數(shù)組 指的是一個數(shù)組里一段連續(xù) 非空 的元素序列。

對于所有的 i ，ans[i] 相互之間獨(dú)立計(jì)算。

將一個數(shù)組中的元素 翻轉(zhuǎn) 指的是將數(shù)組中的值變成 相反順序 。

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

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

來自左程云。

答案2023-09-16：

步驟如下：

1.創(chuàng)建一個奇數(shù)集合（oddSet）和一個偶數(shù)集合（evenSet）。

2.將所有奇數(shù)（除了p和banned中的位置）添加到oddSet中。

3.將所有偶數(shù)（除了p和banned中的位置）添加到evenSet中。

4.創(chuàng)建一個長度為n的數(shù)組ans，初始化全部為-1。

5.創(chuàng)建一個隊(duì)列queue和兩個指針l和r，初始化r=0。

6.將p放入隊(duì)列queue中，r加1。

7.初始化level=0。

8.當(dāng)l < r時，執(zhí)行以下步驟：

• ??取出隊(duì)列頭部元素cur。

• ??將level賦值給ans[cur]。

• ??計(jì)算cur左邊和右邊的范圍，分別為left和right。

• ??根據(jù)left的奇偶性，選擇對應(yīng)的集合curSet（如果left是偶數(shù)，則curSet為evenSet；否則為oddSet）。

• ??在curSet中查找大于等于left的最小元素，并將其加入隊(duì)列queue中，r加1。

• ??從curSet中移除該元素。

• ??重復(fù)以上步驟，直到curSet中沒有大于等于left的元素。

• ??l加1。

9.更新level，重復(fù)步驟8直到l < r不成立。

10.返回ans。

時間復(fù)雜度：假設(shè)n為數(shù)組長度，遍歷數(shù)組需要O(n)的時間復(fù)雜度，每次操作需要在集合中查找和移除元素，集合的查找和移除操作的時間復(fù)雜度為O(log n)?？傮w時間復(fù)雜度為O(n log n)。

空間復(fù)雜度：創(chuàng)建兩個集合，集合的空間復(fù)雜度為O(n)，創(chuàng)建一個隊(duì)列，隊(duì)列的空間復(fù)雜度為O(n)，創(chuàng)建一個數(shù)組，數(shù)組的空間復(fù)雜度為O(n)，總體空間復(fù)雜度為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)
}