企业官网建设流程全解析

刷题的朋友对 1888 这个编号应该不陌生，这道题名字很直白：给定一个二进制字符串，你可以反复做两种操作，一种是让字符串做循环移位，另一种是翻转某个字符，问最少翻转多少次能让它变成交替字符串。第一次看到容易懵，因为“旋转”和“翻转”混在一起，好像既要考虑最终串长什么样，又要考虑每次操作会不会互相影响。实际上把模型拆开之后，这就是一个非常经典的“环形匹配 + 滑动窗口”问题，核心套路在很多竞赛题里都能复用。

我先把结论放前面：任意次循环移位等价于枚举原串的所有循环同构；而最终要变成的交替串只有两种，分别是010101...和101010...。所以问题可以转化为：对于每一种旋转结果，计算它和这两个目标模式的汉明距离（也就是有几个位置不一样），取最小值。直接做是 O(n^2)，但通过把字符串复制一份变成双倍串，再配合前缀和或者滑动窗口，可以在 O(n) 时间内解决。今天就按这个思路一步步拆开讲，顺便把容易踩的坑都列出来。

1. 题目到底在说什么：先建模再动手

1.1 两种操作的真实含义

题目里的第一种操作是“循环左移”，也就是把最左侧的字符挪到最右侧。这个操作可以做任意多次，所以本质上你能拿到的状态就是原始字符串的所有循环同构。举个例子，1100循环左移一次变成1001，左移两次变成0011，左移三次变成0110，四次又回到1100。

第二种操作是翻转单个字符，把一个位置的0变1，或者1变0。这个操作显然会改变字符串本身，但不是一次改一整段，只改一个位置。

问题问的是“最少翻转次数”，注意不是最少操作次数。旋转不算代价，只有翻转算代价。这就很重要了：你可以放心大胆地随便旋转，真正要优化的是“旋转之后，需要翻转多少个位置才能变成交替串”。

1.2 为什么可以把操作顺序拆开

一个常见的疑问是：如果我先翻转某个字符，再旋转，那翻转的位置不就会跟着一起动吗？这个确实会动，但不影响我们建模。

你可以这样想：任何操作序列都可以重新排列成“先完成所有旋转，再做所有翻转”。因为旋转只是把字符的位置整体换了，而翻转是针对某个相对位置的字符。先翻转再旋转，等价于先旋转再翻转对应位置的字符。举个例子，s[2]翻转之后，整体左移一次，原来在位置 2 的字符会跑到位置 1；反过来，先左移一次再翻转位置 1，最终效果一样，翻转次数也完全一样。

既然旋转不花代价，那么我们直接把所有可能的旋转结果都看一遍，然后计算每个结果和交替模式的最小汉明距离，这个最小值就是答案。

1.3 最终状态的数学表达

交替字符串只有两种大方向：以0开头，或者以1开头。用公式写就是：

• T0 =010101...
• T1 =101010...

注意，旋转后的交替串并不一定非得从0开头。比如1010本身也是交替串，它是从1开头的。所以在枚举旋转结果的时候，要同时考虑 T0 和 T1 这两种模式。

假设某个旋转后的字符串是 W，长度为 n。那么它变成交替串的最小翻转次数就是：

min(W 与 T0 的不同位数, W 与 T1 的不同位数)

这个“不同位数”在算法里有一个专门的名字，叫汉明距离。我们的问题就变成了：在所有循环同构里，找汉明距离最小的那个。

2. 一个关键洞察：双倍串与滑动窗口

2.1 旋转状态怎么枚举

最朴素的做法是：枚举 k 从 0 到 n-1，把字符串左移 k 次，得到一个新串，再和 T0、T1 比较一遍。比较一次需要 O(n)，枚举 n 次就是 O(n^2)，在 n 到 10^5 级别时会直接超时。

优化思路很经典：把原串复制一份拼在后面，得到s + s，那么从某个位置 k 开始、长度为 n 的子串，恰好就是原串左移 k 次之后的结果。

s = "1100" s + s = "11001100" 从位置 1 取长度为 4 的子串 = "1001" 这个就是 "1100" 左移一次的结果

这样我们就不需要真的去移动字符，只需要在双倍串上滑一个长度为 n 的窗口。

2.2 为什么只比对一种交替模式就够了

你可能觉得要比较两种模式，工作量要翻倍。但其实不需要。

看 T0 和 T1 的关系：T1 就是 T0 整体取反。也就是说，任意一个字符如果和 T0 相同，就一定和 T1 不同；如果和 T0 不同，就一定和 T1 相同。因为二进制只有0和1两种情况。

所以，对于一个长度为 n 的窗口，如果它和 T0 的差异是 d，那么它和 T1 的差异一定是 n - d。

再想深一层：我们比较窗口的时候，不是把窗口和区间从 0 开始的 T0 比，而是和双倍串上对应位置的 T0 子串比。因为 T0 本身是周期为 2 的串，所以从奇数位置开始的 T0 子串其实就成了以1开头的交替串。举个例子：

T0 = 01010101... 从位置 1 开始取 4 个字符 = 1010，正好是以 1 开头的交替模式

