查找所有串联对之和的高效算法 [英] Efficient algorithm to find the sum of all concatenated pairs

问题描述

我参加了CodeSignal实践考试，并且能够通过14/16测试用例解决此问题。您将得到一个向量作为输入（整数列表），并且该解决方案将很长。

I took a practice CodeSignal exam and was able to pass 14/16 test cases for this problem. You are given a vector as input (list of ints) and the solution will be long long.

最初，我只是简单地使用了两个for循环的蛮力解决方案，并添加了当前a [i]合并a [j]到运行总计。但是，我试图通过使用记忆优化。我使用成对的unordered_map来检查是否已经计算了（i，j）对，如果是，则只返回缓存的结果。即使进行了优化，我仍然没有通过任何其他测试用例并获得14/16的结果。我缺少什么见解或优化？

Originally I simply used a brute-force solution of two for loops and adding the current a[i] concat a[j] to a running total. However, I tried to optimize this by using memoization. I used a unordered_map of pairs to check if I already computed the (i,j) pair and if so, simply return the cached result. Even with my optimization, I still don't pass any additional test cases and receive a 14/16 result. What insight or optimizations am I missing?

我发现了类似的在线问题，但是他们的见识似乎不适用于此特定问题。

I have found similar online problems, however their insight doesn't seem to be applicable to this specific problem.

例如：类似问题

问题：

给出一个正整数数组 a ，
您的任务是计算每个可能的concat（a [i]，a [j]）的总和，其中concat（a [i]，a [j]）是串联

Given an array of positive integers a, your task is to calculate the sum of every possible concat(a[i], a[j]), where concat(a[i],a[j]) is the concatenation of the string representations of a[I] and a[j] respectively.

Ex：

a = [10,2]
sol = 1344
a[0],a[0] = 1010
a[0],a[1] = 102
a[1],a[0] = 210
a[1],a[1] = 22
sum of above = 1344

代码：

long long concat(int x, int y)
{
  string str = to_string(x)+to_string(y);
  return stoll(str);
}
long long calculateSum(vector<int> a)
{
  unordered_map<pair<int,int>,long long, hash_pair> memo;
  long long total = 0;
  for(int i = 0; i < a.size(); i++)
  {
    for(int j = 0; j < a.size(); j++)
    {
      auto currPair = make_pair(a[i],a[j]);
      auto got = memo.find(currPair);
      //if it's a new combination
      if(currPair == got.end())
      {
        long long res = concat(a[i],a[j]);
        memo.insert(make_pair(currPair,res));
        total += res;
      }
      //we've computed this result before
      else
      {
        total += got->second;
      }
    }
  }
  return total;
}

推荐答案

让我们计算贡献 a_i 整数可成对回答。有两种情况。第一种情况是数字 a_i 是低位部分。当总和为 n * a_i 来回答时（ n 是整数整数）。第二种情况很重要。然后，以十进制表示法查找所有偏移量。用 k_j 表示为整数整数长度 j （十进制表示的长度）。然后对所有值 j （）的高部分加答案 k_j * a_i * 10 ^ j 1< = j< = 7 ）。知道了 k_j ，我们可以计算线性时间内所有 a_i 的答案。

Let's calculate the contribution a_i integer to answer in all pairs. There are two cases. The first case when number a_i is low part. When total sum is n * a_i to answer (n is total number integers). The second case is high part. Then let's find all offsets in decimal notation. Denote by k_j as total number integers length j (length in decimal notation). Then high part add to answer k_j * a_i * 10^j for all value j (1 <= j <= 7). Knowing k_j we can calculate the answer for all numbers a_i in linear time.

这篇关于查找所有串联对之和的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！