企业官网建设流程全解析

• 科学计算

本篇文章以《力扣双周赛 189》B 题（b/README.md）的官方题解文档为骨架，完整还原"得到旋转回文字符串的最少操作次数 I"（LC 4021）的两套解法：方法一的 $\mathcal{O}(n^2)$ 暴力枚举，以及方法二的基于循环自卷积与 FFT 的 $\mathcal{O}(|\Sigma|\cdot n\log n)$ 优化。文章同时结合仓库内的 b.go 实现、b_test.go 测试与 math_fft.go 库函数，给出可直接复制运行的多语言代码、完整的公式推导链路与仓库级验证方法，帮助读者掌握"枚举旋转位移 + 环上最短距离"以及"特征函数 + 卷积加速配对计数"这两类通用技巧。

题目背景：最小操作使旋转串成为回文

本题出自力扣第 189 场双周赛，对应题目为 minimum-operations-to-make-a-rotated-palindrome-i，仓库将其编号为leetcode/biweekly/189/b，在 双周赛总览 中被列为 Q2。

问题定义：给定一个长度为 $n$ 的小写字母字符串 $s$，允许两种操作：

1. 左旋：把 $s$ 左旋任意次数（每次把最左边的字符移到最右边），花费等于左旋的次数；
2. 递增：把任意一个字符x增大为字母表中它后面的某个字符（即x→x+1→ ... ），花费为操作次数；字母可以绕回，即z增大一次回到a。

目标是求出最小的总花费，使得 $s$ 在左旋 $\textit{rot}$ 次后，能通过若干次递增操作变成一个回文字符串。

仓库中给出的两个示例（见 b.txt）：

"abc" -> 2 "yb" -> 3

这些样例由 b_test.go 通过testutil.RunLeetCodeFuncWithFile自动载入并校验minOperations函数，测试基础设施位于 leetcode/testutil/leetcode.go。

关键观察：左旋串就是 $s+s$ 的子串

$s$ 左旋 $\textit{rot}=0,1,\dots,n-1$ 次后的字符串，等价于取双写字符串 $s+s$ 中左端点为 $\textit{rot}$、右端点为 $\textit{rot}+n-1$ 的子串。因此，判断该子串能否通过递增操作变成回文串，等价于要求：

$$ s[(\textit{rot}+i)\bmod n] = s[(\textit{rot}+n-1-i)\bmod n] $$

对所有 $i=0,1,\dots,\lfloor n/2\rfloor-1$ 成立（这里下标自动对 $n$ 取模，即把 $s$ 视作一个环）。

方法一：暴力枚举左旋次数（$\mathcal{O}(n^2)$）

单次字符配对的成本：环上的最短距离

把字母视为 $[0,25]$ 中的整数（a=0, ...,z=25）。对于一对字符 $x\le y$，通过递增操作使二者相等，有两种策略：

• 把 $x$ 增大到 $y$，花费 $y-x$ 次；
• 把 $y$ 增大绕回一圈到 $x$，花费 $26-y+x$ 次。

取两者最小值即可。

注（为什么不用都操作）：同时操作 $x$ 和 $y$ 一定不优——若 $x$、$y$ 各少操作一次，两个字母最终仍然相同，花费反而更小。因此最优策略一定是只动其中一个字符。

枚举框架与剪枝

外层枚举 $\textit{rot}$，此时"旋转花费"为 $\textit{rot}$；内层枚举镜像对 $i$ 累加每对的 $\min(d,26-d)$（$d$ 为两字符的绝对差值）。若累加过程中op >= ans即可提前break剪枝。

四语言完整实现（与题解文档一致）：

