google竞赛题SecretSum的C++解法

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;

其中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[

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!