回文字符串

发布时间:2016-12-6 16:15:43 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"回文字符串",主要涉及到回文字符串方面的内容,对于回文字符串感兴趣的同学可以参考一下。

回文字符串 这是一道在线编程的题目,题目详情:   回文字符串是指从左到右和从右到左相同的字符串,现给定一个仅由小写字母组成的字符串,你可以把它的字母重新排列,以形成不同的回文字符串。   输入:非空仅由小写字母组成的字符串,长度不超过100;   输出:能组成的所有回文串的个数(因为结果可能非常大,输出对1000000007取余数的结果)。   例如:输入"aabb" 输出为2(因为“aabb”对应的所有回文字符串有2个:abba和baab)   函数头部 c: int palindrome(const char *s); c++ int palindrome(const string &s); java public static int palindrome(String s) ;  我的解题思路   根据回文字符串的特点,可以知道,一个字符串如果是回文字符串,那么字符串需要满足的条件:字符串中每个字母的个数必须是偶数,或者整个字符串只有一个字母的个数是奇数!比如串"aabbccccdd"即每个字母个数均为偶数,又如“aaabbcc”,只有一个字母a的个数是奇数,得到解题方法: 1、计算字符串的长度Lenth,统计每个字母的长度,存入数组arr[26]中,下标与字母的ASCII码相对应 2、回文字符串的个数result =  (Lenth / 2)! / ∏  (arr[ n ]/2)!  ,n = 0,1,2,3 ……,25,即26个字母   举个例子会更加清晰,比如字符串“aaabbccccdd”,  a :3个,  b:2个 , c:4个, d:2个 ,字符串长度为11,那么按公式来算就是   result = (11/2)! / 【(a/2)! * (b/2)! * (c/2)! * (d/2)! 】= 5! / (1! * 1! * 2! * 1!) = 120 / 2 = 60,这个方法是采用数学里面的排列组合的知识,应该是高中学的!   有学过排列组合的人应该不难想到这种解题方法,但是公式中使用了大量的阶乘,要知道阶乘比指数增长更快更恐怖,int,long等类型的变量是无法存储那么大的数字的,比如20的阶乘是243 2902 0081 7664 0000,程序可能会用到50的阶乘,各个类型的范围如下: unsigned   int  :0~4294967295    int  :2147483648~2147483647   (10位) unsigned long :0~4294967295 long  : 2147483648~2147483647  long long的最大值:9223372036854775807  (19位) long long的最小值:-9223372036854775808 unsigned long long的最大值:18446744073709551615  (20位) __int64的最大值:9223372036854775807 __int64的最小值:-9223372036854775808 unsigned __int64的最大值:18446744073709551615   正因为数据如此庞大,题目才会提出对1000000007取模的要求,我尝试了很多方法,试图避免溢出的情况,最后得到一个比较合适的方法,既然数值有可能溢出,那么我们可以采用化整为零的方法,不直接计算分子中的(Lenth/2)!,将其认为两步走,   第一步,在做 (Lenth/2)!的同时( sum存储结果,sum = sum * k,k = 1,2,3 ……Lenth/2),对(arr[ n ]/2)! 做除法,根据数学的常识,存在k使得sum能被(arr[ n ]/2)! 整除,直到(arr[ n ]/2)! 整除结束,即n = 25结束,记下此时的 sum 和 k;   第二步,继续做(Lenth/2)!,开始位置为 iter= k+ 1,result = sum(result即回文字符串的个数),循环体为result = (result * iter) % 1000000007;  iter = k+1,k+2,……Lenth/2; 循环结束时得到result的值,该值就是回文字符串的个数!   注:再啰嗦一点,来解释一下循环体的内容result = (result * iter) % 1000000007,如果在循环体中不对1000000007取余,很可能会出现溢出的情况,其数学原理为:对于整数a ,M ,r有 a % M = r, 那么 存在k,使得 a = kM + r,两边同时乘以n,得到na = knM + nr, 所以有(na) % M = (nr) % M    以上便是我对这个题目的理解,下面将贴出我的程序的关键算法: for(iter = 1; iter <= len/2; iter++) { MUL = MUL * iter; while((arr[iterM] ==0 || arr[iterM] == 1) && iterM <26 ) { iterM++; } if(iterM < 26 && MUL % arr[iterM] == 0) { MUL = MUL / arr[iterM]; iterM++; } if(iterM >= 26) { death = iter ; result = MUL; break; } } for(iter = death + 1; iter <= len/2 ; iter++) { result = (result * iter) % 1000000007; } MUL初值为1,数组arr[26]中存储的数值不是每个字母的个数,而是(字母个数/2)的阶乘,对,想必您也考虑到了,这里可能会出现溢出的情况,如果极端一点,字符串中存在一个字母的个数超过了50,算一下25的阶乘,那么这个算法就会溢出了,但是这种情况好像也可以特殊处理,我暂时还没想到比较好的办法,希望在这得到大神的指教!   我的程序最终顺利通过了在线编程系统的检测,并且获得了相应的10个积分!下面罗列一些正确的测试用例,供大家使用!我没有贴出完整代码,需要的可以留下邮箱地址! 用例1: s = “xvwsxafqkcawfchxggvsxkq”       result = 19958400 用例2: s = “hqaymehhrsfuqrpahrimsxftuxqrpsejouuehaqtsryxjhearxmogmi”       result = 676517829 用例3: s = “zsmjajrycysuqjvyyraqvoyggmjgsuiyvclurvmygoivmsurgxsyyblvbgxsszlsly”       result = 493584849 用例4: s = “btxgnhdjscrqkqvwzrhtqlekxrgettfvtzcfhtzlhqckkdkntwwrotzzfskddocobfdrkvqozkrxoqqjxcvdcqwo”       result = 376760527 注:本博客与博客园上的博客为同一博客主:http://www.cnblogs.com/bestDavid/

上一篇:关于IOCP的探讨
下一篇:防止sql注入的源代码

相关文章

关键词: 回文字符串

相关评论