题目描述
思路解析动画文字版
记牢:s 第 i 位的当前值 = 已翻转次数的奇偶 P。P 和 target[i] 不同就翻一次后缀、次数加 1;相同就跳过。一遍扫到底,翻转次数即答案。
总览 · 目标串 + 初始全 0 的 s：先看清画面。上面这排格子是 target = "1,0,1,1,1,0,1,0",一共 8 位。你手里的 s 现在是一串 0,要靠不停翻后缀把它修成 target。右边面板记两件事:已经翻了多少次,以及当前位的奇偶 P,现在都是 0。我们让紫色指针从最左边第 0 位开始,一位一位往右修。
起点 · 还没翻过,s 全是 0：开工前先想通一件事。s 一开始全是 0,也就是说,在还没动手的此刻,每一位的当前值都是 0,奇偶 P 等于 0。我们要做的,就是从左往右让 s 的每一位依次追上 target。判断某一位要不要翻,只看它现在的值 P 和 target 这一位是否一致。指针落在第 0 位,准备开始第一次比较。
第 0 位 · 比一比：看第 0 位。此刻已经翻了 0 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 0。而 target 这一位要的是 1。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
第 0 位 · 翻一次：不同就得翻。我们从第 0 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 1,对上了,标成绿色。翻转次数从 0 变成 1。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 1 自动反映出来,不用我们单独记。
第 1 位 · 比一比：看第 1 位。此刻已经翻了 1 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 0。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
第 1 位 · 翻一次：不同就得翻。我们从第 1 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 0,对上了,标成绿色。翻转次数从 1 变成 2。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 0 自动反映出来,不用我们单独记。
第 2 位 · 比一比：看第 2 位。此刻已经翻了 2 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 0。而 target 这一位要的是 1。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
第 2 位 · 翻一次：不同就得翻。我们从第 2 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 1,对上了,标成绿色。翻转次数从 2 变成 3。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 1 自动反映出来,不用我们单独记。
第 3 位 · 比一比：看第 3 位。此刻已经翻了 3 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 1。两个值一样,说明这一位早就对上了,等会儿直接跳过就行。
第 3 位 · 跳过：一样就什么都不做。这一位保持原状已经等于 1,标成蓝色表示已确认对上。翻转次数仍然是 3,奇偶 P 也没变。省下的这一次,正是贪心扫描的便宜之处:相邻两位相同时根本不必动手。
第 4 位 · 比一比：看第 4 位。此刻已经翻了 3 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 1。两个值一样,说明这一位早就对上了,等会儿直接跳过就行。
第 4 位 · 跳过：一样就什么都不做。这一位保持原状已经等于 1,标成蓝色表示已确认对上。翻转次数仍然是 3,奇偶 P 也没变。省下的这一次,正是贪心扫描的便宜之处:相邻两位相同时根本不必动手。
第 5 位 · 比一比：看第 5 位。此刻已经翻了 3 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 0。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
第 5 位 · 翻一次：不同就得翻。我们从第 5 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 0,对上了,标成绿色。翻转次数从 3 变成 4。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 0 自动反映出来,不用我们单独记。
第 6 位 · 比一比：看第 6 位。此刻已经翻了 4 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 0。而 target 这一位要的是 1。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
第 6 位 · 翻一次：不同就得翻。我们从第 6 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 1,对上了,标成绿色。翻转次数从 4 变成 5。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 1 自动反映出来,不用我们单独记。
第 7 位 · 比一比：看第 7 位。此刻已经翻了 5 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 0。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
第 7 位 · 翻一次：不同就得翻。我们从第 7 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 0,对上了,标成绿色。翻转次数从 5 变成 6。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 0 自动反映出来,不用我们单独记。
回收 · 数一数翻过几次：八位全部走完。回头看,标成绿色的是真正动手翻过的位置,下标是 0、1、2、5、6、7,一共 6 个;标成蓝色的第 3、4 位是相邻相同、直接跳过的。把绿色的个数加起来,就是最少翻转次数 6。
换个角度 · 数相邻变化点：其实有个更快的口算法。把 target 想成前面还垫了一个虚拟的 0,因为 s 起步就是全 0。从这个虚拟 0 开始,沿着 "1,0,1,1,1,0,1,0" 一路看相邻两位:只要值发生了一次变化,就对应一次翻转。第 0 位是 1,和前面的虚拟 0 不同,记一次;接着 1 到 0、0 到 1 各一次;中间 1 到 1、1 到 1 没变化,不记;后面 1 到 0、0 到 1、1 到 0 又各一次。数下来正好 6 次,和逐位贪心的结果完全一致。
完成 · 最少翻转次数 = 6：收个尾。整道题不用真的去模拟每次后缀翻转,只要从左往右扫一遍,维护一个奇偶 P,P 和当前目标位不同就计一次翻转、并翻转 P。target = "10111010" 一路下来累计 6 次,这就是答案。线性时间,额外只用一个计数器,既快又省。
边界:全 0 答案为 0;以 1 开头第一位必翻;一段连续相同的位只在开头算一次翻转,后面同值的全跳过。
面试重点:翻后缀不动左边、每步唯一最优所以贪心成立;用 ans 最低位当奇偶免去存 s;逐位贪心等价于数 target 相邻变化点(含与虚拟前导 0 比)。
参考代码
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 minFlips(self, target: str) -> int: ans = 0 for v in target: if (ans & 1) ^ int(v): ans += 1 return ans复杂度
- 时间：O(n)，n 是字符串长度。只从左到右扫一遍,每一位做的是一次取最低位、一次异或、最多一次加法,全是常数操作,总共 n 次,所以是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。关键是没有去真的模拟每一次后缀翻转,否则单次翻转就是 O(n)、整体退化成 O(n 的平方)
- 空间：O(1)，按峰值算。整个过程只用了一个整数 ans 当计数器兼奇偶标记,再加遍历用的字符或下标,都是常数个变量,不随 n 增长,所以额外空间是常数 O(1)。三种语言都不需要额外开数组或拷贝字符串
易错点
面试追问把动画讲成自己的话
追问这题为什么能贪心,逐位定下来不会后悔吗?
追问不维护字符串 s,怎么知道当前这一位到底是几?
追问把它说成「数相邻变化点」和逐位贪心是一回事吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
得到目标数组的最少函数调用次数
LeetCode 1558 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题