主題
題目連結(jié)：
題目意譯：
你被給定一個整數(shù) n 以及一個範圍位於 [0, n - 1] 中的整數(shù) p。這代表著有一個索引值從 0 開始數(shù)且長度為 n 的陣列 arr，除了只有位置 p 的數(shù)值設(shè)為 1 以外，所有位置之?dāng)?shù)值都設(shè)為 0。
你同時也被給定一整數(shù)陣列 banned，其包含著上述陣列中的若干個位置。對於 banned 中的第 i 個位置，arr[banned[i]] = 0，且 banned[i] != p。
你可以對 arr 執(zhí)行若干次操作。在一次操作中，你可以選擇一段大小為 k 的子陣列並反轉(zhuǎn)該子陣列。不過 arr 中的 1 不得跑到 banned 中列出的任意一個位置。換句話說，在每此操作結(jié)束後 arr[banned[i]] 之值將維持為 0。
回傳一個陣列 ans，其中對於每一個位於 [0, n - 1] 中的數(shù)值 i，ans[i] 為將 arr 中的 1 移動到位置 i 所需的最少反轉(zhuǎn)操作數(shù)；如果不可能則為 -1。
一個子陣列為一個陣列中的一段連續(xù)非空元素序列。
不同 i 值之間的 ans[i] 之?dāng)?shù)值彼此獨立。
反轉(zhuǎn)一個陣列意味著把其包含的元素之順序顛倒。
限制：
1 ≦ n ≦ 10 ^ 5
0 ≦ p ≦ n - 1
0 ≦ banned.length ≦ n - 1
0 ≦ banned[i] ≦ n - 1
1 ≦ k ≦ n
banned[i] != p
banned 中所有數(shù)值彼此相異。
範例測資：
範例 1：
輸入： n = 4, p = 0, banned = [1,2], k = 4
輸出： [0,-1,-1,1]
解釋： 在此例中，k = 4 所有只有一種可能的反轉(zhuǎn)操作，其即為反轉(zhuǎn)整個陣列。
一開始 1 位於位置 0 所以要抵達位置 0 所需次數(shù)為 0。
我們不得將 1 放在 banned 中的任意一個位置，因此位置 1 和 2 的答案為 -1。
最後，我們用一次反轉(zhuǎn)可以將 1 帶到位置 3，所以其答案為 1。
範例 2：
輸入： n = 5, p = 0, banned = [2,4], k = 3
輸出： [0,-1,-1,-1,-1]
解釋： 在此例中，1 一開始位於位置 0，所以該位置的答案為 0。
我們可以執(zhí)行大小為 3 的反轉(zhuǎn)操作。1 目前位於位置 0，所以要離開該位置我們需要反轉(zhuǎn) [0, 2] 這個子陣列，但是反轉(zhuǎn)該陣列後 arr[2] 會是 1，而這是不合法的。
所以我們無法把 1 從位置 0 移走，因此其餘位置的答案都是 -1。
範例 3：
輸入： n = 4, p = 2, banned = [0,1,3], k = 1
輸出： [-1,-1,0,-1]
解釋： 在此例中，我們只能執(zhí)行大小為 1 的反轉(zhuǎn)操作。因此 1 永遠不會改變位置。
解題思維：
首先，對於中間（即沒有過於靠近邊界）的索引值而言，k 這個值本身意味著有 k 種可以反轉(zhuǎn)的子陣列。
即如果現(xiàn)在 1 的位置是位於 x，則各個子陣列的開頭索引值依序為 x - k + 1 、 x - k 、 …… 、 x。令 Lx = x - k + 1 、 Rx = x，則這些子陣列的開頭索引值可以簡寫成 [Lx, Rx]。
但是這不代表著所有位置都會遵循這個規(guī)律，畢竟有些位置比較靠邊緣。因此 Lx 、 Rx 之式子應(yīng)改寫為 Lx = max(0, x - k + 1) 和 Rx = min(n - k, x) 來推廣到普遍的情況。
接著我們來觀察一個開頭索引值為 i 的子陣列會把當(dāng)前位於 x 的 1 反轉(zhuǎn)到何處。
可以看到其為 i + ((i + k - 1) - x)，簡化後可以得到 2i + k - x - 1。
而從上式可以看到索引值 i 和索引值 i + 1 的兩個子陣列將位於 x 的 1 反轉(zhuǎn)後的位置會相差恰好 2（對於 k = 1，也只有一個子陣列可以反轉(zhuǎn)，所以沒差）。
因此 Lx 得到的反轉(zhuǎn)位置是 L = 2Lx + k - x - 1 且 Rx 得到的反轉(zhuǎn)位置為 R = 2Rx + k - x - 1。因此各個反轉(zhuǎn)後的位置將會位於 [L, R] 之間且每個相鄰位置之間彼此相差 2，即 L 、 L + 2 、 L + 4 、 …… 、 R。
而如果我們此時直接套用廣度優(yōu)先搜尋（Breadth First Search，BFS）的方式，如這題，即從 p 開始走「一步」到 2Lp + k - p - 1 ～ 2Rp + k - p - 1，然後這些位置再各自走一步等等。
可以看到我們有極高的機會會遇到如現(xiàn)在要走一步走到 L 、 L + 2 、 L + 4 、 …… 、 R 這些位置上，但是實際上 L + 2 ～ R - 2 已經(jīng)全部都走過了等等的情況。
那要怎麼辦？其中一個辦法是我們可以讓每一個位置指向「自己或是其右側(cè)的『下一個』尚未走過的位置」，因此在上面的例子中 L + 2 ～ R - 2 的所有位置將會統(tǒng)一指向 R 這個還沒走過的位置。而 L ～ R 都走完後會全數(shù)統(tǒng)一指向 R + 2（如果 R + 2 還沒走過的話。如果有走過的話，可能實際上是 R + 4 、 R + 6 等等）。
而我們可以把這些行為看作是「合併」，並且將這些位置的群體視為是「集合」。因此這個辦法可以用併查集（Union-Find Set，參見這題的介紹）來實作。不過因為這題會統(tǒng)一指向「右邊」，因此繼續(xù)使用「沒有調(diào)整」的按秩合併（Union-by-rank）的話會出事，但是可以參見該題介紹底下的留言來調(diào)整儲存的資料以便繼續(xù)使用按秩合併（這部份留給讀者思考。範例程式碼中的併查集是直接把按秩合併的部份整個移除）。
因此對於某一個可能的位置 x 來說，反轉(zhuǎn)後的位置會是 L 、 L + 2 、 L + 4 、 …… 、 R。而如果現(xiàn)在看到反轉(zhuǎn)後的位置是 q，則將 q 直接跳到 q 指向的位置，因為那才是實際上我們需要判斷的「未走過的位置」。而當(dāng)然，x 最右邊只能反轉(zhuǎn)到 R，因此如果新的「未走過的位置」超過了 R 就得停止動作了。
當(dāng)然，還沒有結(jié)束。題目還有一個限制條件——即陣列 banned 的存在。但是這部份很單純，只要在 BFS 的過程中忽略掉那些存在於 banned 的位置即可。
剩下的位置只要從位置 p 進行 BFS 一次便可以知道其最少所需的反轉(zhuǎn)次數(shù)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
