找到所有串联对之和的高效算法

Question

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

最初我只是简单地使用了两个 for 循环的强力解决方案并将当前的 a[i] concat a[j] 添加到运行总数。但是，我试图通过使用记忆来优化这一点。我使用 unordered_map 对来检查我是否已经计算了 (i,j) 对，如果是，只需 return 缓存结果。即使进行了优化，我仍然没有通过任何额外的测试用例并收到 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 个整数来回答所有对。有两种情况。第一种情况，number a_i 是低位部分。当总和为n * a_i时作答（n为总数整数）。第二种情况是高部分。然后让我们找到十进制表示法中的所有偏移量。用k_j表示为总数整数长度j（十进制长度）。然后高部分添加到所有值 j (1 <= j <= 7) 的答案 k_j * a_i * 10^j。知道 k_j 我们可以在线性时间内计算出所有数字 a_i 的答案。

Answer 2

我在一个在线评估平台上遇到了完全相同的问题。以下 python 解决方案通过了所有测试用例。

import collections
def concatenatSum(a):
    tot = 0
    dic = collections.defaultdict(int)
    for i in range(len(a)):
        _str = str(a[i])
        n = len(_str)
        dic[n]+=1
    
    for i in  range(len(a)):
        for k,v in dic.items():
            tot+=a[i]*(v*pow(10,k))
        tot+=(a[i]*len(a))
    
    return tot

Answer 3

以下 Java 解决方案通过了我认为的所有测试用例。

long concatenationsSum(int[] a) {
    long[] ans = new long[1];
    long[] total = new long[1];
    Map<Integer, Integer> powMap = new HashMap<>();
    for(int i = 0; i < a.length; ++i){
        int currentPow = (int)Math.log10(a[i]);
        powMap.put(currentPow, powMap.getOrDefault(currentPow, 0)+1);
        total[0] += a[i];
    }
    powMap.put(-1, a.length);
    powMap.forEach((key, val)-> ans[0] +=(long)Math.pow(10, key+1)*total[0]*val);
    return ans[0]; }

Answer 4

JS 解决方案通过了所有测试用例：

function concatenationsSum(arr) {
   let inimSum = 0;
   let offsetSum = 0;
   arr.forEach(el => {
      inimSum += el;

      const size = el.toString().length;
      const offset = Math.pow(10, size);
      offsetSum += offset;
   });

   return inimSum * arr.length + inimSum * offsetSum;
}

Answer 5

这是一个有效的 Java/8-11 解决方案，实现了@aropan 解释：

 static long solution(int[] a){
    java.util.Map<Integer,Integer> intToLength = new java.util.HashMap();
    int len = a.length;
    int[] lengths = new int[len];//track the length of each elements to avoid including it when doing the k_j*a[i]*10^j calculation.
    for(int i=0; i<len; i++){
        int l = (int)Math.log10(a[i])+1;
        lengths[i] = l;
        intToLength.compute(l, (k, v) -> v == null ? 1 : v+1);
    } 

    long sum = 0;
    for(int i=0; i<len; i++){
        sum += len*a[i];
        //k_j*a[i]*10^j calculation
        long x = 0;
        for(var e : intToLength.entrySet()){
            int k_j = 0;
            if(lengths[i] == e.getKey())
                k_j--;//exclude a[i] length
            k_j+=e.getValue();
            x += k_j*a[i]*(long)Math.pow(10, e.getKey());
        }
        sum += x;
    }
    return sum;
}

找到所有串联对之和的高效算法

Efficient algorithm to find the sum of all concatenated pairs

c++

algorithm

combinatorics