pzz
C++博客
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
随笔：8 文章：35 评论：3 引用：0
庞果会-回文字符串
1.一开始想法是对的，就是（总长度/2）！/（每个字母i出现的次数/2）! ,一开始用c++写的代码，错误是因为数据溢出，而java的BigInteger对于处理大数据的加减乘除是最适合不过的啦
下面是写得两个代码：
c++代码
1
int
_init(
string
s,
int
countnum[])
2
{
3
int
len=s.length();
4
for
(
int
i=0;i<len;i++)
5
countnum[s[i]-'a']++;
6
return
len;
7
}
8
int
palindrome(
const
string
&s)
9
{
10
int
countnum[26],visit[26];
11
int
alphanum;
12
memset(countnum,0,
sizeof
(countnum));
13
memset(visit,0,
sizeof
(visit));
14
alphanum=_init(s,countnum);
15
int
is_palindrome=0;
16
for
(
int
i=0;i<26;i++)
17
{
18
if
(countnum[i]%2==1) {
19
is_palindrome++;
20
visit[i]=1;
21
}
22
}
23
if
(is_palindrome>1)
return
0;
24
else
25
{
26
long
long
sum=1;
27
//
则除去中间的一个字母还有两边的字母，(alphanum-1)/2
28
if
(is_palindrome==1){
29
for
(
int
i=1;i<=(alphanum-1)/2;i++)
30
sum=((sum*i)%MAX_VALUE);
31
for
(
int
i=0;i<26;i++)
32
{
33
if
(countnum[i]>0)
34
{
35
if
(visit[i]!=1){
36
for
(
int
j=2;j<=(countnum[i]/2);j++)
37
{
38
sum=(sum/j)%MAX_VALUE;
39
}
40
}
41
else
42
{
43
for
(
int
j=2;j<=(countnum[i]-1)/2;j++)
44
{
45
sum=(sum/j)%MAX_VALUE;
46
}
47
}
48
}
49
}
50
}
51
else
52
{
53
for
(
int
i=1;i<=(alphanum)/2;i++)
54
sum=((sum*i)%MAX_VALUE);
55
for
(
int
i=0;i<26;i++)
56
{
57
if
(countnum[i]>0)
58
{
59
if
(visit[i]!=1){
60
for
(
int
j=2;j<=(countnum[i]/2);j++)
61
{
62
sum=(sum/j)%MAX_VALUE;
63
}
64
}
65
else
66
{
67
for
(
int
j=2;j<=(countnum[i]-1)/2;j++)
68
{
69
sum=(sum/j)%MAX_VALUE;
70
}
71
}
72
}
73
}
74
}
75
return
sum%MAX_VALUE;
76
}
77
}
78
Java代码
参考文章：
http://blog.csdn.net/u011459840/article/details/9667077
1
public
static
int
palindrome(String s) {
2
int
[]countnum=
new
int
[26];
3
int
len=s.length();
4
int
is_can=0;
5
if
(s==
null
||s.length()>100||s.length()<1)
return
0;
6
for
(
int
i=0;i<len;i++)
7
{
8
countnum[s.charAt(i)-'a']++;
9
}
10
for
(
int
i=0;i<26;i++){
11
if
(countnum[i]%2==1){
12
is_can++;
13
}
14
}
15
if
(is_can>1)
return
0;
16
else
17
{
18
//
求阶乘(len/2)!
19
BigInteger result=BigInteger.ONE;
20
for
(
int
i=1;i<=(len/2);i++){
21
result=result.multiply(BigInteger.valueOf(i));
22
}
23
BigInteger dividevalue=BigInteger.ONE;
24
for
(
int
i=0;i<26;i++)
25
{
26
if
(countnum[i]>0){
27
for
(
int
j=1;j<=(countnum[i]/2);j++){
28
dividevalue=dividevalue.multiply(BigInteger.valueOf(j));
29
}
30
}
31
}
32
result=result.divide(dividevalue);
33
return
result.mod(BigInteger.valueOf(1000000007)).intValue();
34
}
35
发表于 2013-08-01 21:43
pzz
阅读(108)
评论(0)
编辑
收藏
引用
所属分类:
庞果会英雄挑战赛
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2024年5月
>
日
一
二
三
四
五
六
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
一些记录(4)
(rss)
一些算法思路(2)
(rss)
随笔档案
2013年2月 (1)
2012年5月 (7)
文章分类
ACM 搜索(1)
(rss)
ahstu_oj(2)
(rss)
c/c++(8)
(rss)
c++基本常识(1)
(rss)
linux嵌入式(5)
(rss)
linux系统下遇到的奇怪问题(1)
(rss)
oj题目思路(2)
(rss)
操作系统(1)
(rss)
成长记录
(rss)
读书(1)
(rss)
九度oj(1)
(rss)
庞果会英雄挑战赛(1)
(rss)
深入理解计算机系统札记
(rss)
树状数组(1)
(rss)
思维火花
(rss)
算法学习(1)
(rss)
网络流
(rss)
线段树
(rss)
杂感
(rss)
状态dp
(rss)
字符串匹配(2)
(rss)
文章档案
2014年5月 (3)
2014年4月 (1)
2014年3月 (1)
2014年2月 (1)
2013年11月 (1)
2013年10月 (3)
2013年9月 (2)
2013年8月 (6)
2013年7月 (4)
2013年6月 (2)
2012年5月 (3)
2012年4月 (4)
2012年3月 (4)
友情链接
csdn
豆瓣
杭电酷行天下
老赵
刘若鹏
南阳c小加
搜索
最新评论
1. re: 树状数组和线段树简单题
。。。
--pzz
2. re: 2013我有梦
恩，是的
--pzz
3. re: 2013我有梦[未登录]
支持一吧！实践梦想需要极大的努力
--true
阅读排行榜
1. 2013我有梦(363)
2. nyoj195_飞翔(245)
3. 熟练才是王道 (240)
4. hfut1245_水晶球(240)
5. 群赛(210)
评论排行榜
1. 2013我有梦(2)
2. 技术员状态dp(0)
3. hfut1245_水晶球(0)
4. 搜索札记(0)
5. 群赛(0)