使二进制字符串字符交替的最少反转次数 图解题解
这道题到底在问什么
- 输入
- s="111000"
- 输出
- 2
- 输入
- s="010"
- 输出
- 0
- 输入
- s="1110"
- 输出
- 1
最优解：一步一步想明白
- 3记牢:轮转 = 在两倍长串上滑长度 n 的窗口;铺固定标尺 0101…,红 = 和标尺不同的位数 = 改成标尺那种交替的反转数,绿 = n 减红 = 改成另一种交替的反转数。每个旋转取 min(红,绿),全局取最小。
- 4先动手准备。把 s = "11100" 复制一份接在自己后面,拼成一个两倍长的串 "1110011100",一共十个格子。为什么要拼两倍?因为轮转就是把开头的字符搬到末尾,在这个两倍长的串上,一个长度为 5 的窗口从左滑到右,依次框住的正好就是 s 的每一种轮转。现在整排先都灰着,还没开始比。
- 5再铺一把固定的标尺 "0101010101",按位置摆:偶数位要 0、奇数位要 1。把两倍长串每个格子和它正下方的标尺比一比,不同的标红,相同的标绿。红色格子就是「想让这段贴合标尺那种交替」必须反转的位;绿色格子是已经对上标尺的位。等会儿窗口框到哪儿,我们就只数窗口里的红和绿,窗口外的先不管。
- 6让长度为 5 的窗口先框住最左边的 [0,4],这段就是原串 "11100" 本身,也就是「一次都不轮转」的那种情况。窗口外的格子先灰掉、不参与计数。第一个旋转我们一格一格仔细比,后面几个就能靠增量偷懒了。
- 7看第 0 格,它是 "1",正下方标尺要的是 "0"。两个不一样,标红,累计红到 1 个。继续看下一格。
- 8看第 1 格,它是 "1",正下方标尺要的是 "1"。两个一样,标绿,红仍是 1 个。继续看下一格。
- 9看第 2 格,它是 "1",正下方标尺要的是 "0"。两个不一样,标红,累计红到 2 个。继续看下一格。
- 10看第 3 格,它是 "0",正下方标尺要的是 "1"。两个不一样,标红,累计红到 3 个。继续看下一格。
- 11看第 4 格,它是 "0",正下方标尺要的是 "0"。两个一样,标绿,红仍是 3 个。五格比完,红一共 3 个。
- 12红数完是 3,绿就是 n 减红,5 减 3 等于 2。绿的含义是:把这段改成「另一种交替串 10101」要反转 2 位。一个旋转的最优,就是红和绿里较小的那个,min(3,2) 等于 2。这是第一个旋转,先把全局最少 ans 记成 2,后面看能不能更小。
- 13窗口向右滑一格,来到 [1,5]。这一格代表把开头轮转掉 1 次后的串 "11001"。滑动时,原来在窗口头部第 0 格的字符离开了,末尾第 5 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
- 14增量更新红。离开的第 0 格有和标尺不同,所以红减 1;新进来的第 5 格没和标尺不同,红加 0。上一个窗口红是 3,这样一减一加,现在红是 2。只动两格、常数时间,这就是滑窗省力的地方。
- 15绿是 5 减 2 等于 3,这个旋转的最优 min(2,3) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
- 16窗口向右滑一格,来到 [2,6]。这一格代表把开头轮转掉 2 次后的串 "10011"。滑动时,原来在窗口头部第 1 格的字符离开了,末尾第 6 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
- 17增量更新红。离开的第 1 格没和标尺不同,所以红减 0;新进来的第 6 格有和标尺不同,红加 1。上一个窗口红是 2,这样一减一加,现在红是 3。只动两格、常数时间,这就是滑窗省力的地方。
- 18绿是 5 减 3 等于 2,这个旋转的最优 min(3,2) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
- 19窗口向右滑一格,来到 [3,7]。这一格代表把开头轮转掉 3 次后的串 "00111"。滑动时,原来在窗口头部第 2 格的字符离开了,末尾第 7 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
- 20增量更新红。离开的第 2 格有和标尺不同,所以红减 1;新进来的第 7 格没和标尺不同,红加 0。上一个窗口红是 3,这样一减一加,现在红是 2。只动两格、常数时间,这就是滑窗省力的地方。
- 21绿是 5 减 2 等于 3,这个旋转的最优 min(2,3) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
- 22窗口向右滑一格,来到 [4,8]。这一格代表把开头轮转掉 4 次后的串 "01110"。滑动时,原来在窗口头部第 3 格的字符离开了,末尾第 8 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
- 23增量更新红。离开的第 3 格有和标尺不同,所以红减 1;新进来的第 8 格没和标尺不同,红加 0。上一个窗口红是 2,这样一减一加,现在红是 1。只动两格、常数时间,这就是滑窗省力的地方。
- 24绿是 5 减 1 等于 4,这个旋转的最优 min(1,4) 等于 1。它比之前记的全局最少更小,于是把 ans 刷新成 1,我们找到了一种更省的旋转。
- 25五个旋转全滑完。最省的落在窗口 [4,8],这段是 "01110",它和标尺只差 1 个红格,也就是只要反转 1 位就能变成交替串。全局最少 ans 就此定格在 1。
- 26把最后那一个红格,第 6 格反转过来,这段就整整齐齐贴上了标尺,变成交替串 "01010"。全程只反转了 1 次,这就是答案。回头看,我们没有真的去反复轮转和重数,只是在两倍长串上滑一遍窗口、增量维护红值,线性时间就把最少反转数锁死了。
⚠️ 容易写错的地方
✗ 错：每换一个旋转,就把整段和标尺从头重数一遍
✓ 对：轮转只让头尾各变一格,红值一减一加增量更新
从头重数每次 O(n),n 种旋转就是 O(n 的平方),n 到 10 的 5 次方会超时。滑窗里离开一格、进来一格,只需在上次红值上减去离开格的贡献、加上进来格的贡献,常数时间搞定,整体 O(n)
✗ 错：只和一种交替串比,只数了红就当答案
✓ 对：每个旋转有两种目标,取 min(红, 绿),绿 = n 减红
交替串有 "0101…" 和 "1010…" 两副长相。红是改成标尺那种要几次,绿 = n 减红是改成另一种要几次。只数红会漏掉「改成另一种更省」的情况,必须两者取小
✗ 错：不分奇偶,以为轮转对任何长度都可能更省
✓ 对：偶数长度轮转不降低答案,红值恒定,答案就看原串
长度为偶数时,固定标尺滑窗里离开的那一格和新进来的那一格,在两倍长串上相差 n 个位置,n 是偶数、这两处标尺值相同,同一个字符一进一出贡献正好抵消,红值滑一圈都不变,答案直接是原串的 min(红,绿)。换个角度看,偶数长度旋转一格会让本地串里两种交替模板互换、红绿对调,min 不变。只有奇数长度轮转才会真正改变红值、可能找到更省的旋转。想清这点能避免在偶数串上白算,也能理解代码为何统一处理仍正确
完整代码（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, s: str) -> int:
n = len(s)
target = "01"
cnt = sum(c != target[i & 1] for i, c in enumerate(s))
ans = min(cnt, n - cnt)
for i in range(n):
cnt -= s[i] != target[i & 1]
cnt += s[i] != target[(i + n) & 1]
ans = min(ans, cnt, n - cnt)
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 s) {
int n = s.size();
string target = "01";
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (s[i] != target[i & 1]) {
++cnt;
}
}
int ans = min(cnt, n - cnt);
for (int i = 0; i < n; ++i) {
if (s[i] != target[i & 1]) {
--cnt;
}
if (s[i] != target[(i + n) & 1]) {
++cnt;
}
ans = min({ans, cnt, n - cnt});
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minFlips(String s) {
int n = s.length();
String target = "01";
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (s.charAt(i) != target.charAt(i & 1)) {
++cnt;
}
}
int ans = Math.min(cnt, n - cnt);
for (int i = 0; i < n; ++i) {
if (s.charAt(i) != target.charAt(i & 1)) {
--cnt;
}
if (s.charAt(i) != target.charAt((i + n) & 1)) {
++cnt;
}
ans = Math.min(ans, Math.min(cnt, n - cnt));
}
return ans;
}
}复杂度
时间
O(n)
n 是串长。第一遍数红扫一遍 O(n);第二遍模拟轮转也是 n 步,每步只做一减一加两次常数操作、再取一次最小,所以整体是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。关键是轮转后红值靠增量更新,绝不每换一个旋转就把整段重数一遍,否则会退化成 O(n 的平方)
空间
O(1)
按峰值算。只用了红值计数器 cnt 和答案 ans 两个整数,外加标尺常量 "01",都是常数个变量,不随 n 增长。注意「两倍长串」只是讲解用的思维模型,参考代码并不真的把串拼长,而是用下标对 2 取模的方式访问,所以额外空间是常数 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使二进制字符串字符交替的最少反转次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么把 s 复制成两倍长,就能覆盖所有轮转?+
因为轮转是把开头的字符搬到末尾,做 k 次轮转得到的串,恰好等于 s 接上 s 之后、从第 k 个位置起连续取 n 个字符。所以在两倍长的串上,让一个长度为 n 的窗口从下标 0 滑到下标 n 减 1,窗口每停一处就对应一种轮转,n 处正好覆盖全部 n 种轮转,不用真的一次次去搬字符重排。
为什么每个旋转要和固定标尺比、还要取 min(红,绿)?+
因为长度确定后,交替串只有两种:以 0 开头的 "0101…" 和以 1 开头的 "1010…"。我们铺的标尺就是其中一种。窗口里和标尺不同的位数是红,等于把这段改成标尺那种交替要反转几次;和标尺相同的位数是绿,等于 n 减红,正好是改成另一种交替要几次。这个旋转能达到的最省,自然是红和绿里较小的那个。
奇数长度和偶数长度处理上有什么不同?+
偶数长度时,固定标尺滑窗里离开位和进入位在两倍长串上相差 n 个位置,n 是偶数、两处标尺值相同,同一个字符一进一出贡献抵消,红值滑一圈都不变,所以答案就是原串的 min(红,绿),轮转帮不上忙;等价地说,偶数长度旋转一格会让两种交替模板互换、红绿对调,min 不变。奇数长度时,离开位与进入位标尺值相反,不同旋转的红值会变化,才需要滑窗把每个旋转都比一遍取最小。参考代码对两种情况统一用滑窗处理,偶数时滑窗值恒定、结果自然正确。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使二进制字符串字符交替的最少反转次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。