分享
 
 
 

google 竞赛题 SecretSum 的 C++ 解法

王朝vc·作者佚名  2006-01-17
窄屏简体版  字體: |||超大  

google 竞赛题 SecretSum 的 C++ 解法

作者: roc

下载源代码

SecretSum 是本次 google 竞赛中第二轮淘汰赛的一道分值为 500 分竞赛题。事实上,这道题目反而比同轮比赛中的那道 1000 分值的RecurringNumbers 难(RecurringNumbers 的难度水准充其量不过是道初一学生奥数竞赛题)。好了,闲话少叙,来看 SecretSum 的题目吧:

一、竞赛题目

Problem Statement

We can substitute each digit of a number with a unique letter from ''A''

to ''Z''. This way we can write groups of numbers in a single

representation. For example "ABA" can represent any of the following:

101, 151, 343, 767, 929. However, "ABA" cannot mean 555 because each

letter must stand for a distinct digit. Furthermore, numbers cannot

begin with 0 and thus ''A'' cannot be replaced by 0.

Given two such representations num1 and num2 and the result of their

summation return the total number of possible combinations of numbers

for which the equation holds. If no combinations are possible then

return 0.

Definition

Class: SecretSum

Method: countPossible

Parameters: String, String, String

Returns: int

Method signature: int countPossible(String num1, String num2, String

result)

(be sure your method is public)

Constraints

- num1, num2, and result will each contain exactly 3 uppercase letters

(''A'' - ''Z'').

Examples

0)

"AAA"

"BBB"

"CCC"

Returns: 32

1)

"ABB"

"DEE"

"TTT"

Returns: 112

2)

"ABC"

"ABA"

"ACC"

Returns: 0

Leading zeroes are not allowed.

3)

"AAA"

"CDD"

"BAA"

Returns: 32

4)

"TEF"

"FET"

"AAA"

Returns: 12

5)

"ABC"

"ABC"

"BCE"

Returns: 5

We can have the following 5 sums:

124 + 124 = 248

125 + 125 = 250

249 + 249 = 498

374 + 374 = 748

375 + 375 = 750

6)

"AAA"

"AAA"

"BBB"

Returns: 4

We can have the following 4 sums:

111 + 111 = 222

222 + 222 = 444

333 + 333 = 666

444 + 444 = 888

This problem statement is the exclusive and proprietary property of

TopCoder, Inc. Any unauthorized use or reproduction of this information

without the prior written consent of TopCoder, Inc. is strictly

prohibited. (c)2003, TopCoder, Inc. All rights reserved.

题目的意思大致是这样的:数字0-9可以分别用A-Z中不相同的字母替代,这样就可以用字母组成的字符串代表一个数了。例如"ABA"可以代表:

101, 151, 343, 767, 929。但"ABA"不可以代表555,因为不同的字母必须取不同的数字。此外每个作为开头的字母不取0值。编写一个类 SecretSum,该类中有一个原型为 int countPossible(string num1, string num2, string

result)的函数。num1、num2 和 result 就是上面所描述的类型的字符串,其中 result 代表的数为 num1 和 num2 代表的数的和,并且这几个字符串都只含有3个A-Z的字母。返回值为可能取得的组合的总数。

二、我的解题步骤.

2.1 解题框架

根据题意我们很容易看出解此题关键步骤有2个,第一是找出候选的3个数;第二判断传入的3个字符串是否可以代表这3个数

2.2 找出候选的3个数

