codeforces-go 题解精读：二进制数组全部变为 1 的最小反转次数——贪心唯一性与正确性证明（LeetCode 双周赛 133 B）-平芜编程栈

科学计算

【免费下载链接】codeforces-go

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

项目地址：https://gitcode.com/GitHub_Trending/co/codeforces-go

导读

本题是 LeetCode 双周赛 133 的 B 题（Minimum Operations to Make Binary Array Elements Equal to One I），同时也是 codeforces-go 仓库中以"题解文档 + 源码 + 测试数据"三联件沉淀的一类经典贪心问题：每次操作反转连续三个位置，求使 01 数组全变为 1 的最小操作次数。读完本文，你将掌握：如何从"第一个位置是否必须操作"出发构造唯一操作序列、为什么贪心在本题必然正确（可交换性 + 至多一次 + 唯一性三段论证）、七种主流语言的等价实现，以及把区间长度 3 推广到任意 k（对应 CF1955E）时如何使用差分数组做到与 k 无关的 O(n) 做法。

题目回顾与问题建模

给定一个 01 数组nums，每次操作可以选择一个下标i ∈ [0, n-3]，把nums[i]、nums[i+1]、nums[i+2]三个位置全部反转，即异或 1。

目标：返回把nums全变成 1 的最小操作次数；如果无法做到，返回-1。

几个关键边界直觉：

操作是幂等的：对同一个i操作两次等价于没操作；
操作覆盖的位置只有i, i+1, i+2三个，彼此之间只与相邻下标重叠；
当n < 3时不存在任何合法下标，此时只有数组已经全为 1 才可行（答案为 0），否则为-1。

贪心决策：从"必须操作"到唯一的操作序列

原文档给出的核心思路是按位置从左到右逐位决策：

讨论是否需要对i = 0执行操作：
- 如果nums[0] = 1，不需要操作，问题变成剩下n-1个数的子问题；
- 如果nums[0] = 0，一定要操作，问题同样变成剩下n-1个数的子问题。
接下来对i = 1重复同样的判断，处理方式与上一步完全相同。
依此类推，一直处理到i = n-3。处理完毕后，还剩下nums[n-2]和nums[n-1]两个位置——这两个数必须都等于 1，否则无法达成题目要求，返回-1。

为什么"遇到 0 就必须操作"是安全的？关键洞察在于：处理到位置i时，nums[i]的最终状态已经定型。因为任何操作j只会影响j, j+1, j+2三个位置，当j > i时影响的起点已经超过i，无法再回头改变nums[i]；而j = i正是此刻的决策点。也就是说，当前位置一旦被"扫描"过去，就再也无法被后续操作修改，因此它是决定操作与否的唯一依据。

模拟过程可以写作：

对i = 0..n-3：
- 若nums[i] == 0：执行操作（反转i+1、i+2两个位置即可，因为nums[i]不需要再看了），操作次数加 1；
- 若nums[i] == 1：跳过。
结束后检查nums[n-2]与nums[n-1]，两者都为 1 则返回累计次数，否则返回-1。

正确性论证：为什么"从左到右贪心"一定是对的

原文档用四步问答把正确性讲得很透彻，这里完整保留并展开：

问：为什么这样做是对的？

答：

操作顺序不影响结果（可交换性）：先操作i再操作j（i ≠ j），与先操作j再操作i的结果完全相同。因为每次操作只是对三个固定位置做异或 1，异或运算是可交换、可结合的，最终每个位置被反转的次数只取决于"操作集合"，与执行顺序无关。既然顺序无关，我们总可以把任何最优操作序列重排成"从左到右"执行。
同一个下标至多操作一次：对同一个i操作两次等于没有操作，所以最优解中每个i的操作次数要么 0 次要么 1 次（多余的偶数次可以删除，奇数次可以合并为 1 次）。
从左到右的操作方式有且仅有一种：结合上述两点，在从左到右扫描的过程中，遇到1一定不能操作（操作了反而会引入多余的翻转，且违反唯一性），遇到0一定要操作（否则这个位置永远无法变成 1），所以操作序列被唯一确定。
既然操作方式是唯一的，只需模拟：唯一性保证了贪心决策没有分叉，直接按规则模拟整个扫描过程即可得到答案。

问：题目要求的"最少"体现在哪里？

答：对同一个i至多操作一次，就可以做到最少的操作次数。由于任意可行解都能重排成从左到右、每个下标至多一次的形态，而满足该形态的操作序列又是唯一的，因此这个唯一序列天然就是操作次数最少的可行解。

复杂度分析

