使二进制数组全部等于 1 的最少操作次数 II

> Problem: 3192. 使二进制数组全部等于 1 的最少操作次数 II

题目描述

给定一个二进制数组 nums，你可以进行任意次的反转操作。每次操作可以选择一个下标 i，将从下标 i 开始直到数组末尾的所有元素反转（即将 0 变为 1，将 1 变为 0）。请你返回使数组所有元素都变为 1 的最少操作次数。

解题思路

这道题的目标是找到最少的反转操作次数，使得数组中的所有元素都变为 1。可以通过观察数组的状态变化来设计贪心策略，以下两种思路分别实现了该目标。

思路一：基于状态变化的贪心算法

核心思路：数组从左向右遍历时，每次遇到状态变化时（从 0 变 1 或从 1 变 0），就进行一次反转操作。这种贪心策略确保我们只在必要的时候操作，避免了不必要的反转操作。

具体步骤：

1. 从头遍历数组，检查当前元素和下一个元素的状态。如果两者不同，则意味着状态发生了变化，反转操作可以使后续的元素恢复到一致的状态。
2. 遍历完成后，若数组的第一个元素为 0，还需要额外的一次反转操作，因为第一次反转可能从 0 开始。

代码实现：

class Solution {
public:int minOperations(vector<int>& nums) {int n = nums.size();int operations = 0;// 遍历数组，遇到不同的元素就执行一次反转操作for (int i = 0; i < n - 1; i++) {if (nums[i] != nums[i + 1]) {// 状态变化，进行反转操作operations++;}}// 如果第一个元素是 0，额外再执行一次反转操作return nums[0] == 0 ? operations + 1 : operations;}
};

复杂度分析：

• 时间复杂度：O(n)，我们需要遍历数组一次。
• 空间复杂度：O(1)，只需要常量空间存储操作次数。

思路二：基于奇偶判断的贪心策略

核心思路：我们可以通过观察每个元素是否与当前的期望状态一致（通过奇偶来判断）来决定是否需要反转。即如果某个元素 num 与当前计数 cnt % 2 相同，则意味着它与期望状态一致，否则我们需要进行反转操作。

具体步骤：

1. 遍历数组，对每个元素检查其是否与当前反转状态（由 cnt % 2 控制）一致。
2. 如果一致，则不需要进行反转；如果不一致，则需要一次反转操作，并将计数 cnt 增加1。

代码实现：

class Solution {
public:int minOperations(vector<int>& nums) {int cnt = 0;for (int num : nums) {if (num == cnt % 2) {// 如果当前元素和期望状态一致，执行一次反转操作cnt++;}}return cnt;}
};

复杂度分析：

• 时间复杂度：O(n)，我们只需遍历数组一次即可。
• 空间复杂度：O(1)，仅使用了常量空间。

两种解法对比

• 基于状态变化的贪心算法 更加直观，基于数组中元素的状态变化来决定反转操作次数。它在遇到相邻元素不一致时进行反转。
• 基于奇偶判断的贪心策略 则通过维护当前的反转次数来决定每个元素是否与期望状态一致。这种方法更为巧妙，利用了奇偶性判断每个元素的状态是否正确。

两者在时间和空间复杂度上相同，都能够有效地解决问题，但第二种方法的实现更加简洁、紧凑。

总结

这道题的关键是设计一个合适的贪心策略来最小化反转操作次数。通过分析数组的状态变化或利用反转次数的奇偶性，可以轻松实现最优解法。