只要一个周期模式 T0 就覆盖了所有旋转后的起点情况，T1 的答案可以通过 n - d 拿到。这样代码简单一半。

2.3 失配数组与窗口和

为了快速计算窗口差异，我们可以先定义一个失配数组 A：

A[i] = 1 表示双倍串第 i 个字符和 T0[i] 不一致 A[i] = 0 表示一致

那么从 k 开始的长度为 n 的窗口，和 T0 的差异 d_k 就等于：

d_k = A[k] + A[k+1] + ... + A[k+n-1]

接下来就是经典的区间和问题。可以用前缀和，也可以用滑动窗口。

3. 最容易写对的解法：前缀和

3.1 失配数组怎么构造

假设双倍串是S = s + s，长度为 2n。T0 的第 i 个字符只取决于 i 的奇偶性：

如果 i 是偶数，T0[i] = '0' 如果 i 是奇数，T0[i] = '1'

于是失配数组可以这样生成：

n = len(s) total = 2 * n diff = [0] * total for i in range(total): target = '0' if i % 2 == 0 else '1' diff[i] = int(s[i % n] != target)

这里用i % n取原串字符，就等价于在双倍串上的取值，不需要真的创建s + s那么大的字符串。不过为了让思路更直观，很多选手也会直接写S = s + s，再用S[i]，效果一样。

3.2 前缀和计算窗口差异

有了失配数组，再用一个前缀和数组pref存累加值：

pref[0] = 0 pref[i + 1] = pref[i] + diff[i]

那么区间[start, start + n - 1]的差异就是：

d = pref[start + n] - pref[start]

枚举 start 从 0 到 n-1，取min(d, n - d)的最小值即可。这里取min(d, n - d)就是在 T0 和 T1 之间选更划算的那个。

3.3 完整参考代码（Python）

class Solution: def minFlips(self, s: str) -> int: n = len(s) total = 2 * n diff = [0] * total for i in range(total): target = '0' if i % 2 == 0 else '1' diff[i] = int(s[i % n] != target) pref = [0] * (total + 1) for i in range(total): pref[i + 1] = pref[i] + diff[i] ans = n for start in range(n): d = pref[start + n] - pref[start] ans = min(ans, d, n - d) return ans

这段代码的时间复杂度是 O(n)，因为构建 diff 和 pref 各循环了 2n 次，枚举窗口又循环了 n 次。空间复杂度也是 O(n)，主要花在 diff 和 pref 这两个数组上。

3.4 复杂度分析

如果你面试或者笔试的时候被问复杂度，可以这样说：双倍串的长度是 2n，数组构建和前缀和构建都是 O(n)，枚举 n 个窗口每次 O(1) 求结果，所以总时间是 O(n)。空间上因为存了长度为 2n 的失配数组和前缀和数组，是 O(n)。

这个复杂度在 O(n^2) 的暴力算法面前是质变，也是这道题考查的核心点：能不能看出滑动窗口结构。

4. 把空间省下来：滑动窗口

4.1 窗口移动时的更新公式

前缀和版本已经能 AC 了，但空间上还有优化空间。既然我们只是要连续窗口的和，完全可以维护一个running值，窗口向右移动一步时，把滑出窗口的贡献减掉，把滑进窗口的贡献加上。

假设当前窗口起点是start，它对应的差异是：

d_start = sum(diff[start], ..., diff[start + n - 1])

窗口右移一步之后，新的起点是start + 1，新的差异是：

d_{start+1} = d_start - diff[start] + diff[start + n]

这里diff[start]是旧窗口最左边的失配值，diff[start + n]是新窗口最右边的失配值。中间那些元素在原窗口和新窗口中都存在，贡献不变，所以不需要重新计算。

4.2 不构造双倍串的写法

其实连 diff 数组都可以不提前构造。因为diff[i]的值只依赖s[i % n]和i % 2，所以用一个很小的函数就能实时算出来：

def mismatch(i: int) -> int: target = '0' if i % 2 == 0 else '1' return int(s[i % n] != target)

这样空间复杂度可以降到 O(1)，只保留一个 running 变量。

4.3 参考代码（Python / C++）

Python 版本：

class Solution: def minFlips(self, s: str) -> int: n = len(s) def mismatch(i: int) -> int: target = '0' if i % 2 == 0 else '1' return int(s[i % n] != target) running = 0 for i in range(n): running += mismatch(i) ans = min(running, n - running) for start in range(1, n): running += mismatch(start + n - 1) - mismatch(start - 1) ans = min(ans, running, n - running) return ans

C++ 版本：

class Solution { public: int minFlips(string s) { int n = s.size(); auto mismatch = [&](int i) -> int { char target = (i % 2 == 0) ? '0' : '1'; return s[i % n] != target ? 1 : 0; }; int running = 0; for (int i = 0; i < n; ++i) { running += mismatch(i); } int ans = min(running, n - running); for (int start = 1; start < n; ++start) { running += mismatch(start + n - 1) - mismatch(start - 1); ans = min(ans, min(running, n - running)); } return ans; } };

