最少的后缀翻转次数 图解题解
这道题到底在问什么
- 输入
- target="10111"
- 输出
- 3
- 输入
- target="101"
- 输出
- 3
- 输入
- target="00000"
- 输出
- 0
最优解：一步一步想明白
- 3记牢:s 第 i 位的当前值 = 已翻转次数的奇偶 P。P 和 target[i] 不同就翻一次后缀、次数加 1;相同就跳过。一遍扫到底,翻转次数即答案。
- 4先看清画面。上面这排格子是 target = "1,0,1,1,1,0,1,0",一共 8 位。你手里的 s 现在是一串 0,要靠不停翻后缀把它修成 target。右边面板记两件事:已经翻了多少次,以及当前位的奇偶 P,现在都是 0。我们让紫色指针从最左边第 0 位开始,一位一位往右修。
- 5开工前先想通一件事。s 一开始全是 0,也就是说,在还没动手的此刻,每一位的当前值都是 0,奇偶 P 等于 0。我们要做的,就是从左往右让 s 的每一位依次追上 target。判断某一位要不要翻,只看它现在的值 P 和 target 这一位是否一致。指针落在第 0 位,准备开始第一次比较。
- 6看第 0 位。此刻已经翻了 0 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 0。而 target 这一位要的是 1。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
- 7不同就得翻。我们从第 0 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 1,对上了,标成绿色。翻转次数从 0 变成 1。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 1 自动反映出来,不用我们单独记。
- 8看第 1 位。此刻已经翻了 1 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 0。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
- 9不同就得翻。我们从第 1 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 0,对上了,标成绿色。翻转次数从 1 变成 2。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 0 自动反映出来,不用我们单独记。
- 10看第 2 位。此刻已经翻了 2 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 0。而 target 这一位要的是 1。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
- 11不同就得翻。我们从第 2 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 1,对上了,标成绿色。翻转次数从 2 变成 3。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 1 自动反映出来,不用我们单独记。
- 12看第 3 位。此刻已经翻了 3 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 1。两个值一样,说明这一位早就对上了,等会儿直接跳过就行。
- 13一样就什么都不做。这一位保持原状已经等于 1,标成蓝色表示已确认对上。翻转次数仍然是 3,奇偶 P 也没变。省下的这一次,正是贪心扫描的便宜之处:相邻两位相同时根本不必动手。
- 14看第 4 位。此刻已经翻了 3 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 1。两个值一样,说明这一位早就对上了,等会儿直接跳过就行。
- 15一样就什么都不做。这一位保持原状已经等于 1,标成蓝色表示已确认对上。翻转次数仍然是 3,奇偶 P 也没变。省下的这一次,正是贪心扫描的便宜之处:相邻两位相同时根本不必动手。
- 16看第 5 位。此刻已经翻了 3 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 0。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
- 17不同就得翻。我们从第 5 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 0,对上了,标成绿色。翻转次数从 3 变成 4。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 0 自动反映出来,不用我们单独记。
- 18看第 6 位。此刻已经翻了 4 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 0。而 target 这一位要的是 1。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
- 19不同就得翻。我们从第 6 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 1,对上了,标成绿色。翻转次数从 4 变成 5。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 1 自动反映出来,不用我们单独记。
- 20看第 7 位。此刻已经翻了 5 次,所以 s 这一位的值就是这个次数的奇偶 P 等于 1。而 target 这一位要的是 0。两个值不一样,说明这一位还没对上,得想办法把它翻过来。
- 21不同就得翻。我们从第 7 位起,把这一位到末尾的整段后缀全部取反,这一位立刻变成 0,对上了,标成绿色。翻转次数从 5 变成 6。注意后面那些位也跟着被翻了,但没关系,它们的新状态会在轮到它们时由更新后的奇偶 P 等于 0 自动反映出来,不用我们单独记。
- 22八位全部走完。回头看,标成绿色的是真正动手翻过的位置,下标是 0、1、2、5、6、7,一共 6 个;标成蓝色的第 3、4 位是相邻相同、直接跳过的。把绿色的个数加起来,就是最少翻转次数 6。
- 23其实有个更快的口算法。把 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 次,和逐位贪心的结果完全一致。
- 24收个尾。整道题不用真的去模拟每次后缀翻转,只要从左往右扫一遍,维护一个奇偶 P,P 和当前目标位不同就计一次翻转、并翻转 P。target = "10111010" 一路下来累计 6 次,这就是答案。线性时间,额外只用一个计数器,既快又省。
⚠️ 容易写错的地方
✗ 错：老老实实模拟:每次真把后缀整段取反一遍
✓ 对：只维护已翻次数的奇偶 P,逐位判断要不要计一次
每翻一次后缀就是一趟 O(n) 的扫描,最坏要翻 O(n) 次,整体 O(n 的平方),n 到 10 的 5 次方会超时。其实第 i 位的当前值完全由之前翻转次数的奇偶决定,根本不必真翻,O(n) 一遍扫描就够
✗ 错：忘了开头那一位:以为第 0 位前面没有可比的
✓ 对：把 target 看成前面垫了一个虚拟的 0(因为 s 起步全 0)
第 0 位也要判断:此刻 P 等于 0,若 target[0] 是 1 就得翻一次。等价于和虚拟前导 0 比较。漏掉它会在 target 以 1 开头时少算一次
✗ 错：另设一个 P 变量,加 1 后忘了同步翻转 P
✓ 对：直接用 ans 的最低位当 P,ans 加 1 自动更新奇偶
ans 每加 1,它的最低位就翻一次,正好等于「又翻了一次后缀,奇偶取反」。复用 ans 的最低位既省一个变量,也避免忘记同步两者导致后面全错
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minFlips(string target) {
int ans = 0;
for (char c : target) {
int v = c - '0';
if ((ans & 1) ^ v) {
++ans;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minFlips(String target) {
int ans = 0;
for (int i = 0; i < target.length(); ++i) {
int v = target.charAt(i) - '0';
if (((ans & 1) ^ v) != 0) {
++ans;
}
}
return ans;
}
}复杂度
时间
O(n)
n 是字符串长度。只从左到右扫一遍,每一位做的是一次取最低位、一次异或、最多一次加法,全是常数操作,总共 n 次,所以是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。关键是没有去真的模拟每一次后缀翻转,否则单次翻转就是 O(n)、整体退化成 O(n 的平方)
空间
O(1)
按峰值算。整个过程只用了一个整数 ans 当计数器兼奇偶标记,再加遍历用的字符或下标,都是常数个变量,不随 n 增长,所以额外空间是常数 O(1)。三种语言都不需要额外开数组或拷贝字符串
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最少的后缀翻转次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么能贪心,逐位定下来不会后悔吗?+
不会。因为每次翻的是后缀,只会影响当前位和它右边的位,绝不会动到左边已经修好的位。我们从左往右处理,一旦把第 i 位修对,后面的操作都从更靠右的下标开始,左边纹丝不动。而要让第 i 位对上,此刻有且只有一个选择:不同就必须翻、相同就必然不翻,没有别的余地。每一步都是被逼出来的唯一最优解,所以逐位贪心既正确又不会反悔。
不维护字符串 s,怎么知道当前这一位到底是几?+
靠奇偶。因为之前每一次后缀翻转都覆盖了当前位,而 s 起步是 0,所以当前位的值就等于到目前为止翻转次数的奇偶:偶数次还是 0,奇数次是 1。我们用计数器 ans 的最低位来表示这个奇偶,完全不需要真的存一份 s,也不需要真去翻转,省时又省空间。
把它说成「数相邻变化点」和逐位贪心是一回事吗?+
是同一件事的两种说法。逐位贪心里,第 i 位要翻,当且仅当它的目标值和前一位的目标值不同,因为修完前一位后当前奇偶恰好等于前一位的目标值。第 0 位则是和虚拟前导 0 比。把这些「相邻不同」的位置数出来,就是翻转次数。所以你可以一行写循环判断奇偶,也可以直接数 target 里相邻字符不同的次数,结果完全一样。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最少的后缀翻转次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。