1

问题：“一种找出六位数字的数量的算法，其中前三位数字的总和等于后三位数字的总和。”

我在一次采访中遇到了这个问题，想知道最好的解决方案。这是我到现在为止的。

方法 1：蛮力解决方案当然是检查每个数字（100,000 到 999,999 之间）的前三位数字和后三位数字的总和是否相等。如果是，则增加某个计数器，该计数器保持对所有此类数字的计数。

但这会检查所有 900,000 个数字，因此效率低下。

方法2：既然我们被问到“有多少”这样的数字而不是“哪些数字”，我们可以做得更好。将数字分为两部分：前三位（从 100 到 999）和后三位（从 000 到 999）。因此，候选数字的任一部分的三位数字之和的范围可以从 1 到 27。
* 为每个部分维护一个std::map<int, int>，其中 key 是总和，value 是在相应部分中具有该总和的数字的数量（3 位）。
* 现在，对于第一部分中的每个数字，找出其总和并更新相应的地图。
* 同样，我们可以获得第二部分的更新地图。* 现在通过将相应的对相乘（例如，键 4 的映射 1 中的值和键 4 的映射 2 中的值）并将它们相加，我们得到了答案。

在这种方法中，我们最终会检查 1K 个数字。

我的问题是我们如何进一步优化？有更好的解决方案吗？

4

5 回答 5

6

对于0 <= s <= 18，有确切的10 - |s - 9|方法来获得s两位数的总和。

所以，对于第一部分

int first[28] = {0};
for(int s = 0; s <= 18; ++s) {
    int c = 10 - (s < 9 ? (9 - s) : (s - 9));
    for(int d = 1; d <= 9; ++d) {
        first[s+d] += c;
    }
}

那是 19*9 = 171 次迭代，对于后半部分，类似地执行，内部循环从 0 而不是 1 开始，即 19*10 = 190 次迭代。然后求和first[i]*second[i]。1 <= i <= 27

于 2012-10-25T00:54:35.033 回答
1

生成所有三位数字；根据它们的数字总和将它们划分为集合。（实际上，您需要做的就是保留一个计算集合大小的向量）。对于每个集合，可以生成的六位数字的数量是集合平方的大小。将设置大小的平方相加得到你的答案。

int sumCounts[28]; // sums can go from 0 through 27
for (int i = 0; i < 1000; ++i) {
    sumCounts[sumOfDigits(i)]++;
}
int total = 0;
for (int i = 0; i < 28; ++i) {
    count = sumCounts[i];
    total += count * count;
}

编辑变体以消除计数前导零：

int sumCounts[28];
int sumCounts2[28];
for (int i = 0; i < 100; ++i) {
    int s = sumOfDigits(i);
    sumCounts[s]++;
    sumCounts2[s]++;
}
for (int i = 100; i < 1000; ++i) {
    sumCounts[sumOfDigits(i)]++;
}
int total = 0;
for (int i = 0; i < 28; ++i) {
    count = sumCounts[i];
    total += (count - sumCounts2[i]) * count;
}
于 2012-10-25T00:38:10.517 回答
1

Python 实现

def equal_digit_sums():
dists = {}
for i in range(1000):
    digits = [int(d) for d in str(i)]
    dsum = sum(digits)
    if dsum not in dists:
        dists[dsum] = [0,0]
    dists[dsum][0 if len(digits) == 3 else 1] += 1
def prod(dsum):
    t = dists[dsum]
    return (t[0]+t[1])*t[0]
return sum(prod(dsum) for dsum in dists)

print(equal_digit_sums())

结果：50412

于 2013-12-17T03:48:52.910 回答
0

一个想法：对于从 0 到 27 的每个数字，计算具有该数字和的三位数字的数量。这应该可以通过 DP 风格的方法有效地实现。

现在您只需将结果的平方相加，因为对于每个答案，您可以用每边一个数字组成一个六位数。

于 2012-10-25T00:37:28.783 回答
0

假设不允许使用前导 0，您需要计算有多少种不同的方法可以用 3 位数求和到 n。要计算，您可以在 for 循环内有一个 for 循环。所以：

firstHalf = 0
for i in xrange(max(1,n/3),min(9,n+1)): #first digit
  for j in xrange((n-i)/2,min(9,n-i+1)): #second digit
    firstHalf +=1  #Will only be one possible third digit
secondHalf = firstHalf + max(0,10-|n-9|)

如果您试图对一个数字求和，那么最后一个数字始终是唯一确定的。因此，在第一个数字为 0 的情况下，我们只是在计算第二个数字可能有多少不同的值。如果 n 小于 10，这将是 n+1。如果 n 大于，直到 18 它将是 19-n。超过 18 岁没有办法形成总和。如果你遍历所有 n，从 1 到 27，你将得到你的总和。

于 2012-10-25T00:53:22.717 回答