2026-11-08:得到旋转回文字符串的最少操作次数Ⅰ。用go语言,给定一个只含小写字母的字符串。允许重复进行两类改动:第一类,任选一个位置,把该字符按字母表顺序向后挪一位,若原来是 z 则变成 a;第二类,把当前字符串最前面的字符取下来放到最后面。两类改动可以任意穿插、任意次数进行。要求算出把这个字符串变成正读和反读都相同的回文串,最少需要执行多少次改动。

2 <= s.length <= 2000。

s 仅由小写英文字母组成。

输入: s = "abc"。

输出: 2。

解释:

一种最优方案:

左旋字符串:"abc" -> "bca" 。

递增 'a' 为 'b':"bca" -> "bcb" 。

"bcb" 是一个回文串。因此,答案是 2 。

题目来自力扣4021。

大体步骤如下:

  1. 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 + total

if __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助力您的未来发展。