LeetCode 2612. Minimum Reverse Operations

題意理解

給定一個整數 n 和一個整數 p，分別表示一個長度為 n 且除了索引為 p 處是 1 之外，其他所有數都是 0 的陣列 arr；同時給定一個由整數組成的陣列 banned 表示陣列中的限制位置。可以對陣列 arr 進行以下操作：如果單個 1 不在 banned 所標示的位置上，反轉大小為 k 的子陣列。

舉例來說：

n = 4, p = 0, banned = [1, 2], k = 4

n = 4, p = 0, banned = [1, 2], k = 4

這一條件表示初始的陣列為 [1, 0, 0, 0]，接著逐個索引討論：

1. 索引值為 0 時，原始陣列中該位置已為 1，因此所需最少操作次數為 0。
2. 索引值為 1 時，屬於 banned 中禁止操作的數字，因此無法調整為指定目標，所需操作次數為 -1。
3. 索引值為 2 時，屬於 banned 中禁止操作的數字，因此無法調整為指定目標，所需操作次數為 -1。
4. 索引值為 3 時，翻轉大小為 4 的子陣列，可以得到 [0, 0, 0, 1]，因此所需操作次數為 `1`。

綜合上述，返回結果為 [0, -1, -1, 1]。

解法一：Breadth-First Search

假設字串 s 的長度為 $n$ 且其中共有 $z$ 個 '0' 和 $n-z$ 個 '1'，假設在進行操作時可以翻轉 $x$ 個 '0' 和 $(k-x)$ 個 '1'。考慮翻轉一次後的情況：

• 翻轉後的 '0' 共有 $z\prime = z – x + (k – x) = z + k – 2x$ 個。
• 翻轉後的 '1' 共有 $n – z – k + 2x$ 個。