分类： C/C++
2008-04-23 22:02:57
google 竞赛题 SecretSum 的 C 解法
作者：
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<=899; i )
{
for ( j = 100; j <= 999-i; j )
{
if ( 匹配成功)
{
count ;
}
}
}
这么一来需要判断的组合数量变成
800 799 ...... 1
=320400(种)
比原先减少了近一半。但数量依旧庞大。
void init(string **pStr)
{
int i,j;
memset(m_linePattern,0,sizeof(m_linePattern));
for ( i = 0 ; i< 3; i )
{
char ch[3];
for ( j = 0; j<3; j )
{
ch[j] = (*pStr[i])[j];
}
if ( ch[0]==ch[1]) m_linePattern[i][0]=1;//比较0,1位置
if ( ch[0]==ch[2]) m_linePattern[i][1]=1;//比较0,2位置
if ( ch[1]==ch[2]) m_linePattern[i][2]=1;//比较1,2位置
}
}
我又添加了成员函数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< 3; i )
if ( com[i] != m_linePattern[idx][i]) return 0;
return 1;
}
这样同时通过了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<=899; i )
{
if ( ! IfNumOk(0, i)) continue;
for ( j = 100; j <= 999-i; j )
{
if ( ! IfNumOk(1, j)) continue;
int maybe[]={i,j,i j};
if ( ! IfNumOk(2, maybe[2])) continue;
if ( IfMatch (maybe))
{
count ;
}
}
}
return count;
}
通过上述方法筛选出的3个候选数时,当字符串中相同字母越多,则符合的数越少.例如当三个字母都相等时,通过筛选的num1,num2的数各只有8个,显然计算速度大大加快.即使最糟糕的情况下num1,num2和result中三个字母各不相同,则通过筛选的组合有166176种,还是远少于优化前的320400(种)了.
typedef struct{
int dim1;
int dim2;
}POS;
其中dim1表示一个字母(数字)的第1维下标值。同理,dim2表示一个字母(数字)的第2维下标值。一个字母可能在多个位置出现，所以我添加了个成员变量来保存每个字母在矩阵中出现的位置:
typedef vector其中m_letterPos[0]保存字母A出现的位置，m_letterPos[1]保存字母B出现的位置，以此类推m_letterPos[25]保存字母Z出现的位置。在字母矩阵中显然许多字母的位置向量为空，空向量对接下去的筛选判断根本没有用处，所以我又添加了个成员变量，来保存不为空的字母位置向量的指针POSVEC; POSVEC m_letterPos[26]; //保存每个字母的出现位置向量的数组