分享
 
 
 

C++解的一道Google Top Coder 850分的题目

王朝c/c++·作者佚名  2007-08-10
窄屏简体版  字體: |||超大  

今天看了我旁边一哥们的Blog(http://www.chenshuo.com/) ,仔细研究了一下他做的一道Top coder的题目(其实以前就看了,只是一直没时间去研究,呵呵).看完题做了一下,然后看他的答案,两人的想法竟然是一致的,只是思考的过程略有不同,在此还是把我的思路写出来.

原题如下(注:引自http://www.chenshuo.com/,我没去top coder看过,只是根据chenshuo的Blog上面的题做的)

假设有这样一种字符串,它们的长度不大于26,而且若一个这样的字符串其长度为

m,则这个字符串必定由a, b, c, . . . , z 中的前m 个字母构成,同时我们保证每个字母出

现且仅出现一次。比方说某个字符串长度为5,那么它一定是由a, b, c, d, e 这5 个字母

构成,不会多一个也不会少一个。嗯嗯,这样一来,一旦长度确定,这个字符串中有哪些

字母也就确定了,唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母A 和B 构成的序列来描述这类字符串里各个字母的前

后顺序:

1. 如果字母b 在字母a 的后面,那么序列的第一个字母就是A(After),否则序列的

第一个字母就是B(Before);

2. 如果字母c 在字母b 的后面,那么序列的第二个字母就是A,否则就是B;

3. 如果字母d 在字母c 的后面,那么??不用多说了吧?直到这个字符串的结束。

这规则甚是简单,不过有个问题就是同一个AB 序列,可能有多个字符串都与之相

符,比方说序列"ABA",就有"acdb"、"cadb" 等等好几种可能性。说的专业一点,这一

个序列实际上对应了一个字符串集合。那么现在问题来了:给你一个这样的AB 序列,

问你究竟有多少个不同的字符串能够与之相符?或者说这个序列对应的字符串集合有多

大?注意,只要求个数,不要求枚举所有的字符串。

注:如果结果大于10 亿就返回-1。

我把题目总结为:给定一个字符串"ABAB..."(以下称为模式串),计算出符合要求的所有"abcd..."字符串(以下称为结果串)的个数.

要解答这个问题,首先需要明确两点(为什么就不要说了吧,呵呵):

1. 如果模式串的长度为n,那么结果串的长度为n+1

2. 一个模式串至少对应一个结果串,一个结果串对应而且只能对应一个模式串

下面我把我的思考过程写出来:

一. 从一个给定的模式串递推出所有的结果串,假设给定的模式串是"ABAB":

1.对于第一个字母"A",那么结果串只能是"ab"

2.对于第二个字母"B",说明c在b之前,而b之前有2个空位可以插入,所以可能的结果串是"cab","acb"

3.对于第三个字母"A",说明d在c之后.在"cab"中,d可以插到3个空位中,可能的结果串是"cdab","cadb","cabd";在"acb"中,d可以插到2个空位中----"acdb","acbd".所以总的可能数是5

4.对于第四个字母"B",同样的道理可以算出总的可能的结果串有16个.

二. 总结一下刚才的递推过程,可以发现每一次递推只和前一次递推的结果和模式串相应位置的字母有关,而模式串是给定的,所以确切的说,只和前一次递推结果中最大字母(最大字母指的是按字母排序的大小,如z>y>x>...>c>b>a)的位置有关.

现在有点事没时间写了,明天接着写,不过规律已经给出了,就是根据前一次结果的最大字母的位置来计算.大家可以先自己想想.

接着写.

既然找到了问题的本质,那么就构造一个数据结构存储每次递推的最大字母的位置即可.本题可以用一个简单数组记录便可.如下所示,用一个整型数组num记录.(数组的具体大小视情况而定,在此不做细究,题目中说不会大于26).num[a] = b的含义是,在位置a上(第a位上)最大字母出现的次数是b次.

const int maxNum = 30;

int num[maxNum];

用string moduleString;记录模式串.

程序的思想是:

1. 输入模式串的长度为n时,从模式串的第一个字母开始递推.

2. 数组num的第一位即num[0]做边界处理,真正的记录从num[1]开始.

3. 在递推时,如果当前字母是”A”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”右边的情况有几种.如果是”B”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”左边的情况有几种

下面举个具体的例子来分析:以输出”ABAB”为例,每一行表示每次递推之后num数组的变化

模式串/位置

第零位

第一位

第二位

第三位

第四位

第五位

A

0

0

1

AB

0

1

1

0

ABA

0

0

1

2

2

ABAB

0

5

5

4

2

0

1) A: 此时最大字母为b,显然它出现在第2位(记住第零位永远是0,真正的记录从第一位开始)

2) AB:此时最大字母为c,它要求出现在b之前,分别是cab,acb.所以c在第一位,第二位上各出现一次.

3) ABA: 此时最大字母为d,它要求出现在c之后.显然d出现在第一位是不可能的,所以在第一位出现的次数是0.因为c在前一次结果的第一位出现过一次,所以d在那种情况下可以在第二位出现一次.下面来看d在第三位可能出现的次数,因为前一次结果中,在第三位之前c出现过2次,那么d可以在那两种情况下出现在第三位,所以d在第三位出现的次数为2.最后看d在第四位出现的次数,还是因为前一次结果中c在第四位之前出现的次数是2次,所以d在第四位出现的次数是2

4) ABAB: 此时最大字母是e,计算它出现的次数的方法和前面的一样,只是它要求是在前一次最大字母d的左边,只要反过来从右往左遍历就行了,在此不再累述.

最终的程序为:

int main(int argc, char* argv[])

{

const int maxNum = 30;

int num[maxNum]; //num[0] = 0;

string moduleString;

int length;

cout<<"Input Module String"<<endl;

cin>>moduleString;

length = moduleString.length();

if(moduleString[0] == 'A')

{

num[1] = 0;

num[2] = 1;

}

else

{

num[1] = 1;

num[2] = 0;

}

num[0] = 0;

int preNum0 = 0;

int preNum1 = 0;

for(int i = 1; i < length; i++)

{

if(moduleString[i] == 'A')

{

preNum0 = num[0];

preNum1 = num[1];

for(int j = 1; j <= i+2; j++)

{

num[j] = num[j-1] + preNum0;

preNum0 = preNum1;

preNum1 = num[j+1];

}

}

else

{

num[i+2] = 0;

for(int j = i+1; j > 0; j--)

{

num[j] = num[j+1] + num[j];

}

}

}

int totalNum = 0;

for(int i = 0;i < length + 2;i++)

{

totalNum += num[i];

}

cout<<totalNum<<endl;

return 0;

}

对程序的几点说明:

1. 该程序缺少头部信息.(<string>,<iostream>)

2. 该程序已调试通过,为可用版本

3. 该程序的输入为一个形如”ABA..”的模式串,输出为符合要求的结果串的个数.

4. 该程序的时间复杂度为n^2

5. 该程序只为展示如何解决此类问题,输入输出可能与原题不符,相信读者可根据此程序作少许修改以通过Top coder的测试.

写了这么多,也不知道自己有没有讲清楚,呵呵,我的语言表达能力还有待提高,要是大家看了有什么不明白或者有什么建议的话,可以随时联系我(jiangbiao0827@163.com),或者留言即可.

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有