# 前言
本来不想写这道题的，但这两天的题是同一个类型的，就一起写了把。
# 第一道
难度：中等
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意连续 3 个元素，并将它们 全部反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 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 <= nums.length <= 10^5
0 <= nums[i] <= 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
一开始在想，最少操作次数是否能通过贪心来解决，或者观察出规律。由于每次只能反转连续的3个元素，那么就有这几种包含0的情况：
...0...00...、...000...、...00...0...，...代表n个1。
那是否能通过分类讨论来解决呢？比如优先把第二种情况先反转，因为其不会影响到其他非0的元素，但我试着模拟了一下，优先处理000的反而操作次数更多了。
仔细思考后发现，从左向右按顺序反转元素其实就是最少操作次数了，因为0是一定要反转的，只要反转就必定会带来其他影响，虽然证明不了从左到右是最优的，但可以先试试。
用一个指针p来记录下标，当遇到0就处理从当前下标到往后2个元素进行反转，然后考虑一下不能全部反转成1的情况即可
function minOperations(nums: number[]): number {
let p = 0 // p以及往前的元素都是1
const n = nums.length
let ans = 0
while(p < n) {
while(nums[p] && p < n) p++
if (p >= n) {
break
}
if (p+2 >= n) {
ans = -1
break
}
// nums[p] == 0
nums[p+1] = Number(!nums[p+1])
nums[p+2] = Number(!nums[p+2])
ans++
p++
if (nums[p]) p++
if (nums[p]) p++
}
return ans
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
官方解法也是同样的思路，但是写法更加简洁：
function minOperations(nums: number[]): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
if (nums[i] === 0) {
if (i > n - 3) {
return -1;
}
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
ans++;
}
}
return ans;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度：O(n)
# 第二道
难度：中等
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。
示例 1：
输入：nums = [0,1,1,0,1]
输出：4
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。
选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。
选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。
选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。
示例 2：
输入：nums = [1,0,0,0]
输出：1
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [1,1,1,1] 。
提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
第二道和第一道的区别是第二道是反转后面的所有元素，而非只有3个，这样子就不会出现不能全部反转成1的情况了。
有了第一道的思路，可以很容易想到，后面的变更操作，我并不用每次一个个去反转他们，因为我可以记录他们的反转次数，并且如果反转次数是奇数次，则原数需要反转，如果是0或者偶数次则不需要反转，因为反转的结果是相同的。
function minOperations(nums: number[]): number {
// 记录后面需要变化多少次
// 若为奇数次，则反转，若为偶数次则不变
const n = nums.length;
//let ans = 0;
let change = 0
for (let i = 0; i < n; i++) {
if (change % 2 != 0) {
nums[i] ^= 1
}
if (nums[i] == 0) {
change++
}
}
return change;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度也是O(n)。
官方还提供了dp的解法，但明显复杂了很多，也很难想到dp的定义以及状态转移方程，就不继续深入了，没什么必要。