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

本文介绍了查找所有串联对之和的高效算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我参加了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.