首页 > 代码库 > 转换为回文的步数

转换为回文的步数

2024-07-17 13:11:26   226人阅读

 

James找到了他的朋友Harry要给女朋友的情书。James很爱恶作剧，所以他决定要胡搞一下。他把信中的每个单字都变成了回文。对任何给定的字符串，他可以减少其中任何一个字符的值，例如‘d‘可以变成‘c‘，这算是一次操作。(另外，他最多只能将字符的值减少至‘a‘，‘a‘不能再被减少成‘z‘)。找出将给定字符串转换成回文所需的最少操作次数。

输入格式 
第一行包含整数 T 代表测试数据的组数。 
接着 T 行各包含一个字符串。

输出格式 
每个测试数据各输出一行，代表此数据需要的最少操作次数。

取值范围 
1 ≤ T ≤ 10
1 ≤ 字符串长度 ≤ 104

样例输入 #00

3abcabcbaabcd

样例输出 #00

204

样例解析

第一组数据：ab*c* -> ab*b* -> ab*a*。 
第二组数据：abcba本身已经是回文了。 
第三组数据：abc*d* -> abc*c* -> abc*b* -> abc*a* = ab*c*a -> ab*b*a。

 1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 int getChangeToPalindromeStep(char *string); 5  6 int main(int argc, const char * argv[]) 7 { 8  9     // insert code here...10 //    printf("Hello, World!\n");11     int stringCount = 0;12 //    printf("input string count: ");13     scanf("%d", &stringCount);14     int totalStep = 0;15     int stepCount[10];16     for (int i=0; i<stringCount; i++) {17 //        printf("input string%d : \n", i);18         char string[10000];19         scanf("%s", string);20 //        printf("%s\n", string);21         stepCount[i] = getChangeToPalindromeStep(string);22 //        printf("need step : %d\n", stepCount);23         totalStep += stepCount[i];24     }25     for (int i=0; i<stringCount; i++) {26         printf("%d\n", stepCount[i]);27     }28 //    printf("total need step : %d\n", totalStep);29     return 0;30 }31 32 int getDiffValue(char *c1, char *c2)33 {34     int ic1 = (int)*c1;35     int ic2 = (int)*c2;36     return (int)fabs(ic1 - ic2);37 }38 39 int getChangeToPalindromeStep(char *string)40 {41     if (string == NULL) {42         return 0;43     }44     if (strlen(string) == 0 || strlen(string) == 1) {45         return 0;46     }47     48     int posStart = 0;49     int posEnd = (int)strlen(string) - 1;50     51     int step = 0;52     while (posStart < posEnd) {53         step += getDiffValue(string + posStart, string + posEnd);54         posStart++;55         posEnd--;56     }57     58     return step;59 }
代码

 


联系
我们