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(種) 比原先減少了近一半。但數量依舊龐大。
繼續省題，我從"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（[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];//保存每個字符串匹配類型的數組
};
三、小結
使用上述的代碼對題中給出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}型的計算還有優化的余地，限於時間和精力我沒有繼續優化下去。歡迎各位高手，共同探討，給出更優的解決方案。
