google比赛题SecretSum的C++解法
副标题#e#
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.
#p#副标题#e#
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(种) 比原先淘汰了近一半。但数量依旧复杂。
继承省题，我从"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)来完成此事情.代码如下:
#p#分页标题#e#
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(种)了.
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;
#p#分页标题#e#
个中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 ; i< 3; i++)
{
char ch[3];
for ( j = 0; j<3; j++)
{
ch[j] = (*pStr[i])[j];
POS ps={i,j};
m_letterPos[ch[j]-''A''].push_back(ps);//将坐标生存到相应向量中
}
//计较各个字母的匹配矩阵
if ( ch[0]==ch[1]) m_linePattern[i][0]=1;
if ( ch[0]==ch[2]) m_linePattern[i][1]=1;
if ( ch[1]==ch[2]) m_linePattern[i][2]=1;
}
for ( i = 0; i<26; i++)
{
if (m_letterPos[i].size()>0)
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 <3; i++)
sprintf(numChar[i],"%d",maybe[i]);//将数字转换成字符串
for ( i = 0; i < m_posptrVec.size(); i++)//遍历所有呈现的字母
{
POSVEC &ps= (*m_posptrVec[i]);
int ch = numChar[ps[0].dim1][ps[0].dim2]-''0'';//取得该字母第一个位置处的数字
if ( bUse[ch] ) return 0; //假如数字已被利用就返回0
//逐一较量其他位置出的数字是否都沟通
j=1;
while( j < ps.size() )
{
int ch2 = numChar[ps[j].dim1][ps[j].dim2]-''0'';
if (ch != ch2 ) return 0;
j++;
}
bUse[ch] = 1;//将该数字配置为已被利用
}
return 1;
}
2.4.最后将这个类的实现代码汇总如下:
#include <string>
#include <vector>
#include <stdlib.h>
#include <iostream>
using namespace std;
//****************************************************************
//类名：SecretSum
//作者：roc（[email protected]）
//日期：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; 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;
}
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];
POS ps={i,j};
m_letterPos[ch[j]-''A''].push_back(ps);//将坐标生存到相应向量中
}
//计较各个字母的匹配矩阵
if ( ch[0]==ch[1]) m_linePattern[i][0]=1;
if ( ch[0]==ch[2]) m_linePattern[i][1]=1;
if ( ch[1]==ch[2]) m_linePattern[i][2]=1;
}
for ( i = 0; i<26; i++)
{
if (m_letterPos[i].size()>0)
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 <3; i++)
sprintf(numChar[i],"%d",maybe[i]);//将数字转换成字符串
for ( i = 0; i < m_posptrVec.size(); i++)//遍历所有呈现的字母
{
POSVEC &ps= (*m_posptrVec[i]);
int ch = numChar[ps[0].dim1][ps[0].dim2]-''0'';//取得该字母第一个位置处的数字
if ( bUse[ch] ) return 0; //假如数字已被利用就返回0
//逐一较量其他位置出的数字是否都沟通
j=1;
while( j < ps.size() )
{
int ch2 = numChar[ps[j].dim1][ps[j].dim2]-''0'';
if (ch != ch2 ) return 0;
j++;
}
bUse[ch] = 1;//将该数字配置为已被利用
}
return 1;
}
int IfNumOk(int idx, int num)
{
char temp[4];
int com[3]={0};
sprintf(temp,"%d",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;
}
protected:
POSVEC m_letterPos[26]; //生存每个字母的呈现位置向量的数组
POSPTRVEC m_posptrVec; //生存呈现的字母向量的指针
int m_linePattern[3][3];//生存每个字符串匹配范例的数组
};
三、小结
#p#分页标题#e#
利用上述的代码对题中给出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}型的计较尚有优化的余地，限于时间和精神我没有继承优化下去。接待列位好手，配合探讨，给出更优的办理方案。
