c++ - 找到所有连接对的总和的高效算法

Question

我参加了 CodeSignal 练习考试，并且能够通过 14/16 测试用例来解决这个问题。您将获得一个 vector 作为输入(整数列表)，并且解决方案将很长很长。

最初我只是使用了两个 for 循环的蛮力解决方案，并将当前的 a[i] concat a[j] 添加到运行总数中。但是，我尝试通过使用内存来优化它。我使用 unordered_map 对检查我是否已经计算了 (i,j) 对，如果已经计算，只需返回缓存的结果。即使进行了优化，我仍然没有通过任何额外的测试用例并收到 14/16 的结果。我缺少什么见解或优化？

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

例如:Similar Problem

问题:

给定一个正整数数组 a ，
您的任务是计算每个可能的 concat(a[i], a[j]) 的总和，其中 concat(a[i],a[j]) 是 a[I] 和 a 的字符串表示的串联[j] 分别。

前任:

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;
}

Answer 1

让我们计算贡献 a_i 整数来回答所有对。有两种情况。 a_i 数为低部分时的第一种情况。当总和是 n * a_i 时回答( n 是总数整数)。第二种情况是高分。然后让我们找到十进制表示法中的所有偏移量。由 k_j 表示为总数整数长度 j(十进制长度)。然后高部分添加回答 k_j * a_i * 10^j 所有值 j ( 1 <= j <= 7 )。知道 k_j 我们可以在线性时间内计算所有数字 a_i 的答案。