题目描述
思路解析动画文字版
记住这一句:从左往右,谁是 0 就把从它开始的连续三个翻过来,数一次操作。为什么必须从左往右、为什么这样一定最省,下面用画面讲给你看。
起点 · 先找出所有的 0：先看这个二进制数组 [0,1,1,1,0,0]。红色标出来的是 0,我们的任务是把所有 0 都变成 1。每次操作能任选连续的三个数,把它们同时翻转,0 变 1、1 变 0。
一次操作 · 任选连续三个一起翻转：像这样框住连续的三个位置,一按开关,这三个数同时翻个面。有个关键想法:最左边那个 0,只有以它为左端的这一个框能翻到它,再往左没有数了。所以处理顺序只能从左往右,一个都躲不掉。
看第 0 位 · nums[0] = 0：指针走到第 0 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
框住 [0, 2] · 准备翻转：把框放在第 0 到第 2 位这三个数上。因为下标 i 加 2 等于 2,还落在数组里,框放得下,可以翻。
翻转完成 · 第 0 位变 1,操作数加一：开关一按,这三个数全翻了面。第 0 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 1 次。第 0 位从此定死是 1,指针放心往右挪。
看第 1 位 · nums[1] = 0：指针走到第 1 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
框住 [1, 3] · 准备翻转：把框放在第 1 到第 3 位这三个数上。因为下标 i 加 2 等于 3,还落在数组里,框放得下,可以翻。
翻转完成 · 第 1 位变 1,操作数加一：开关一按,这三个数全翻了面。第 1 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 2 次。第 1 位从此定死是 1,指针放心往右挪。
看第 2 位 · nums[2] = 1：指针走到第 2 位,这里已经是 1 了,不用管它,直接往右走。
看第 3 位 · nums[3] = 0：指针走到第 3 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
框住 [3, 5] · 准备翻转：把框放在第 3 到第 5 位这三个数上。因为下标 i 加 2 等于 5,还落在数组里,框放得下,可以翻。
翻转完成 · 第 3 位变 1,操作数加一：开关一按,这三个数全翻了面。第 3 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 3 次。第 3 位从此定死是 1,指针放心往右挪。
看第 4 位 · nums[4] = 1：指针走到第 4 位,这里已经是 1 了,不用管它,直接往右走。
看第 5 位 · nums[5] = 1：指针走到第 5 位,这里已经是 1 了,不用管它,直接往右走。
全部变成 1 · 答案 = 3：扫到头了,整个数组变成了 [1,1,1,1,1,1],全是 1。一路上一共动手 3 次,这就是最少操作次数,答案 3。
换一组 · [0,1,1,1] 能不能全变 1?：再看一个反例 [0,1,1,1]。只有开头一个 0,看着好像很好办,咱们按同样的规矩走一遍,看会遇到什么。
第 0 位是 0 · 框住 [0, 2] 翻转：第 0 位是 0,右边还够三个,框住第 0 到第 2 位翻转。
翻转后 · ans = 1：翻完第 0 位变成 1,可注意后面两位也被翻了,说不定又冒出新的 0,接着往下看。
第 1 位是 0 · 框住 [1, 3] 翻转：第 1 位是 0,右边还够三个,框住第 1 到第 3 位翻转。
翻转后 · ans = 2：翻完第 1 位变成 1,可注意后面两位也被翻了,说不定又冒出新的 0,接着往下看。
第 2 位是 1 · 跳过：第 2 位是 1,略过,继续往右。
第 3 位是 0 · 右边不足三个,卡住了：走到第 3 位,它还是 0,可它右边只剩不到两个数了,下标 i 加 2 等于 5,已经超出数组。没有以第 3 位为左端、长度为三的合法窗口;能盖住它的窗口都得从更左边伸过来,一翻就会破坏已经固定好的前缀,所以在保持前缀全 1 的前提下这个 0 变不成 1。
无解 · 返回 -1：所以这组数据没救,直接返回 -1。这也是判无解的唯一情形:某个 0 落在末尾不足三个的位置上,凑不出以它为左端的合法窗口,而任何盖住它的窗口都得从左边伸过来、又会翻坏已固定的前缀。
边界想清:全是 1 答案 0、[0,0,0] 一次搞定、[0,1,1,1] 翻着翻着末尾卡出无法消除的 0 返回 -1。
面试重点:每个 0 只能靠以它为左端的窗口在不破坏左侧前缀的前提下翻转所以贪心最优、右边不足三个即返回 -1、时间 O(n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minOperations(self, nums: List[int]) -> int: ans = 0 for i, x in enumerate(nums): if x == 0: if i + 2 >= len(nums): return -1 nums[i + 1] ^= 1 nums[i + 2] ^= 1 ans += 1 return ans复杂度
- 时间：O(n)，n 是数组长度。指针从左到右只走一遍,每个位置最多做一次翻转和一次判断,都是常数操作,总量随长度线性增长
- 空间：O(1)，按峰值算。直接在原数组上做异或翻转,不额外开辅助数组,只用了答案计数和下标这几个变量,占用是常数
易错点
面试追问把动画讲成自己的话
追问这题为什么能用贪心,而且一定最优?
追问怎么判断无法全部变成 1?
追问复杂度是多少,能不能优化空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题