Every day a Leetcode
題目來源：3192. 使二進制數組全部等于 1 的最少操作次數 II
解法1：遍歷
由于 nums[i] 會被其左側元素的操作影響，所以我們先從最左邊的 nums[0] 開始思考。
分類討論：
- 如果 nums[0]=1，無需反轉，問題變成剩下 n?1 個數如何操作。接下來考慮 nums[1]。
- 如果 nums[0]=0，反轉次數加一，問題變成剩下 n?1 個數（在修改次數是奇數的情況下）如何操作。接下來考慮 nums[1]。
對后續元素來說，由于反轉偶數次等于沒反轉，所以只需考慮反轉次數的奇偶性。
一般地，設反轉次數的奇偶性為 k，分類討論：
- 如果 nums[i]≠k，無需反轉，接下來考慮 nums[i+1]。
- 如果 nums[i]=k，反轉次數加一，接下來考慮 nums[i+1]。
代碼：
/** @lc app=leetcode.cn id=3192 lang=cpp** [3192] 使二進制數組全部等于 1 的最少操作次數 II*/// @lc code=start
class Solution
{
public:int minOperations(vector<int> &nums){int n = nums.size();int ans = 0;for (int i = 0; i < n; i++){if (nums[i] == 1 && ans % 2 == 1)ans++;if (nums[i] == 0 && ans % 2 == 0)ans++;}return ans;}
};
// @lc code=end
結果：
復雜度分析：
時間復雜度：O(n)，其中 n 是數組 nums 的長度。
空間復雜度：O(1)。