class Solution: def minOperations(self, s: str) -> int: n = len(s) ans = inf for rot in range(n): op = rot for i in range(n // 2): d = abs(ord(s[(rot + i) % n]) - ord(s[(rot - 1 - i) % n])) op += min(d, 26 - d) # 注：这里可以加个剪枝，如果 op >= ans 则 break ans = min(ans, op) return ans

class Solution { public int minOperations(String S) { char[] s = S.toCharArray(); int n = s.length; int ans = Integer.MAX_VALUE; for (int rot = 0; rot < n; rot++) { int op = rot; for (int i = 0; i < n / 2; i++) { int d = Math.abs(s[(rot + i) % n] - s[(rot + n - 1 - i) % n]); op += Math.min(d, 26 - d); // 注：这里可以加个剪枝，如果 op >= ans 则 break } ans = Math.min(ans, op); } return ans; } }

class Solution { public: int minOperations(string s) { int n = s.size(); int ans = INT_MAX; for (int rot = 0; rot < n; rot++) { int op = rot; for (int i = 0; i < n / 2; i++) { int d = abs(s[(rot + i) % n] - s[(rot + n - 1 - i) % n]); op += min(d, 26 - d); // 注：这里可以加个剪枝，如果 op >= ans 则 break } ans = min(ans, op); } return ans; } };

func minOperations(s string) int { n := len(s) ans := math.MaxInt for rot := range n { op := rot for i := range n / 2 { d := abs(int(s[(rot+i)%n]) - int(s[(rot+n-1-i)%n])) op += min(d, 26-d) // 注：这里可以加个剪枝，如果 op >= ans 则 break } ans = min(ans, op) } return ans } func abs(x int) int { if x < 0 { return -x } return x }

这段 Go 实现与仓库 b.go 中的minOperations1完全一致。

复杂度分析

• 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $s$ 的长度；
• 空间复杂度：$\mathcal{O}(1)$。

当 $n$ 达到 $10^4$ 甚至更大时，$\mathcal{O}(n^2)$ 不可行，因此需要方法二。

方法二：循环自卷积 + FFT（$\mathcal{O}(|\Sigma|\cdot n\log n)$）

从 26 环最短距离到特征函数

定义 $D(x,y)$ 为使字母 $x$ 和 $y$ 相等的最少递增操作次数——即长为 26 的环上两点 $x,y$ 的最短距离。

设左旋 $R$ 次，总花费为：

$$ S_R = \sum_{i=0}^{\lfloor n/2 \rfloor - 1} D(s[(R+i)\bmod n],s[(R+n-1-i)\bmod n]) = \frac{1}{2}\sum_{i=0}^{n-1} D(s[(R+i)\bmod n],s[(R+n-1-i)\bmod n]) $$

（第二个等号成立是因为镜像对 $i$ 与 $n-1-i$ 各被计数一次。）

考虑两个下标之和模 $n$：

$$ (R+i) + (R+n-1-i) \equiv 2R-1 \pmod n $$

当 $R$ 固定时这是一个定值——这正是把 $S_R$ 转化为某种"循环卷积"的突破口。

关键转化：最短距离 = 被"半圆弧切分"分开的次数。想象把长为 26 的环均匀切成两个半圆弧（端点落在整点上）。对 $x=1$（b）与 $y=4$（e），恰好有 3 种切法（半圆弧分别为 $[2,14]$、$[3,15]$、$[4,16]$）使二者分属不同的半圆弧，这 3 恰好等于它们的最短距离 3。

推广到一般情形：定义特征函数（$k=0,1,\dots,12$）

$$ I_k(x) = \begin{cases} 1, & x\in [k,k+12] \ 0, & x\notin [k,k+12] \end{cases} $$

那么 $x,y$ 的最短距离等于"有多少个不同的 $k$ 使得 $I_k(x)\ne I_k(y)$"：

$$ D(x,y) = \sum_{k=0}^{12} [I_k(x)\ne I_k(y)] $$

记号 $[p\ne q]$ 表示当 $p\ne q$ 时结果为 1，否则为 0（即把 bool 值转为 int）。

交换求和顺序，露出卷积

设 $a_k = [I_k(s[0]), I_k(s[1]), \dots, I_k(s[n-1])]$（0/1 数组），代入并交换求和顺序：

$$ S_R = \frac{1}{2}\sum_{k=0}^{12}\sum_{i=0}^{n-1} [a_k[(R+i)\bmod n]\ne a_k[(R+n-1-i)\bmod n]] $$

以 $R=0$ 为例，内层和式为：

$$ [a_k[0]\ne a_k[n-1]] + [a_k[1]\ne a_k[n-2]] + \cdots + [a_k[n-1]\ne a_k[0]] $$

设 $a_k$ 的循环自卷积为 $c_k$：

$$ c_k[r] = \sum_{\substack{0\le i,j< n\ i+j\equiv r\pmod n}} a_k[i]\cdot a_k[j] $$

令 $r=(2R-1)\bmod n$。对 $R=0$ 有 $r=n-1$：

$$ c_k[n-1] = a_k[0]\cdot a_k[n-1] + a_k[1]\cdot a_k[n-2] + \cdots + a_k[n-1]\cdot a_k[0] $$

由于 $a_k[i]\in{0,1}$，乘积为 1 当且仅当两个位置都是 1。设 $a_k$ 中 1 的总数为 $\textit{cnt}_k$，则"一个为 1 一个为 0"的镜像对数量为：

• $a_k[i]=1, a_k[n-1-i]=0$：$\textit{cnt}_k - c_k[n-1]$ 个；
• $a_k[i]=0, a_k[n-1-i]=1$：由对称性同样为 $\textit{cnt}_k - c_k[n-1]$ 个。

因此内层和式 $= 2(\textit{cnt}_k - c_k[n-1])$。一般化到任意 $R$：

$$ S_R = \frac{1}{2}\sum_{k=0}^{12} 2(\textit{cnt}k - c_k[r]) = \sum{k=0}^{12}\textit{cnt}k - \sum{k=0}^{12} c_k[r] $$

记 $\textit{total}=\sum_{k=0}^{12}\textit{cnt}k$（所有特征数组里 1 的总数），$\textit{convSum}[r]=\sum{k=0}^{12} c_k[r]$，则：

$$ S_R = \textit{total} - \textit{convSum}[(2R-1)\bmod n] $$

最终答案

总花费 $= R + S_R$，枚举 $R=0,\dots,n-1$ 取最小：

$$ \min_{R=0}^{n-1}\big(R+S_R\big) = \textit{total} + \min_{R=0}^{n-1}\big(R - \textit{convSum}[(2R-1)\bmod n]\big) $$

于是问题归结为：对 13 个 0/1 数组分别做一次循环自卷积，把结果按位累加进 $\textit{convSum}$。每对 (0/1) 数组的循环自卷积用 FFT 在 $\mathcal{O}(n\log n)$ 内完成，总复杂度 $\mathcal{O}(13\cdot n\log n)=\mathcal{O}(|\Sigma| n\log n)$。

Python 实现（numpy + FFT）

import numpy as np # 返回 a 的循环自卷积 def self_cyclic_conv(a: list[int]) -> np.ndarray: return np.rint(np.fft.ifft(np.fft.fft(a) ** 2).real) class Solution: def minOperations(self, s: str) -> int: s = [ord(c) - ord('a') for c in s] n = len(s) conv_sum = np.zeros(n, dtype=np.float64) a = [0] * n total = 0 for k in range(13): for i, ch in enumerate(s): if k <= ch < k + 13: a[i] = 1 total += 1 else: a[i] = 0 c = self_cyclic_conv(a) conv_sum += c # 对每个 i 执行 conv_sum[i] += c[i] return total + min(rot - int(conv_sum[(rot * 2 - 1) % n]) for rot in range(n))

Go 实现（手写迭代 FFT）

type fft struct { n int omega []complex128 omegaInv []complex128 } func newFFT(n int) *fft { omega := make([]complex128, n) omegaInv := make([]complex128, n) for i := range omega { sin, cos := math.Sincos(2 * math.Pi * float64(i) / float64(n)) omega[i] = complex(cos, sin) omegaInv[i] = complex(cos, -sin) } return &fft{n, omega, omegaInv} } func (t *fft) transform(a, omega []complex128) { n := t.n for i, j := 0, 0; i < n; i++ { if i > j { // 保证同一对元素只交换一次 a[i], a[j] = a[j], a[i] } for l := n / 2; ; l /= 2 { j ^= l if j >= l { break } } } for l := 2; l <= n; l *= 2 { m := l / 2 for st := 0; st < n; st += l { b := a[st:] for i := range m { v := omega[n/l*i] * b[m+i] b[m+i] = b[i] - v b[i] += v } } } } func (t *fft) dft(a []complex128) { t.transform(a, t.omega) } func (t *fft) idft(a []complex128) { t.transform(a, t.omegaInv) cn := complex(float64(t.n), 0) for i := range a { a[i] /= cn } } // 计算 a 的自卷积 func selfPolyConvFFT(a []int) []int { n := len(a) limit := 1 << bits.Len(uint(n*2-1)) A := make([]complex128, limit) for i, v := range a { A[i] = complex(float64(v), 0) } t := newFFT(limit) t.dft(A) for i, x := range A { A[i] *= x } t.idft(A) conv := make([]int, n*2-1) for i := range conv { conv[i] = int(math.Round(real(A[i]))) } return conv } // 计算 a 的循环自卷积 func selfCyclicConvFFT(a []int) []int { n := len(a) conv := selfPolyConvFFT(a) for k := range n - 1 { conv[k] += conv[n+k] } return conv[:n] } func minOperations(s string) int { n := len(s) convSum := make([]int, n) a := make([]int, n) total := 0 for k := range 13 { for i := range n { x := int(s[i] - 'a') if k <= x && x < k+13 { a[i] = 1 total++ } else { a[i] = 0 } } c := selfCyclicConvFFT(a) for i, v := range c { convSum[i] += v } } ans := math.MaxInt for rot := range n { c := (rot*2 - 1 + n) % n ans = min(ans, rot-convSum[c]) } return ans + total }

复杂度分析

• 时间复杂度：$\mathcal{O}(|\Sigma| n\log n)$，其中 $n$ 是 $s$ 的长度，$|\Sigma|=26$ 是字符集合大小（特征函数只取 $k=0..12$ 共 13 个，即 $\lceil|\Sigma|/2\rceil$ 个）；
• 空间复杂度：$\mathcal{O}(n)$。

仓库内的实现与验证证据

题解文档中的两套 Go 代码在仓库中都有完全对应的可运行实现：

• b.go：同时包含方法一的minOperations1（L9-L21）与方法二的minOperations（L120-L147），FFT 部分自带了fft结构体、蝶形变换transform、正变换dft/逆变换idft、普通自卷积selfPolyConvFFT与循环自卷积selfCyclicConvFFT；
• b_test.go：通过testutil.RunLeetCodeFuncWithFile(t, minOperations, "b.txt", 0)驱动测试，逐条比对 b.txt 中的输入与期望输出；
• 测试框架 leetcode.go：RunLeetCodeFuncWithFile按"每 输入数+输出数 行一组"读取样例文件，用反射自动调用被测函数，是仓库内所有力扣题解统一使用的校验入口。

更值得关注的是，循环自卷积工具本身是仓库的通用算法库成员：selfCyclicConvFFT在 copypasta/math_fft.go 中被定义，注释明确标注了它服务于 LC 4021（本题），并给出数学语义：

$$ c[k] = \sum_{i=0}^{n-1} a[i]\cdot a[(k-i+n)\bmod n] = \sum_{(i+j)\bmod n = k} a[i]\cdot a[j] $$

以及它与普通卷积的换算关系 $c[k] = \textit{conv}[k] + \textit{conv}[n+k]$（唯一例外是 $k=n-1$ 时只有 $c[k]=\textit{conv}[k]$，因为 $i+j$ 最大只能到 $2n-2=n+(n-2)$）。同文件还提供了 滑动窗口点积slidingWindowDotProduct（反转数组后做普通卷积）等配套工具，说明"循环卷积"这一技巧在该库中被复用到了字符串匹配、图像重叠等多类问题。

小结：两种解法的选型建议

整套推导可以抽象为一个可复用的套路：当需要统计"环形结构上按镜像关系配对的所有位置差"时，先构造 0/1 特征数组，再把配对计数写成 $\sum_{i+j\equiv r} a[i]b[j]$ 形式的循环卷积，最后用 FFT 统一加速。仓库中copypasta/math_fft.go的selfCyclicConvFFT正是这一思路的通用实现，配合 testutil 的样例驱动测试，读者可以在本地直接运行b_test.go验证上述两种解法输出一致（对"abc"得 2，对"yb"得 3）。

• 科学计算