google 竞赛题 SecretSum 的 C++ 解法

【 tulaoshi.com - C语言心得技巧 】

google 竞赛题 SecretSum 的 C++ 解法

作者： roc

下载源代码

　　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<=89