google 竞赛题 SecretSum 的 C++ 解法

SecretSum 是2005年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(种) 比原先减少了近一半。但数量依旧庞大。

　　继续省题，我从"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< 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;

　　其中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（[e-mail]）
//日期：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];//保存每个字符串匹配类型的数组
};

三、小结
使用上述的代码对题中给出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}型的计算还有优化的余地，限于时间和精力我没有继续优化下去。欢迎各位高手，共同探讨，给出更优的解决方案。