反復番号を解決するアルゴリズム

Question

4,7桁の同じ数字（例：4747,4477など）からなる「ラッキーナンバー」を見つける必要があります。入力nが与えられた場合、nより大きいが、nに最も近い最小の「ラッキーナンバー」を見つける必要があります（たとえば、入力が6060の場合、回答は7447になります）。この問題を解決する最良のアルゴリズムは何ですか？入力が< = 10^100000になると仮定すると、私はそれを文字に分離して論理的に解決することを考えましたが、答えを見つけるのは容易ではない場合があります。誰も私にこの問題にアプローチする方法を教えてもらえますか？

Answer 1

以下のアルゴリズムは、ワーストケースの線形時間が最適である。

これは少し複雑ですが、それは、一方向に多くスキャンし、次にもう一方にスキャンし、次に最初にスキャンします。最適でも簡単なアルゴリズムがあるかもしれません。 （そして、現実的な実装では、平均的なケースを改善するために、マイナーな最適化を追加することになり、および/または一定の係数により、最悪の場合のパフォーマンスを向上させること。）

• ステップ＃1：結果が必要となるケースを扱います入力よりも多くの数字。
  • a1。n（入力の長さ）が奇数の場合、希望の結果は長さがn +1の '444＆hellip; 44777＆hellip; 77'になります。出力バッファにその結果を設定してから、戻ります。
  • 1b。入力が長さnの '777＆hellip; 77444＆hellip; 44'より大きい場合、希望の結果は長さがn +2の '444＆hellip; 44777＆hellip; 77'になります。出力バッファにその結果を設定してから、戻ります。
• ステップ＃2：入力を出力バッファにコピーします。
• ステップ＃3：出力バッファを、それより大きいか等しい4と7だけの最小整数になるように切り替えます（出力バッファを直接出力バッファで操作します）。その現在の値に戻します。 （例えば、「4723」の場合は「4744」が必要です。）これを行うには、左から右（最上位桁から最下位桁）までスキャンし、4または7.（そのような数字が見つからない場合、＃4に進みます。）3つのケースがあり、この桁の値に応じて：
  • ケース0 – 3：この数字が4未満である場合に、
  • ケース5 – 6：この桁が5または6の場合は、7に変更し、右側に変更それを4にする。
  • ケース8 – 9：この桁が8または9の場合は、最初の4個を見つけて左にもう一度スキャンします（そうでなければ、ステップ＃1で終了します）。を7に変更し、各桁を以前の4から4の右に変更します。
• ステップ＃4：以上の電流値に等しい4Sと7Sの等しいカウントからなる少なくとも整数で、出力バッファを突然変異させます。 （例えば、それは、その後、私たちは "4747" をしたい "4744" だ場合。）
  • 4A：は、出力バッファに4Sと7Sを数えます。
  • 4b： 4sよりも7sが多い場合は、それらのバランスを取るために4sに変更する必要のある7sの数を計算します。 kとしてください。 k +1 7sが表示されるまで右から左へ進み、4になるまで左に進みます（そうでなければ、ステップ1で終了します）。 〜に7; 4桁目から4桁目の各桁を右に変更します。その後、出力バッファーの4と7を再カウントします。 （注：このサブステップの後には、7秒よりも4秒以上ある場合があります。たとえば、「4777」があった場合は「7444」となります）。
  • 4c： 7sよりも4sが多い場合は、それらのバランスをとるために7sの数を4sに変更する必要があります。 kとしてください。右から左へ進みます。あなたが4秒に来るように、あなたが変更されるまで、7秒に変更してくださいk 4秒から7秒。