私はインタビューの練習の1つでこの問題を抱えていて、O（N ^ 2）以外のより複雑な時間でこれを取得するのに問題がありました。あるレベルでは、リストの各要素にアクセスする必要があります。ハッシュテーブルを使用することを考えましたが、それでもハッシュテーブルを実行してデータを入力してから計算する必要があります。基本的に私の解決策はネストされたforループで、コードも含まれていて、4秒未満の時間例外を除いてすべてを渡しました。
私のコード：
def concatenationsSum(a):
sum = 0
current_index_looking_at = 0
for i in a:
for x in a:
temp = str(i)+str(x)
sum += int(temp)
return sum
問題の説明：
Given an array of positive integers a, your task is to calculate the sum
of every possible a[i] ∘ a[j], where a[i] ∘ a[j] is the concatenation
of the string representations of a[i] and a[j] respectively.
Example
For a = [10, 2], the output should be concatenationsSum(a) = 1344.
a[0] ∘ a[0] = 10 ∘ 10 = 1010,
a[0] ∘ a[1] = 10 ∘ 2 = 102,
a[1] ∘ a[0] = 2 ∘ 10 = 210,
a[1] ∘ a[1] = 2 ∘ 2 = 22.
So the sum is equal to 1010 + 102 + 210 + 22 = 1344.
For a = [8], the output should be concatenationsSum(a) = 88.
There is only one number in a, and a[0] ∘ a[0] = 8 ∘ 8 = 88, so the answer is 88.
Input/Output
[execution time limit] 4 seconds (py3)
[input] array.integer a
A non-empty array of positive integers.
Guaranteed constraints:
1 ≤ a.length ≤ 10^5,
1 ≤ a[i] ≤ 10^6.
[output] integer64
The sum of all a[i] ∘ a[j]s. It's guaranteed that the answer is less than 2^53.
2つの整数の連結：
m ∘ n
等しい：
10**digit_length(n) * m + n
したがって、指定された整数を持つすべてのリスト項目の連結の合計：
(a[0] ∘ n) + (a[1] ∘ n) + …
等しい：
(10**digit_length(n) * a[0] + n) + (10**digit_length(n) * a[1] + n) + …
そして、すべてのnを片側に置くことができます：
(10**digit_length(n) * a[0]) + (10**digit_length(n) * a[1]) + … + n + n + …
配列の各要素には、nにのみ依存する値が乗算されることに注意してください。
10**digit_length(n) * (a[0] + a[1] + …) + n + n + …
再び簡素化：
10**digit_length(n) * sum(a) + len(a) * n
sum(a)は変化せず、len(a) * nすべてnのsのs の合計はlen(a) * sum(a)次のとおりです。
def concatenationsSum(a):
sum_a = sum(a)
return sum(10**digit_length(n) * sum_a for n in a) + len(a) * sum_a
def digit_length(n):
"""
The number of base-10 digits in an integer.
>>> digit_length(256)
3
>>> digit_length(0)
1
"""
return len(str(n))
これは、関係する整数の上限が一定である場合、線形時間で実行されます。を使用math.log10してdigit_length、浮動小数点演算が関係する整数サイズに対して十分正確である限り、高速化することもできます（そうでない場合でも、文字列を使用するよりも実装するための優れた方法があります。 。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加