 暴力枚举到循环自卷积 + FFT（灵茶山艾府双周赛 189 题解解析）)
★ FEATURED ARTICLE 科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇文章以《力扣双周赛 189》B 题b/README.md的官方题解文档为骨架完整还原得到旋转回文字符串的最少操作次数 ILC 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$允许两种操作左旋把 $s$ 左旋任意次数每次把最左边的字符移到最右边花费等于左旋的次数递增把任意一个字符x增大为字母表中它后面的某个字符即x→x1→ ... 花费为操作次数字母可以绕回即z增大一次回到a。目标是求出最小的总花费使得 $s$ 在左旋 $\textit{rot}$ 次后能通过若干次递增操作变成一个回文字符串。仓库中给出的两个示例见 b.txtabc - 2 yb - 3这些样例由 b_test.go 通过testutil.RunLeetCodeFuncWithFile自动载入并校验minOperations函数测试基础设施位于 leetcode/testutil/leetcode.go。关键观察左旋串就是 $ss$ 的子串$s$ 左旋 $\textit{rot}0,1,\dots,n-1$ 次后的字符串等价于取双写字符串 $ss$ 中左端点为 $\textit{rot}$、右端点为 $\textit{rot}n-1$ 的子串。因此判断该子串能否通过递增操作变成回文串等价于要求$$ s[(\textit{rot}i)\bmod n] s[(\textit{rot}n-1-i)\bmod n] $$对所有 $i0,1,\dots,\lfloor n/2\rfloor-1$ 成立这里下标自动对 $n$ 取模即把 $s$ 视作一个环。方法一暴力枚举左旋次数$\mathcal{O}(n^2)$单次字符配对的成本环上的最短距离把字母视为 $[0,25]$ 中的整数a0, ...,z25。对于一对字符 $x\le y$通过递增操作使二者相等有两种策略把 $x$ 增大到 $y$花费 $y-x$ 次把 $y$ 增大绕回一圈到 $x$花费 $26-yx$ 次。取两者最小值即可。注为什么不用都操作同时操作 $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 ansclass 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[(roti)%n]) - int(s[(rotn-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_{i0}^{\lfloor n/2 \rfloor - 1} D(s[(Ri)\bmod n],s[(Rn-1-i)\bmod n]) \frac{1}{2}\sum_{i0}^{n-1} D(s[(Ri)\bmod n],s[(Rn-1-i)\bmod n]) $$第二个等号成立是因为镜像对 $i$ 与 $n-1-i$ 各被计数一次。考虑两个下标之和模 $n$$$ (Ri) (Rn-1-i) \equiv 2R-1 \pmod n $$当 $R$ 固定时这是一个定值——这正是把 $S_R$ 转化为某种循环卷积的突破口。关键转化最短距离 被半圆弧切分分开的次数。想象把长为 26 的环均匀切成两个半圆弧端点落在整点上。对 $x1$b与 $y4$e恰好有 3 种切法半圆弧分别为 $[2,14]$、$[3,15]$、$[4,16]$使二者分属不同的半圆弧这 3 恰好等于它们的最短距离 3。推广到一般情形定义特征函数$k0,1,\dots,12$$$ I_k(x) \begin{cases} 1, x\in [k,k12] \ 0, x\notin [k,k12] \end{cases} $$那么 $x,y$ 的最短距离等于有多少个不同的 $k$ 使得 $I_k(x)\ne I_k(y)$$$ D(x,y) \sum_{k0}^{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_{k0}^{12}\sum_{i0}^{n-1} [a_k[(Ri)\bmod n]\ne a_k[(Rn-1-i)\bmod n]] $$以 $R0$ 为例内层和式为$$ [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\ ij\equiv r\pmod n}} a_k[i]\cdot a_k[j] $$令 $r(2R-1)\bmod n$。对 $R0$ 有 $rn-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_{k0}^{12} 2(\textit{cnt}k - c_k[r]) \sum{k0}^{12}\textit{cnt}k - \sum{k0}^{12} c_k[r] $$记 $\textit{total}\sum_{k0}^{12}\textit{cnt}k$所有特征数组里 1 的总数$\textit{convSum}[r]\sum{k0}^{12} c_k[r]$则$$ S_R \textit{total} - \textit{convSum}[(2R-1)\bmod n] $$最终答案总花费 $ R S_R$枚举 $R0,\dots,n-1$ 取最小$$ \min_{R0}^{n-1}\big(RS_R\big) \textit{total} \min_{R0}^{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 FFTimport 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, dtypenp.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 实现手写迭代 FFTtype 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[mi] b[mi] 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[nk] } 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 k13 { 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$ 是字符集合大小特征函数只取 $k0..12$ 共 13 个即 $\lceil|\Sigma|/2\rceil$ 个空间复杂度$\mathcal{O}(n)$。仓库内的实现与验证证据题解文档中的两套 Go 代码在仓库中都有完全对应的可运行实现b.go同时包含方法一的minOperations1L9-L21与方法二的minOperationsL120-L147FFT 部分自带了fft结构体、蝶形变换transform、正变换dft/逆变换idft、普通自卷积selfPolyConvFFT与循环自卷积selfCyclicConvFFTb_test.go通过testutil.RunLeetCodeFuncWithFile(t, minOperations, b.txt, 0)驱动测试逐条比对 b.txt 中的输入与期望输出测试框架 leetcode.goRunLeetCodeFuncWithFile按每 输入数输出数 行一组读取样例文件用反射自动调用被测函数是仓库内所有力扣题解统一使用的校验入口。更值得关注的是循环自卷积工具本身是仓库的通用算法库成员selfCyclicConvFFT在 copypasta/math_fft.go 中被定义注释明确标注了它服务于 LC 4021本题并给出数学语义$$ c[k] \sum_{i0}^{n-1} a[i]\cdot a[(k-in)\bmod n] \sum_{(ij)\bmod n k} a[i]\cdot a[j] $$以及它与普通卷积的换算关系 $c[k] \textit{conv}[k] \textit{conv}[nk]$唯一例外是 $kn-1$ 时只有 $c[k]\textit{conv}[k]$因为 $ij$ 最大只能到 $2n-2n(n-2)$。同文件还提供了 滑动窗口点积slidingWindowDotProduct反转数组后做普通卷积等配套工具说明循环卷积这一技巧在该库中被复用到了字符串匹配、图像重叠等多类问题。小结两种解法的选型建议方法核心思想时间复杂度空间复杂度适用场景方法一枚举 $\textit{rot}$逐镜像对计算 $\min(d,26-d)$$\mathcal{O}(n^2)$$\mathcal{O}(1)$$n$ 较小如 $n\le 10^3$代码短、易剪枝方法二特征函数 $I_k$ 把最短距离拆成被半圆弧切分的次数用循环自卷积 FFT 一次性统计所有镜像对$\mathcal{O}(\Sigman\log n)$$\mathcal{O}(n)$$n$ 大$10^4\sim10^5$需要 FFT 基础设施整套推导可以抽象为一个可复用的套路当需要统计环形结构上按镜像关系配对的所有位置差时先构造 0/1 特征数组再把配对计数写成 $\sum_{ij\equiv r} a[i]b[j]$ 形式的循环卷积最后用 FFT 统一加速。仓库中copypasta/math_fft.go的selfCyclicConvFFT正是这一思路的通用实现配合 testutil 的样例驱动测试读者可以在本地直接运行b_test.go验证上述两种解法输出一致对abc得 2对yb得 3。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 186 全题解从唯一中位数到双序列交错计数灵茶山艾府题解 × codeforces-go 仓库 Go 实现力扣双周赛 186 全题解从唯一中位数到双序列交错计数灵茶山艾府题解 × codeforces go 仓库 Go 实现 本篇技术指南以 codeforce科学计算枚举木板对与双哈希表力扣双周赛 188「最宽栅栏」O(n²) 题解剖析codeforces-go 实战枚举木板对与双哈希表力扣双周赛 188「最宽栅栏」O n² 题解剖析codeforces go 实战 导读 本文围绕 codeforces go 仓库中科学计算LeetCode 31 Next Permutation 全解析从 O(n!) 暴力枚举到 O(n) 贪心双指针LeetCode 31 Next Permutation 全解析从 O n! 暴力枚举到 O n 贪心双指针 导读 本文围绕 LeetCode 经典中等题 N示例工程教程上一篇TFT_eSPI嵌入式显示屏终极开发指南从零基础到高级应用下一篇从零到一3步搞定黑苹果EFI配置的智能工具指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
