8

最も近い回文数を見つけるという、よくあるインタビューの質問の 1 つに出くわしました。入力が127の場合、出力は131になり、125の場合、出力として121が得られるはずです。

ロジックを考え出すことはできますが、91、911 などの特定のケースではロジックが失敗します。これらの入力では 99 、919 が得られますが、正しい出力は 88 と 909 です。

アルゴリズムの手順は次のとおりです。

  • 数値を文字列に変換します。
  • 前半から後半を逆順にコピー
  • 数値に変換して腹筋を測定します。元の数との差 diff1
  • 文字列の半分に 1 を追加し、前半を後半に逆順にコピーする
  • 数値に変換して腹筋を測定します。元の数との差 diff2
  • diff1 が diff2 より小さい場合は最初の数値を返し、それ以外の場合は 2 番目の数値を返します
4

6 に答える 6

15

これは実際には興味深い問題です。明らかに、これを単なる力ずく以上のものにするためにやりたいことは、最上位桁を使用し、それらを最下位桁の位置に配置して回文を形成することです。（回文とオリジナルの違いを「距離」と呼ぶことにします）

そのことから、数値の最下位半分は無視できると言うつもりです。これは、実際には問題ではないためです (距離を決定する場合は重要ですが、それだけです)。

抽象的な数字を取ります: ABCDEF. A、B、C、D、E、F はすべてランダムな数字です。繰り返しますが、D、E、F は、回文を決定するために必要ではありません。数字の前半を後半にミラーリングすることです。明らかに、逆にしたくはありません。そうしないと、より有効な数字を変更して、元の数字から大きく離れてしまいます。

したがって、回文は になりABCCBAますが、既に述べたように、これが常に最短距離であるとは限りません。ただし、「解決策」はまだ形式でXYZZYXあるため、変更している数字の「重要性」を最小限に抑えることを考えると、C (または真ん中の数字) を変更する必要があることを意味します。

一歩下がって、その理由を見てみましょう。ABCCBA

  • 最初は変更したくなるかもしれませんがA、これは最も重要でない位置、つまり右端にあるためです。ただし、最も重要でないものを変更するには、最も重要なものを変更する必要があります。アウトAです。
  • についても同じことが言えるBのでC、最終的に選択した数字になります。

では、より近い可能性のある数値を取得するために変更Cする必要があることがわかったので、境界について考える必要があります。ABCDEFは私たちの元の数でありABCCBA、最も近い回文ではない場合、何が考えられるでしょうか? 上記の少し回り道に基づいて、 を変更することで見つけることができますC。したがって、ABCDEFより大きい場合ABCCBAと より小さい場合の 2 つのケースがありABCCBAます。

ABCDEFより大きい場合はABCCBA、 に 1 を加算しCます。T = C+1これで number が得られましたABTTBA。したがって、それを確認するためにテストし、そうであれば、それが最も近い回文ABCDEF - ABCCBA > ABCDEF - ABTTBA であることがわかります。ABTTBAC にこれ以上変更を加えると、私たちはますます遠ざかってしまいます。

ABCDEFまたは、が より小さい場合はABCCBAから 1 を引きますC。としましょうV = C-1。がありABVVBA、上記と同じようにテストします:ABCDEF - ABCCBA > ABCDEF - ABVVBAそして、同じ解決策が得られます。

トリックは、ABCDEFは常に と の間ABTTBAにありABVVBA、これらの数の間の他の回文は だけですABCCBA。したがって、ソリューションには3つのオプションしかありません。と比較ABCDEFするABCCBA場合は、2 のみを確認する必要があります。

これを任意のサイズの数値に適応させるのは難しくないと思います。桁数が奇数の場合は、単にABCBA、ABVBAなどABTBA...

あなたの例のように、911を取ります.

  1. 最後の 1 は無視して、前半のみを取得します (切り上げ)。だから91X。
  2. X を 9 に置き換えます。これは 919 です。これは中間点です。
  3. 元の 911 が 919 より小さいことがわかっているので、中間の数値から 1 を引いて、2 番目の (下限) 909 を取得します。
  4. 比較911 - 919して911 - 909
  5. 差が最も小さいものを返します。

したがって、これにより一定時間アルゴリズムが得られます:) コメントで指摘されているように、これは最悪の場合は一定時間ではありませんが（おっと）、ブルートフォースアプローチよりも確かに優れています。

これはあなたが持っているもののようですが、それ以外の場合は小さなプログラミングエラーのように見えるので、うまくいけば問題を明らかにするために詳しく説明したいと思いました.

于 2013-09-24T18:42:35.280 に答える