时间复杂度：O(nk)，其中 n 是nums的长度，k = 3 是每次操作反转的元素个数；由于 k 是常数，实际表现为 O(n) 的单次扫描。
空间复杂度：O(1)，全程原地修改数组，只使用常数个变量。

七种语言的等价实现

原文档给出了 Python3、Java、C++、C、Go、JavaScript、Rust 七个版本的实现，逻辑完全一致，全部继承如下：

class Solution: def minOperations(self, nums: List[int]) -> int: ans = 0 for i in range(len(nums) - 2): if nums[i] == 0: # 必须操作 nums[i + 1] ^= 1 nums[i + 2] ^= 1 ans += 1 return ans if nums[-2] and nums[-1] else -1

class Solution { public int minOperations(int[] nums) { int n = nums.length; int ans = 0; for (int i = 0; i < n - 2; i++) { if (nums[i] == 0) { // 必须操作 nums[i + 1] ^= 1; nums[i + 2] ^= 1; ans++; } } return nums[n - 2] != 0 && nums[n - 1] != 0 ? ans : -1; } }

class Solution { public: int minOperations(vector<int>& nums) { int n = nums.size(); int ans = 0; for (int i = 0; i < n - 2; i++) { if (nums[i] == 0) { // 必须操作 nums[i + 1] ^= 1; nums[i + 2] ^= 1; ans++; } } return nums[n - 2] && nums[n - 1] ? ans : -1; } };

int minOperations(int* nums, int n) { int ans = 0; for (int i = 0; i < n - 2; i++) { if (nums[i] == 0) { // 必须操作 nums[i + 1] ^= 1; nums[i + 2] ^= 1; ans++; } } return nums[n - 2] && nums[n - 1] ? ans : -1; }

func minOperations(nums []int) (ans int) { n := len(nums) for i, x := range nums[:n-2] { if x == 0 { // 必须操作 nums[i+1] ^= 1 nums[i+2] ^= 1 ans++ } } if nums[n-2] == 0 || nums[n-1] == 0 { return -1 } return }

var minOperations = function(nums) { const n = nums.length; let ans = 0; for (let i = 0; i < n - 2; i++) { if (nums[i] === 0) { // 必须操作 nums[i + 1] ^= 1; nums[i + 2] ^= 1; ans++; } } return nums[n - 2] && nums[n - 1] ? ans : -1; };

impl Solution { pub fn min_operations(mut nums: Vec<i32>) -> i32 { let n = nums.len(); let mut ans = 0; for i in 0..n - 2 { if nums[i] == 0 { // 必须操作 nums[i + 1] ^= 1; nums[i + 2] ^= 1; ans += 1; } } if nums[n - 2] != 0 && nums[n - 1] != 0 { ans } else { -1 } } }

各实现中值得注意的实现细节：

Python 版用range(len(nums) - 2)控制扫描区间，末尾用nums[-2] and nums[-1]做短路判断；
Go 版的循环体可以直接读nums[i]的当前值，因为每次操作后nums[i+1]、nums[i+2]会立刻被就地更新，下一次迭代读到的nums[i+1]已经是"应用了之前所有操作"后的真实值——这正是"当前值已定型"的落地体现；
末尾两个位置无需进入循环：它们可能被i = n-4, n-3的操作修改，但自己永远不能作为操作起点，所以扫描结束后必须单独校验。

仓库中的实现与实测验证

本题在仓库中不是孤立的一页题解，而是"文档 + 源码 + 测试数据"三件套：

题解文档：leetcode/biweekly/133/b/README.md（即本文主体）；
Go 实现：leetcode/biweekly/133/b/b.go，与上文 Go 版代码逐字一致；
测试数据：leetcode/biweekly/133/b/b.txt；
测试用例：leetcode/biweekly/133/b/b_test.go，文件头注明由 copypasta/template/leetcode/generator_test.go 自动生成。

b_test.go 的核心只有一条调用：

func Test_b(t *testing.T) { if err := testutil.RunLeetCodeFuncWithFile(t, minOperations, "b.txt", 0); err != nil { t.Fatal(err) } }

b.txt 中存放的是两组"输入 → 期望输出"数据：

[0,1,1,1,0,0] 3 [0,1,1,1] -1

两组数据对应的模拟过程如下：

输入	输出	决策轨迹
`[0,1,1,1,0,0]`	`3`	依次在`i=0`、`i=1`、`i=3`执行操作
`[0,1,1,1]`	`-1`	扫描后末尾两位为`1,0`，无法达成

以第一组为例逐步验证：i=0时nums[0]=0，翻转1,2得[1,0,0,1,0,0]；i=1时nums[1]=0，翻转2,3得[1,0,1,0,0,0]；i=2时nums[2]=1跳过；i=3时nums[3]=0，翻转4,5得[1,0,1,0,1,1]；末尾nums[4]=1、nums[5]=1，返回3。

测试机制：testutil.RunLeetCodeFuncWithFile（实现在 leetcode/testutil/leetcode.go）读取 b.txt，按"每fNumIn + fNumOut = 2行一组"切分样例，交给RunLeetCodeFuncWithExamples（leetcode/testutil/leetcode.go）逐组调用：先通过反射把[0,1,1,1,0,0]解析为[]int入参、把3解析为期望输出，再执行被测函数并比对实际结果；每个用例以t.Run("Case N")子测试运行，还内置了基于time.Timer的 TLE 检测。运行方式（在仓库根目录执行）：

go test ./leetcode/biweekly/133/b -run Test_b -v -count=1

注意：本文撰写环境的 shell 中未检测到 Go 工具链（go: not found），上述命令适用于安装了 Go 1.x 的开发环境。

边界情况与"无法做到"的判定

本题判-1的唯一条件是：扫描完[0, n-3]后，nums[n-2]与nums[n-1]中存在 0。深层原因有二：

末尾两个位置永远不可能作为操作起点（没有合法的i能覆盖它们之前的完整三连），只能被i = n-4或i = n-3的操作翻转；
若扫描结束后它们仍为 0，则没有任何操作还能改变它们，问题无解。

此外还有两类平凡情形值得注意：

输入全为 1：循环一次也不触发，末尾校验通过，答案为0；
n < 3：不存在任何合法操作。此时若数组已全为 1 答案为0，否则为-1。仓库 Go 实现中range nums[:n-2]在n=2时自然为空切片、直接以末尾两位判断，逻辑自洽；测试数据集中在n >= 4的场景。

思考题延伸：把 3 推广到任意 k（CF1955E）

原文档留下一道思考题：把题目中的 3 替换成k（1 <= k <= n），能否想出一个与 k 无关的 O(n)做法？

思路分两步递进：

固定 k 的贪心依旧成立：把"翻三个位置"换成"翻k个连续位置"后，前面的三段论证完全不变——操作可交换、同一个起点至多一次、从左到右唯一。扫描i = 0..n-k，遇到nums[i] == 0就翻转[i, i+k-1]，最后检查末尾k-1个位置。
去掉翻转本身的 O(k) 开销：朴素实现每次翻转要写k个位置，总代价 O(nk)。要做到"与 k 无关的 O(n)"，需要引入差分标记 + 懒更新计数：用变量cur记录当前位置累积被翻转的次数（奇偶性），用差分数组diff记录每个操作在区间右端点+1位置处的撤销标记。处理位置i时先cur += diff[i]，若(nums[i] + cur) % 2 == 0（即当前位置当前值为 0），则执行一次区间翻转：cur ^= 1（懒标记生效），diff[i+k] ^= 1（在区间外撤销），ans++。这样每次翻转是 O(1) 的，整体 O(n)。

这道思考题对应的正是 Codeforces 1955E（Long Inversions）：外层枚举每个k，内层套用上述固定k的 O(n) 检查，总复杂度 O(n²)。理解本题"从左到右唯一性"是解开那道题的关键前置知识。

归类与延伸：这类贪心在竞赛题单中的位置

原文档将本题归类于贪心与思维题单，该分类下覆盖：基本贪心策略、反悔贪心、区间贪心、字典序相关、数学与思维、脑筋急转弯、构造类问题。与本题同族的知识点还包括：

滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）：反转区间问题的兄弟模型；
常用数据结构（差分）：把区间批量操作从 O(k) 摊到 O(1)，正是上一节思考题的解法基石；
位运算：异或 1 实现 0/1 翻转是本题操作的语言实现核心。

如果你需要继续在仓库中精读同族题目，可以重点关注 main/ 目录下按题号组织的 CF 题解，以及 leetcode/ 目录下按周赛/双周赛组织的逐题目录——每一题通常都遵循"README 题解 + 同名 Go 实现 + 文本测试数据 + 自动生成测试"的同一套沉淀模式。

一句话总结：本题的价值不在于"贪心策略本身"，而在于它示范了一套可复用的正确性证明框架——先证明操作可交换（顺序无关）、再证明每个决策点至多一次、最后推出操作序列唯一——这套三段论几乎可以原样迁移到所有"区间反转、目标为全 1/全 0"的翻转类问题（含 CF1955E 的 k 推广版本）上。