首页 > 试题广场 >

小红的字符串

[编程题]小红的字符串
  • 热度指数:2357 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红拥有一个长度为 n 的小写字母字符串 s。她可以重复执行如下操作任意次:
\hspace{23pt}\bullet\, 选择一个下标 i\ (1\leqq i\leqq n),将字符 s_i 循环右移到字母表中的下一个字母。特别地,``\texttt{z}`` 右移后变成 ``\texttt{a}``。
\hspace{15pt}
\hspace{15pt}请计算,使 s 变为回文串所需的最少操作次数。

\hspace{15pt}【名词解释】回文串:一个字符串从左往右与从右往左读完全相同。

输入描述:
\hspace{15pt}一行输入一个长度不超过 1000 的小写字母字符串 s


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数,代表把 s 变成回文串的最少操作次数。
示例1

输入

abcd

输出

4

说明

一种可行方案:\texttt{(共 4 次操作)。
示例2

输入

nuhhhh

输出

19
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int len = s.length();
        int sum = 0;
        
        for (int i = 0; i < len / 2; i++) {
            char a = s.charAt(i);
            char b = s.charAt(len - 1 - i);
            
            // 计算两个字符的最小距离(循环右移次数)
            int diff = Math.abs(a - b);
            sum += Math.min(diff, 26 - diff);
        }
        
        System.out.println(sum);
    }
}
    

发表于 2025-09-03 14:30:53 回复(0)
import java.util.*;
import java.io.*;

//下标为i和下标为n-1-i的字符是一组c1和c2。
//c1操作和c2操作一个右移到另一个是最短的,
//两个都移动为第三个字符的情况一定会比单个移动到另一个的移动次数多,因为可假设第三字符在两个字符之间或两字符之外循环单向移动都会更长

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        char[] input=bf.readLine().toCharArray();
        int min=0;
        for(int a=0,b=input.length-1;a<b;a++,b--){
            int c1c2=(input[a]-input[b]+26)%26;//c1右移到c2  取模为正取正,为负取正向移动的另一半距离。
            int c2c1=(input[b]-input[a]+26)%26;//c2右移到c1
            min+=Math.min(c2c1,c1c2);
        }
        System.out.println(min);
    }
}

发表于 2025-09-03 12:42:04 回复(0)