1
google codeJam資格取得の問題の1つは、2つの指定された整数の間に「リサイクルされたペア」がいくつあるかを調べることでした。ネストされたループよりも速いアルゴリズムですか？
これは私の解決策でしたが、大きなデータ入力セットでは十分に速くはありませんでした。 @ a = 10、@ b = 200000のようなものがあれば、それは遅くなり始める。
私の解決策はO（2^n）（私は大きなO分析をしっかりと把握していません）が恐ろしいと思います。私は高速なアルゴリズムでこのような2つのループを反復する標準的な方法があるのだろうかと思いましたか？
def getPairs
(@[email protected]).each do |n|
([email protected]).each do |m|
if (containsSame(n,m)) && (isMatch(@a, n, m, @b))
@recycledPairs += 1
end
end
end
end
編集： Google CodeJam siteから：
あなたはn個の背面からいくつかの数字を移動してメートルを得ることができるかどうかは、明確な正の整数（n、m）とのペアが再利用されるとしましょう順序を変更することなく前面に表示されます。たとえば、（12345、34512）はリサイクルされたペアです.3445を3445を12345の最後から前面に移動することで取得できます。リサイクルされたペアになるには、nとmの桁数が同じでなければならないことに注意してください。 nもmも先行ゼロを持つことはできません。
「リサイクルされたペア」とは何ですか？ – Ryan
ループとネストされたループは、アルゴリズムではなく実装成果物です。 – JRL
google codeJamサイトから：nの後ろからいくつかの桁を順序を変えずに正面に移動してmを得ることができる場合は、別々の正の整数（n、m）のペアをリサイクルするとしましょう。たとえば、（12345、34512）はリサイクルされたペアです.3445を3445を12345の最後から前面に移動することで取得できます。リサイクルされたペアになるには、nとmの桁数が同じでなければならないことに注意してください。 nもmも先行ゼロを持つことはできません。 – AFraser