注意循环里的下标范围。我取的是窗口左闭右开结构，比较别扭的是start + n - 1，它对应新进入窗口的那个位置。以 start = 1 为例，旧窗口是 [0, n-1]，新窗口是 [1, n]，所以要加上 diff[n]，减去 diff[0]，正好是mismatch(1 + n - 1) - mismatch(0)。

这个写法的时间复杂度依旧是 O(n)，但省掉了 diff 和 pref 两个数组，空间变成 O(1)。

5. 常见错误、坑位与自测用例

5.1 最容易踩的坑

第一个坑：忘记取n - d。这是最经典的错误。有人算完窗口和 T0 的差异 d，直接就ans = min(ans, d)。这样会把 T1 的情况完全丢掉。因为窗口可能和 T1 更接近，这时候答案应该是n - d。这道题的数据规模不小，漏掉这个取反操作会导致一部分用例错误，而且不容易一眼看出来。

第二个坑：下标越界。双倍串其实不需要真的做满 2n 的长度，窗口最大终点是start + n - 1，start 最大是 n-1，所以终点最大是 2n-2。严格来说长度 2n-1 就够，但很多人在代码里只构造了长度为 2n 的双倍串，这也完全没问题。怕的是在某些滑动窗口写法里，把新加入的位置写成start + n，就会在最后一轮越界。

第三个坑：目标字符的奇偶关系写反。i为偶数对应0，奇数对应1。如果写反，整个失配数组都会错，但程序不会报错，只能靠测试用例发现。建议在代码里用一行注释标注清楚。

第四个坑：在遍历过程中改了原串。有些选手为了模拟旋转，真的去移动字符，然后在原串上继续翻转。这个思路在 n 很大的时候不仅慢，而且特别容易因为字符位移搞乱索引。正确做法是只把原串当成一个只读数组，通过下标去计算。

5.2 边界情况与自测数据

我建议把下面这几个用例拿来验证代码：

最后一个用例值得说一下。111000和模式101010比较，位置 1 和位置 4 不一致，所以直接翻转这两个位置就能变成交替串，答案是 2。这个用例能帮你确认n - d那个逻辑没有写错。

5.3 手推一个完整例子

以s = "0100"为例，n = 4。双倍串长度为 8，原串是01000100。T0 的开头 8 位是01010101。逐个比较得到失配数组：

• i=0，字符 0 对目标 0，失配 0
• i=1，字符 1 对目标 1，失配 0
• i=2，字符 0 对目标 0，失配 0
• i=3，字符 0 对目标 1，失配 1
• i=4，字符 0 对目标 0，失配 0
• i=5，字符 1 对目标 1，失配 0
• i=6，字符 0 对目标 0，失配 0
• i=7，字符 0 对目标 1，失配 1

窗口 start=0 时，窗口是0100，和 T0 的差异是 1，和 T1 的差异是 4 - 1 = 3，答案至少是 1。滑动 start=1 时，窗口变成1000，对应左移一次的结果。这时候的差异用公式算就是加上 diff[4]、减去 diff[0]，running 还是 1，所以答案维持 1。这说明不管怎么旋转，至少需要翻转一个位置，最终答案是 1。

6. 这套思路能用到哪：循环匹配的通用套路

6.1 环形问题的标准处理

以后看到“字符串可以循环移位”“数组是环形的”“头尾相接”这类描述，第一反应就是把序列复制一份变成双倍长度，然后用长度为 n 的滑动窗口去枚举所有可能的“起点”。这是一个很通用的套路，很多环形数组、循环子串的问题都能用这个思路降维。

尤其是在序列上做区间统计的场景，复制一份之后，区间[start, start + n - 1]就变成了一个普通的一维区间问题，可以用前缀和、差分、滑动窗口、单调队列等等手段处理。

6.2 更通用的操作拆分思路

这道题还有一层更抽象的启发：当多种操作混在一起时，先看哪些操作是“无代价”的，哪些是“有代价”的。无代价的操作往往可以大量使用，所以问题可以转换成“在最有利的无代价操作之后，最小化有代价操作的次数”。

在这题里，旋转无代价，翻转有代价。于是问题从“执行一串复杂操作”变成了“枚举旋转终态，然后数差异”。如果你以后遇到别的题，比如可以随便移动某个元素、但修改某个值需要花费，也可以先想清楚移动和修改之间的顺序能不能交换，能不能先把移动枚举完，再单独考虑修改成本。

6.3 一点经验

我自己实际写这道题的时候，第一次用的是前缀和版本，因为思路最直接，不容易在滑动窗口的边界上犯错。AC 之后再改成 O(1) 空间的滑动窗口版本，反而花了一点时间核对索引。我的建议是，比赛或面试里优先选自己最有把握的写法，能过就行；有时间再去优化空间。

最后再分享一个小技巧：这类“和某个固定交替模式比差异”的题，通常固定模式只会有两个，而且互为取反。你只要算出一个方向的差异 d，另一个方向就是 n - d，不用真的再建立第二个模式串。记住了这个小结论，很多交替串相关的题都能省一半代码量。