2026-11-08:得到旋转回文字符串的最少操作次数Ⅰ。用go语言,给定一个只含小写字母的字符串。允许重复进行两类改动:第一类,任选一个位置,把该字符按字母表顺序向后挪一位,若原来是 z 则变成 a;第二类,把当前字符串最前面的字符取下来放到最后面。两类改动可以任意穿插、任意次数进行。要求算出把这个字符串变成正读和反读都相同的回文串,最少需要执行多少次改动。
2 <= s.length <= 2000。
s 仅由小写英文字母组成。
输入: s = "abc"。
输出: 2。
解释:
一种最优方案:
左旋字符串:"abc" -> "bca" 。
递增 'a' 为 'b':"bca" -> "bcb" 。
"bcb" 是一个回文串。因此,答案是 2 。
题目来自力扣4021。
大体步骤如下:
1.固定旋转次数,把问题拆成“旋转代价 + 字符递增代价”
• 题目允许把首字符移到末尾任意次。若最终相当于左旋了
rot次,那么旋转本身贡献rot次操作。• 左旋
rot次后,新字符串第i位来自原串的(i+rot) mod n。• 回文要求新串第
i位与第n-1-i位相同。换回原串下标,就是原位置p与q要配成一对,并且满足p + q ≡ 2*rot - 1 (mod n)。• 因此固定
rot后,所有配对位置的和模n都等于(2*rot-1) mod n。代码里枚举rot,并令c = (2*rot - 1 + n) mod n,就是当前旋转下配对位置的下标和。
2.两个字符变成相同字符的最小递增代价
• 字符只能向后递增,且
z后回到a。• 对两个字符
x、y,要让它们变成同一个字符,最优策略是把其中一个沿较短的那段字母环增加到另一个,所以最小代价就是它们在 26 个字母环上的最短距离,即min((y-x) mod 26, (x-y) mod 26)。• 若两个位置本来字符相同,代价为 0;若是同一个中心位置,也不需要修改,代价为 0。
3.用 13 个长度为 13 的字母窗口来分解“最短距离”
• 代码枚举
k = 0..12,对应 13 个窗口W_k = {k, k+1, ..., k+12},即从字母k开始连续 13 个字母。• 对每个字符
x,记S(x)为覆盖它的窗口集合,也就是所有满足k <= x < k+13的窗口编号。• 对两个字符
x、y,有|S(x)| + |S(y)| - 2*|S(x) ∩ S(y)|
正好等于它们在 26 字母环上的最短距离。• 直观理解:两个字符的覆盖窗口集合的“对称差”大小,就是它们在字母环上较短方向的距离。相同字符的对称差为 0,距离最大为 13。
• 代码中的
total就是把所有位置在所有窗口中被覆盖的次数全部累加起来,即total = Σ_i |S(s[i])|。• 如果某些配对的共同覆盖次数也能统计出来,那么配对总代价就可以写成
total - 共同覆盖计数。
4.对每个窗口构造二进制数组并做循环自卷积
• 对固定的窗口
W_k,构造一个长度等于字符串长度的二进制数组:• 若原串第
i个字符属于W_k,该位为 1;• 否则为 0。
• 然后计算这个二进制数组的循环自卷积。循环自卷积在模
n下标d处的值,统计的是有多少对位置(i,j)满足:• 两个位置在该窗口中的值都为 1;
• 并且
i + j ≡ d (mod n)。
• 由于是“自卷积”,当
i != j时,有序对(i,j)和(j,i)都会分别被统计一次;当i = j时只统计一次。这个性质正好和后面的配对计数相匹配。• 代码对所有 13 个窗口分别做循环自卷积,并把结果按模
n的下标累加到数组convSum中。于是convSum[d]表示:在所有 13 个窗口中,满足i+j≡d (mod n)且两个位置都在对应窗口内的有序 1 对总数。
5.固定旋转下的配对代价公式
• 固定
rot后,需要配对的原始位置满足i + j ≡ c (mod n),其中c = (2*rot-1) mod n。• 对于所有这样的配对:
•
total贡献每个字符被窗口覆盖的次数之和;•
convSum[c]贡献两个位置同时被同一窗口覆盖的次数,并且有序对会贡献两次;• 两者相减后,对每一对位置,正好得到两个字符在字母环上的最短距离。
• 中心位置若存在,即
i = j,它在total中贡献一次,在convSum[c]中也贡献一次,正好抵消为 0,符合中心字符不需要修改。• 因此固定
rot下的字符递增总代价为total - convSum[c]。• 加上旋转代价
rot,总代价就是rot + total - convSum[c]。
6.枚举旋转次数取最小
• 代码枚举
rot = 0..n-1,计算候选值rot + total - convSum[(2*rot-1+n) mod n]。• 代码实际写法是先令
ans = min(ans, rot - convSum[c]),
最后再返回ans + total,两者等价。• 因为旋转超过
n次会回到原串,所以只需要枚举0..n-1。
7.循环自卷积如何用 FFT 实现
• 线性自卷积需要长度至少
2n-1。• 代码取
limit为大于等于2n-1的最小 2 的幂。• 把长度为
n的二进制数组补零到limit,做一次 DFT;• 频域中每个复数点乘自身,相当于时域做自卷积;
• 再做 IDFT,并对实部四舍五入,得到普通的线性自卷积。
• 线性卷积结果长度为
2n-1。要变成模x^n-1的循环卷积,就把下标n到2n-2的系数折回到下标0到n-2,即把conv[n+k]加到conv[k]。• 代码中的
selfCyclicConvFFT正是这样得到长度n的循环自卷积。
8.对示例s = "abc"的结果解释
• 长度为 3,窗口和循环自卷积累加后,枚举三种旋转:
• 旋转 0 次候选总代价;
• 旋转 1 次候选总代价;
• 旋转 2 次候选总代价。
• 最优是先左旋一次:
"abc" -> "bca",操作数 1;• 再把
'a'递增为'b':"bca" -> "bcb",操作数 1;• 总共 2 次。程序输出 2。
总时间复杂度
主循环有 13 个字母窗口,是常数。每次需要对长度L的数组做 FFT,其中L是大于等于2n-1的最小 2 的幂,因此L = O(n)。一次 FFT 的时间是O(L log L),所以总时间为O(13 * L log L + n) = O(n log n)。
总额外空间复杂度
每次 FFT 需要长度为L的复数数组、旋转因子数组,以及长度O(n)的卷积结果、二进制数组和累加数组。L = O(n),因此额外空间为O(n)。
Go完整代码如下:
package main
import (
"fmt"
"math"
"math/bits"
)
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 := range13 {
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
}func main() {
s := "abc"
result := minOperations(s)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
import math
classFFT:
def__init__(self, n):
self.n = n
self.omega = [0j] * n
self.omega_inv = [0j] * n
for i inrange(n):
theta = 2.0 * math.pi * i / n
c = math.cos(theta)
s = math.sin(theta)
self.omega[i] = complex(c, s)
self.omega_inv[i] = complex(c, -s)
deftransform(self, a, omega):
n = self.n
j = 0
for i inrange(n):
if i < j:
a[i], a[j] = a[j], a[i]
l = n // 2
whileTrue:
j ^= l
if j >= l:
break
l //= 2
l = 2
while l <= n:
m = l // 2
for st inrange(0, n, l):
for i inrange(m):
v = omega[(n // l) * i] * a[st + m + i]
a[st + m + i] = a[st + i] - v
a[st + i] += v
l *= 2
defdft(self, a):
self.transform(a, self.omega)
defidft(self, a):
self.transform(a, self.omega_inv)
cn = complex(self.n, 0)
for i inrange(len(a)):
a[i] /= cn
defself_poly_conv_fft(a):
n = len(a)
m = n * 2 - 1
limit = 1 << m.bit_length()
A = [0j] * limit
for i, v inenumerate(a):
A[i] = complex(v, 0)
fft = FFT(limit)
fft.dft(A)
for i inrange(limit):
A[i] *= A[i]
fft.idft(A)
conv = [0] * m
for i inrange(m):
conv[i] = int(math.floor(A[i].real + 0.5))
return conv
defself_cyclic_conv_fft(a):
n = len(a)
conv = self_poly_conv_fft(a)
for k inrange(n - 1):
conv[k] += conv[n + k]
return conv[:n]
defmin_operations(s: str) -> int:
n = len(s)
conv_sum = [0] * n
a = [0] * n
total = 0
for k inrange(13):
for i inrange(n):
x = ord(s[i]) - ord('a')
if k <= x < k + 13:
a[i] = 1
total += 1
else:
a[i] = 0
c = self_cyclic_conv_fft(a)
for i, v inenumerate(c):
conv_sum[i] += v
ans = 10**18
for rot inrange(n):
c = (rot * 2 - 1 + n) % n
ans = min(ans, rot - conv_sum[c])
return ans + totalif __name__ == "__main__":
s = "abc"
result = min_operations(s)
print(result)
C++完整代码如下:
#include
#include
#include
#include
#include
#include
#include
usingnamespace std;
structFFT {
int n;
vector double >> omega;
vector double >> omega_inv;
FFT ( int n_) : n (n_), omega (n), omega_inv (n) {
const double PI = acos ( -1.0 );
for ( int i = 0 ; i < n; i++) {
double theta = 2.0 * PI * i / n;
double s = sin (theta);
double c = cos (theta);
omega[i] = complex < double >(c, s);
omega_inv[i] = complex < double >(c, -s);
}
}
void transform(vector double >>& a, const vector double >>& omega_) {
int n = this->n;
// 位反转置换
for (int i = 0, j = 0; i < n; i++) {
if (i > j) {
swap(a[i], a[j]);
}
for (int l = n / 2; ; l /= 2) {
j ^= l;
if (j >= l) break;
}
}
// 蝶形运算
for (int l = 2; l <= n; l *= 2) {
int m = l / 2;
for (int st = 0; st < n; st += l) {
for (int i = 0; i < m; i++) {
complex v = omega_[(n / l) * i] * a[st + m + i];
a[st + m + i] = a[st + i] - v;
a[st + i] += v;
}
}
}
}
void dft(vector double >>& a) {
transform(a, omega);
}
void idft(vector double >>& a) {
transform(a, omega_inv);
complex cn(n, 0);
for (auto& x : a) x /= cn;
}
};
// 计算 a 的自卷积
vector selfPolyConvFFT(const vector& a) {
int n = (int)a.size();
int m = n * 2 - 1;
// 等价于 Go 的 1 << bits.Len(uint(n*2-1))
int limit = 1;
while (limit <= m) limit <<= 1;vector double >> A (limit, complex < double >( 0 , 0 ));
for ( int i = 0 ; i < n; i++) {
A[i] = complex < double >(a[i], 0 );
}
FFT fft(limit) ;
fft. dft (A);
for ( auto & x : A) x *= x;
fft. idft (A);
vector conv(m) ;
for ( int i = 0 ; i < m; i++) {
conv[i] = ( int ) llround (A[i]. real ());
}
return conv;
}
// 计算 a 的循环自卷积
vector selfCyclicConvFFT(const vector& a) {
int n = ( int )a. size ();
vector< int > conv = selfPolyConvFFT (a);
for ( int k = 0 ; k < n - 1 ; k++) {
conv[k] += conv[n + k];
}
conv. resize (n);
return conv;
}
int minOperations(const string& s) {
int n = ( int )s. size ();
vector convSum(n, 0) ;
vector a(n) ;
int total = 0 ;
for ( int k = 0 ; k < 13 ; k++) {
for ( int i = 0 ; i < n; i++) {
int x = s[i] - 'a' ;
if (k <= x && x < k + 13 ) {
a[i] = 1 ;
total++;
} else {
a[i] = 0 ;
}
}
vector< int > c = selfCyclicConvFFT (a);
for ( int i = 0 ; i < n; i++) {
convSum[i] += c[i];
}
}
int ans = INT_MAX;
for ( int rot = 0 ; rot < n; rot++) {
int c = (rot * 2 - 1 + n) % n;
ans = min (ans, rot - convSum[c]);
}
return ans + total;
}
int main() {
string s = "abc" ;
int result = minOperations (s);
cout << result << endl;
return 0 ;
}
芯谷ai:https://xinguhub.com/sign-up?aff=txk5
我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.