由于第一个字母不会是0,所以三个字母所代表的数取值范围为100-999。同时由于result为num1与num2的和,当num1和num2确定后,result的值也就确定了。所以3个数中,我们先确定2个数(假设先确定num1,num2),然后用这两个数的和就可以确定第3个数(result)了。这样最笨的方法就是把num1和num2代表的数分别从100-999取一遍。这需要判断900*900=810,000种组合。显然这么筛选效率太低,还可以优化。进一步分析,我们可以发现既然result的最大值可取到999,那么当num1=100时,num2最大值为999-100=899;当num1=400时,num2的最大值为999-400=599.也就是说当num1 = i时,num2的最大值为999-i。这样当num1确定时假设为i,则num2的范围为[100,999-i]。当num2取得最小值100时,num1可以取得最大值999-100=899。所以num1的取值范围为[100,899]。这样遍历num1和num2可取的值的代码如下所示:

int i,j,count=0;

for ( i = 100; i

这么一来需要判断的组合数量变成

800+799+......+1

=320400(种)

比原先减少了近一半。但数量依旧庞大。

继续省题,我从"ABA"不可以代表555的说明中得到提示:在得到一个三位数时,就可以根据不同字母取不同的值来筛掉一批不符合要求的数。怎么实现这种比较呢?我是这么做的,将一个三位数(或字符串)中每一位置的数(或字母)与其他位置的数(或字母)比较,记下比较的结果保存在一个整型数组中,1表示比较结果相同,0表示不相同。还好字符串才3个字母,各个位置的比较总共才三次,分别为(0,1),(0,2),(2,1),例如在"ABA"的比较中:0位置的A和1位置的B比较,显然不等结果为0;0位置的A和2位置的A比较,相等结果为1;1位置的B和2位置的A比较,结果不等为0.结果可以用一个大小为3的数组保存."ABA"的比较结果为{0,1,0};同样的方法来计算929的比较结果为{0,1,0};和"ABA"结果相同,所以"ABA"可以代表929.而555比较结果为{1,1,1},所以"ABA"不可能代表555.由于传入的字符串有3个,我们可以使用3*3大小来保存这个结果.在类中我用int m_linePattern[3][3];这个成员变量来表示.在循环筛选前,应该先把传入的字符串匹配类型计算出来.我添加了成员函数void init(string **pStr)来完成此工作.代码如下:

void init(string **pStr)

{

int i,j;

memset(m_linePattern,0,sizeof(m_linePattern));

for ( i = 0 ; i

我又添加了成员函数int IfNumOk(int idx, int num)来比较num是否符合索引为idx的字符串.匹配成功返回1,失败返回0.代码如下:

int IfNumOk(int idx, int num)

{

char temp[4];

int com[3]={0};

sprintf(temp,"%d",num);//将num转换成字符串

//计算传入数字的匹配结果

if (temp[0] == temp[1] ) com[0]=1;

if (temp[0] == temp[2] ) com[1]=1;

if (temp[2] == temp[1] ) com[2]=1;

//与索引为idx的字符串匹配结果比较

for ( int i=0; i

这样同时通过了IfNumOk筛选的数字才正式进入最后的比较.我添加了函数int IfMatch(int *maybe)来做判断,符合要求时返回1,不符合返回0.至此函数countPossible的代码已可全部确定下来了,代码如下:

int countPossible(string num1, string num2, string result)

{

string *pStr[]={&num1,&num2,&result};

init(pStr);

int i,j,count=0;

for ( i = 100; i

通过上述方法筛选出的3个候选数时,当字符串中相同字母越多,则符合的数越少.例如当三个字母都相等时,通过筛选的num1,num2的数各只有8个,显然计算速度大大加快.即使最糟糕的情况下num1,num2和result中三个字母各不相同,则通过筛选的组合有166176种,还是远少于优化前的320400(种)了.

2.3 判断候选的3个数是否匹配传入的字符串

我是这样判断的:首先在候选的3个数中,在相同字母出现的对应位置的数必须相同.其次,该数字必须是未被使用过的。

后者的实现很简单,添加一个变量 int bUse[10]={0};。bUse[i](i=0-9)的值表示数字i被使用的情况,0表示未被使用过;1表示已经使用过了。初始化时都为0表示都未被使用过。当一个字母出现的对应位置的数都相同时,若这个数字为i,则bUse[i]=1。

在前者的处理中,为了确定位置,我将传入的三个字符串看成一个2维的字母矩阵。num1,num2,result对应的一维下标值分别为0,1,2。该矩阵的第1维下标值和第2维下标值就可看成矩阵中字母的坐标。例如在例1中字母A的坐标为(0,0);D点的坐标为(1,0)。同样的方法也可为候选的3个数中的每个数字确定坐标。我添加了一个结构来保存上述的坐标:

typedef struct{

int dim1;

int dim2;

}POS;

其中dim1表示一个字母(数字)的第1维下标值。同理,dim2表示一个字母(数字)的第2维下标值。一个字母可能在多个位置出现,所以我添加了个成员变量来保存每个字母在矩阵中出现的位置:

typedef vector<POS POSVEC;

POSVEC m_letterPos[26]; //保存每个字母的出现位置向量的数组

其中m_letterPos[0]保存字母A出现的位置,m_letterPos[1]保存字母B出现的位置,以此类推m_letterPos[25]保存字母Z出现的位置。在字母矩阵中显然许多字母的位置向量为空,空向量对接下去的筛选判断根本没有用处,所以我又添加了个成员变量,来保存不为空的字母位置向量的指针

typedef vector<POSVEC* POSPTRVEC;

POSPTRVEC m_posptrVec; //保存出现的字母向量的指针

显然上述2个成员变量同样需要在循环筛选前初始化,代码同样添加到成员函数init中。添加后init代码如下:

void init(string **pStr)

{

int i,j;

memset(m_linePattern,0,sizeof(m_linePattern));

for ( i = 0 ; i0)

m_posptrVec.push_back(&m_letterPos[i]);//将所有出现的字母向量指针保存起来

}

}

具体判断候选的3个数字是否匹配时,先将这3个数字转换到3个字符串数组中去,这个转换可以使用sprintf函数。然后遍历m_posptrVec中非空的位置向量,判断每个保存在相同字母的位置向量中的位置,在相应的候选数字矩阵的相应位置的数是否相等,若相等则设置该数字以被使用,具体的IfMatch代码如下:

int IfMatch(int *maybe)

{

char numChar[3][4];

int bUse[10]={0};

int i,j;

for ( i = 0 ; i

2.4.最后将这个类的实现代码汇总如下:

#include <string

#include <vector

#include <stdlib.h

#include <iostream

using namespace std;

//****************************************************************

//类名:SecretSum

//作者:roc(txqc4@sohu.com)

//日期:2005-12-26

//用途: 本代码为实现上述竞赛题所作。

//注意事项:如欲转载,敬请保持本段说明。

//****************************************************************

class SecretSum{

typedef struct{

int dim1;

int dim2;

}POS;

typedef vector<POS POSVEC;

typedef vector<POSVEC* POSPTRVEC;

public :

int countPossible(string num1, string num2, string result)

{

string *pStr[]={&num1,&num2,&result};

init(pStr);

int i,j,count=0;

for ( i = 100; i0)

m_posptrVec.push_back(&m_letterPos[i]);//将所有出现的字母向量指针保存起来

}

}

int IfMatch(int *maybe)

{

char numChar[3][4];

int bUse[10]={0};

int i,j;

for ( i = 0 ; i 三、小结

使用上述的代码对题中给出7个实例进行实测时,我发现例5的计算过程最慢。一分析发现原来例5中的num1,num2,result,都是{0,0,0}型的,这样最终IfMatch被调用了117662次。而在例4中num1和num2同样是{0,0,0}型的,但由于result为{1,1,1}型,事实上IfMatch最终只被调用了2144次,计算用时尚能忍受。由此可见,我的代码对于num1,num2,都是{0,0,0}型的计算还有优化的余地,限于时间和精力我没有继续优化下去。欢迎各位高手,共同探讨,给出更优的解决方案。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
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- 王朝網路 版權所有