题目描述
思路解析动画文字版
记牢:轮转 = 在两倍长串上滑长度 n 的窗口;铺固定标尺 0101…,红 = 和标尺不同的位数 = 改成标尺那种交替的反转数,绿 = n 减红 = 改成另一种交替的反转数。每个旋转取 min(红,绿),全局取最小。
第 1 步 · 把 s 接成两倍长：先动手准备。把 s = "11100" 复制一份接在自己后面,拼成一个两倍长的串 "1110011100",一共十个格子。为什么要拼两倍?因为轮转就是把开头的字符搬到末尾,在这个两倍长的串上,一个长度为 5 的窗口从左滑到右,依次框住的正好就是 s 的每一种轮转。现在整排先都灰着,还没开始比。
第 2 步 · 铺固定标尺 0101010101：再铺一把固定的标尺 "0101010101",按位置摆:偶数位要 0、奇数位要 1。把两倍长串每个格子和它正下方的标尺比一比,不同的标红,相同的标绿。红色格子就是「想让这段贴合标尺那种交替」必须反转的位;绿色格子是已经对上标尺的位。等会儿窗口框到哪儿,我们就只数窗口里的红和绿,窗口外的先不管。
旋转 0 · 窗口框住 [0,4]：让长度为 5 的窗口先框住最左边的 [0,4],这段就是原串 "11100" 本身,也就是「一次都不轮转」的那种情况。窗口外的格子先灰掉、不参与计数。第一个旋转我们一格一格仔细比,后面几个就能靠增量偷懒了。
旋转 0 · 逐格比对第 0 格：看第 0 格,它是 "1",正下方标尺要的是 "0"。两个不一样,标红,累计红到 1 个。继续看下一格。
旋转 0 · 逐格比对第 1 格：看第 1 格,它是 "1",正下方标尺要的是 "1"。两个一样,标绿,红仍是 1 个。继续看下一格。
旋转 0 · 逐格比对第 2 格：看第 2 格,它是 "1",正下方标尺要的是 "0"。两个不一样,标红,累计红到 2 个。继续看下一格。
旋转 0 · 逐格比对第 3 格：看第 3 格,它是 "0",正下方标尺要的是 "1"。两个不一样,标红,累计红到 3 个。继续看下一格。
旋转 0 · 逐格比对第 4 格：看第 4 格,它是 "0",正下方标尺要的是 "0"。两个一样,标绿,红仍是 3 个。五格比完,红一共 3 个。
旋转 0 · 绿 = 2,最优 = 2：红数完是 3,绿就是 n 减红,5 减 3 等于 2。绿的含义是:把这段改成「另一种交替串 10101」要反转 2 位。一个旋转的最优,就是红和绿里较小的那个,min(3,2) 等于 2。这是第一个旋转,先把全局最少 ans 记成 2,后面看能不能更小。
旋转 1 · 窗口滑到 [1,5]：窗口向右滑一格,来到 [1,5]。这一格代表把开头轮转掉 1 次后的串 "11001"。滑动时,原来在窗口头部第 0 格的字符离开了,末尾第 5 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 1 · 增量算红 = 2：增量更新红。离开的第 0 格有和标尺不同,所以红减 1;新进来的第 5 格没和标尺不同,红加 0。上一个窗口红是 3,这样一减一加,现在红是 2。只动两格、常数时间,这就是滑窗省力的地方。
旋转 1 · 最优 2 → ans 2：绿是 5 减 2 等于 3,这个旋转的最优 min(2,3) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
旋转 2 · 窗口滑到 [2,6]：窗口向右滑一格,来到 [2,6]。这一格代表把开头轮转掉 2 次后的串 "10011"。滑动时,原来在窗口头部第 1 格的字符离开了,末尾第 6 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 2 · 增量算红 = 3：增量更新红。离开的第 1 格没和标尺不同,所以红减 0;新进来的第 6 格有和标尺不同,红加 1。上一个窗口红是 2,这样一减一加,现在红是 3。只动两格、常数时间,这就是滑窗省力的地方。
旋转 2 · 最优 2 → ans 2：绿是 5 减 3 等于 2,这个旋转的最优 min(3,2) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
旋转 3 · 窗口滑到 [3,7]：窗口向右滑一格,来到 [3,7]。这一格代表把开头轮转掉 3 次后的串 "00111"。滑动时,原来在窗口头部第 2 格的字符离开了,末尾第 7 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 3 · 增量算红 = 2：增量更新红。离开的第 2 格有和标尺不同,所以红减 1;新进来的第 7 格没和标尺不同,红加 0。上一个窗口红是 3,这样一减一加,现在红是 2。只动两格、常数时间,这就是滑窗省力的地方。
旋转 3 · 最优 2 → ans 2：绿是 5 减 2 等于 3,这个旋转的最优 min(2,3) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
旋转 4 · 窗口滑到 [4,8]：窗口向右滑一格,来到 [4,8]。这一格代表把开头轮转掉 4 次后的串 "01110"。滑动时,原来在窗口头部第 3 格的字符离开了,末尾第 8 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 4 · 增量算红 = 1：增量更新红。离开的第 3 格有和标尺不同,所以红减 1;新进来的第 8 格没和标尺不同,红加 0。上一个窗口红是 2,这样一减一加,现在红是 1。只动两格、常数时间,这就是滑窗省力的地方。
旋转 4 · 最优 1 → ans 1：绿是 5 减 1 等于 4,这个旋转的最优 min(1,4) 等于 1。它比之前记的全局最少更小,于是把 ans 刷新成 1,我们找到了一种更省的旋转。
收束 · 最省旋转红 = 1：五个旋转全滑完。最省的落在窗口 [4,8],这段是 "01110",它和标尺只差 1 个红格,也就是只要反转 1 位就能变成交替串。全局最少 ans 就此定格在 1。
收束 · 反转 1 位 → 交替串：把最后那一个红格,第 6 格反转过来,这段就整整齐齐贴上了标尺,变成交替串 "01010"。全程只反转了 1 次,这就是答案。回头看,我们没有真的去反复轮转和重数,只是在两倍长串上滑一遍窗口、增量维护红值,线性时间就把最少反转数锁死了。
边界:本身交替答案为 0;偶数长度轮转不改变结果,只看原串 min(红,绿);"1110" 取绿 1、"0100" 取红 1,都是反转一位就成交替。
面试重点:两倍长串上滑长度 n 的窗口覆盖全部轮转;交替串只有两种,每个旋转取 min(红,绿)、绿 = n 减红;偶数长度轮转不改变答案,奇数长度才靠滑窗找更优,代码统一处理仍正确。
参考代码
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, 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 ans复杂度
- 时间：O(n)，n 是串长。第一遍数红扫一遍 O(n);第二遍模拟轮转也是 n 步,每步只做一减一加两次常数操作、再取一次最小,所以整体是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。关键是轮转后红值靠增量更新,绝不每换一个旋转就把整段重数一遍,否则会退化成 O(n 的平方)
- 空间：O(1)，按峰值算。只用了红值计数器 cnt 和答案 ans 两个整数,外加标尺常量 "01",都是常数个变量,不随 n 增长。注意「两倍长串」只是讲解用的思维模型,参考代码并不真的把串拼长,而是用下标对 2 取模的方式访问,所以额外空间是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么把 s 复制成两倍长,就能覆盖所有轮转?
追问为什么每个旋转要和固定标尺比、还要取 min(红,绿)?
追问奇数长度和偶数长度处理上有什么不同?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大交替子序列和
LeetCode 1911 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题