題目資訊

• 題目編號: 3191
• 題目連結: Minimum Operations to Make Binary Array Elements Equal to One I
• 主題: Array, Bit Manipulation, Queue, Sliding Window, Prefix Sum

題目敘述

你有一個二元陣列 nums。

你可以對陣列進行以下操作任意次（可能為零次）：

• 選擇陣列中的任意三個連續元素，並翻轉所有元素。

翻轉一個元素意味著將其值從 0 變為 1，從 1 變為 0。

返回將 nums 中的所有元素變為 1 所需的最小操作次數。如果無法做到，則返回 -1。

範例 1：

輸入: nums = [0,1,1,1,0,0]

輸出: 3

解釋： 我們可以進行以下操作：

• 選擇索引為 0, 1 和 2 的元素。得到的陣列是 nums = [1,0,0,1,0,0]。
• 選擇索引為 1, 2 和 3 的元素。得到的陣列是 nums = [1,1,1,0,0,0]。
• 選擇索引為 3, 4 和 5 的元素。得到的陣列是 nums = [1,1,1,1,1,1]。

範例 2：

輸入: nums = [0,1,1,1]

輸出: -1

解釋： 無法使所有元素變為 1。

約束條件：

• $3 \leq \text{nums.length} \leq 10^5$
• $0 \leq \text{nums}[i] \leq 1$

直覺

這個問題的核心在於透過翻轉三個連續元素的特定操作，將一個二元數組轉換為全為1的均勻數組。挑戰在於系統化地應用此操作，以及決定何時無法達成目標。

解法

此方法涉及遍歷 nums 數組，並在需要時執行翻轉操作。演算法的步驟如下：

1. 初始化：首先獲取 nums 數組的大小，並初始化一個計數器 operations 為零，來跟踪執行的操作次數。

2. 遍歷數組：從第一個元素開始遍歷 nums 數組直至最後一個。

3. 檢查零：對於每個元素，檢查其是否為零。若存在零，則表示需要執行翻轉操作將其轉換為一。

4. 執行翻轉操作：

   • 若遇到零，增加 operations 計數。
   • 檢查是否能執行翻轉：確保在當前索引之後至少還有兩個元素（i + 1 和 i + 2），以便對三個連續元素應用翻轉操作。如若不然，則返回 -1，表示不可能將所有元素變為一。

5. 翻轉元素：如果可以進行翻轉，則更改接下來的兩個連續元素的狀態：使用操作 1 - nums[j] 翻轉 nums[i + 1] 和 nums[i + 2]。

6. 輸出結果：一旦迴圈完成，返回總的 operations 計數作為結果。

該演算法利用了一種簡單的貪婪策略，在遇到零時立即將其轉換為一，從局部的角度保持操作最小化。這確保了涵蓋所有情境，同時也能檢測出無法將整個數組轉換為全為1的情況。

程式碼

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();  // 獲取 nums 陣列的大小
        int operations = 0;   // 初始化所需操作次數為 0

        for (int i = 0; i < n; i++) {
            // 檢查當前元素是否為 0
            if (nums[i] == 0) {
                operations++;  // 翻轉操作次數加 1
            
                // 檢查是否有足夠的元素可供翻轉
                if (i + 2 >= n) return -1;  // 如果沒有，返回 -1 表示不可能

                // 翻轉接下來的兩個連續元素
                nums[i + 1] = 1 - nums[i + 1];
                nums[i + 2] = 1 - nums[i + 2];
            }
        }
        return operations;  // 返回所需的總操作次數
    }
};

Python

class Solution:
    def minOperations(self, nums):
        n = len(nums)  # 獲取 nums 陣列的大小
        operations = 0  # 初始化所需操作次數為 0

        for i in range(n):
            # 檢查當前元素是否為 0
            if nums[i] == 0:
                operations += 1  # 增加翻轉操作次數

                # 檢查是否有足夠的元素可供翻轉
                if i + 2 >= n:
                    return -1  # 如果沒有，返回 -1 表示不可能

                # 翻轉接下來的兩個連續元素
                nums[i + 1] = 1 - nums[i + 1]
                nums[i + 2] = 1 - nums[i + 2]

        return operations  # 返回所需的總操作次數

複雜度分析

• 時間複雜度: $O(n)$

  演算法對陣列中的每個元素都恰好處理一次，根據當前元素的值進行決策，並在可能的情況下翻轉接下來的兩個元素。這導致了對陣列的線性遍歷，使得時間複雜度為 $O(n)$，其中 $n$ 是陣列 nums 的長度。

• 空間複雜度: $O(1)$

  演算法就地運行，只使用固定數量的額外空間來存儲變數，如 operations 和循環控制變數。沒有使用隨著輸入大小增長的額外資料結構，因此空間複雜度是常數 $O(1)$。