4

この問題は本当に私を混乱させます。2つの整数A、Bが与えられ、 [A、B]の範囲の数字の出現をカウントします。[0、A]から[0、B]の範囲の桁の出現回数を数えることができれば、残りは簡単です。では、 [0、x]の範囲の数字の出現をどのようにカウントできますか？これは宿題ではありません。これは実際にはSPOJの問題です。AとBは10^9まで大きくなる可能性があるため、単純なアプローチは機能しません。いくつかの例を次に示します。

入力：

1 10

出力：

1 2 1 1 1 1 1 1 1 1

入力：

44 497

出力：

85185185185190 96 96 96 95 93

4

3 に答える 3

9

私は最初にブルートフォースアプローチを試して、何かを機能させます。各数字を見て、その数字の文字列表現の各文字を繰り返し処理します。

ただし、もっと簡単な方法があります。

  • [0,9]の間隔で、3が1回出現します
  • [0,99]の間隔では、3が最初の桁に10回、2番目の桁に10回表示されます。
  • [0,999]の間隔では、3が1桁目に100回、2桁目に100回、3桁目に100回出現します。

これを一般化することができ、少しの努力で、特定の範囲に表示される特定の桁（0は特殊なケースの可能性があります）の数の式を考え出します。実際に各番号を確認する必要はありません。

于 2011-07-08T20:33:35.787 に答える
1

Wolfram Alphaはあなたの友達です（少なくとも21 * 10 ^ 4に近い数の場合）： 

Input:

44 497

Output:

85 185 185 185 190 96 96 96 95 93

私を試してみてください

結果：

{85、185、185、185、188、96、96、96、95、93}

于 2011-07-08T22:13:15.137 に答える
-1

この種の問題では、適切かつ高速に実行する方法を理解する前に、遅くて醜い実装から始めると便利なことがよくあります。問題の構造について何かを学ぶかもしれません、そしてあなたは速いものの正しさをテストするために遅い実装を使うことができます。

たとえば、Pythonでは、このような遅いバージョンを作成する場合があります（これは必ずしも最善の方法ではありませんが、最短の方法の1つです...）

>>> A, B = 1, 100
>>> from collections import Counter
>>> Counter(''.join(map(str, range(A, B + 1))))
Counter({'1': 21, '3': 20, '2': 20, '5': 20, '4': 20,
         '7': 20, '6': 20, '9': 20, '8': 20, '0': 11})
于 2011-07-08T21:09:29.810 に答える