1

問題: 「最初の 3 桁の合計が最後の 3 桁の合計と等しい 6 桁の数を見つけるアルゴリズム」

インタビューでこの問題に遭遇し、最善の解決策を知りたい. これは私が今まで持っているものです。

アプローチ 1: もちろん、ブルート フォース ソリューションは、各数字 (100,000 から 999,999 の間) について、最初の 3 桁と最後の 3 桁の合計が等しいかどうかを確認することです。はいの場合、そのようなすべての数のカウントを保持する特定のカウンターをインクリメントします。

しかし、これは 900,000 個の数字すべてをチェックするため、非効率的です。

アプローチ 2: そのような数は「どの数」ではなく「いくつ」と尋ねられるため、より適切に行うことができます。数字を 2 つの部分に分割します。最初の 3 桁 (100 から 999 まで) と最後の 3 桁 (000 から 999 まで) です。したがって、候補番号のいずれかの部分の 3 桁の合計は 1 から 27 の範囲になる可能性があり
ますstd::map<int, int>。
* ここで、最初の部分の各数値について、その合計を見つけ、対応するマップを更新します。
* 同様に、2 番目の部分の更新されたマップを取得できます。* ここで、対応するペア (たとえば、キー 4 のマップ 1 の値とキー 4 のマップ 2 の値) を乗算し、それらを合計すると、答えが得られます。

このアプローチでは、最終的に 1K の数字をチェックすることになります。

私の質問は、どうすればさらに最適化できるでしょうか? より良い解決策はありますか？

4

5 に答える 5

6

の場合0 <= s <= 18、正確に 2 桁の和として10 - |s - 9|取得する方法があります。s

では、第一部として

int first[28] = {0};
for(int s = 0; s <= 18; ++s) {
    int c = 10 - (s < 9 ? (9 - s) : (s - 9));
    for(int d = 1; d <= 9; ++d) {
        first[s+d] += c;
    }
}

これは 19*9 = 171 回の反復です。後半については、1 ではなく 0 から開始する内側のループを使用して同様に行います。つまり、19*10 = 190 回の反復です。次に、合計first[i]*second[i]し1 <= i <= 27ます。

于 2012-10-25T00:54:35.033 に答える
1

すべての 3 桁の数字を生成します。桁の合計に基づいてセットに分割します。(実際には、セットのサイズをカウントするベクトルを保持するだけで済みます)。各セットについて、生成できる 6 桁の数字の数は、セットの 2 乗のサイズです。あなたの答えを得るために設定されたサイズの二乗を合計します。

int sumCounts[28]; // sums can go from 0 through 27
for (int i = 0; i < 1000; ++i) {
    sumCounts[sumOfDigits(i)]++;
}
int total = 0;
for (int i = 0; i < 28; ++i) {
    count = sumCounts[i];
    total += count * count;
}

先行ゼロのカウントを排除する編集バリエーション:

int sumCounts[28];
int sumCounts2[28];
for (int i = 0; i < 100; ++i) {
    int s = sumOfDigits(i);
    sumCounts[s]++;
    sumCounts2[s]++;
}
for (int i = 100; i < 1000; ++i) {
    sumCounts[sumOfDigits(i)]++;
}
int total = 0;
for (int i = 0; i < 28; ++i) {
    count = sumCounts[i];
    total += (count - sumCounts2[i]) * count;
}
于 2012-10-25T00:38:10.517 に答える
1

Python 実装

def equal_digit_sums():
dists = {}
for i in range(1000):
    digits = [int(d) for d in str(i)]
    dsum = sum(digits)
    if dsum not in dists:
        dists[dsum] = [0,0]
    dists[dsum][0 if len(digits) == 3 else 1] += 1
def prod(dsum):
    t = dists[dsum]
    return (t[0]+t[1])*t[0]
return sum(prod(dsum) for dsum in dists)

print(equal_digit_sums())

結果: 50412

于 2013-12-17T03:48:52.910 に答える
0

1 つのアイデア: 0 から 27 までの各数字について、その数字の合計を持つ 3 桁の数字の数を数えます。これは、DP スタイルのアプローチで効率的に実行できるはずです。

ここで、結果の 2 乗を合計するだけです。これは、各回答に対して、各辺に 1 つを使用して 6 桁の数を作成できるためです。

于 2012-10-25T00:37:28.783 に答える
0

先頭の 0 が許可されていないと仮定すると、3 桁の n に合計する方法がいくつあるかを計算する必要があります。for ループ内に for ループを含めることができることを計算します。そう：

firstHalf = 0
for i in xrange(max(1,n/3),min(9,n+1)): #first digit
  for j in xrange((n-i)/2,min(9,n-i+1)): #second digit
    firstHalf +=1  #Will only be one possible third digit
secondHalf = firstHalf + max(0,10-|n-9|)

数値を合計しようとしている場合、最後の数値は常に一意に決定されます。したがって、最初の数値が 0 の場合、2 番目の数値に可能な異なる値の数を計算しているだけです。n が 10 未満の場合、これは n+1 になります。n が大きい場合、18 までは 19-n になります。18 歳以上の場合、金額を計算する方法はありません。1 から 27 までのすべての n をループすると、合計が得られます。

于 2012-10-25T00:53:22.717 に答える