0

Google からのインタビューの質問を表示するサイトで、この質問を見たことがあります。

この問題の解き方がわかりません。

他のいくつかの変数を保持できる場合は、2 つのインデックスを保持することをお勧めします。1 つは先頭を指し、もう 1 つは最後を指します。そして、ビット変数を使用して、それらの 2 つを比較します (ビット操作による)。

しかし、これ以上変数を使用することが許可されていない場合、それを解決する方法がわかりません。

4

2 に答える 2

1

ビット単位の回文について話していると仮定しています (つまり、3 = 11 はそうですが、2 = 10 はそうではありません)。

2つの可能性があることがわかりました：

(それぞれに Java コードをいくつか書きました。一部の括弧は読みやすくするためにのみ含まれています)

  • インデックスは変数としてカウントされません。

    私が最初に言うことは、おそらく「しかし、インデックスは変数です...」です。

    番号をループして、不一致が発生したら戻ることができます。

    digits以下は変数ですが、読みやすくするために、簡単に if ステートメントに代入できます。

    の式はdigits、いくつか遊んだ後に生まれました (もっと簡単な方法があるかもしれません)。

    boolean isPalidrome(int number)
{
   int digits = (int)Math.ceil(Math.ceil(Math.log10(1+number)/Math.log10(2)))-1;
   for (int i = 0; number/2 >> i != 0; i++)
   {
      if (((number >> i) & 1) != (((number >> digits - i) & 1)))
         return false;
   }
   return true;
}

  • インデックスは変数としてカウントされます。

    intこれは、固定サイズの数値 ( 32 ビットのなど) が与えられていると仮定して、基本的に上記のループをアンロールすることで実行できます。

    byte本質的に多くの行を複製するポイントが実際にはわからなかったので、タイプをに変更しました。byteは 8 ビットしかないため、ブレーク条件付きの 4 つのチェックのみが必要です。

    これdigitsも変数ですが、そうである必要はありません。

    boolean isPalidrome(byte number)
{
   int digits = (int)Math.ceil(Math.ceil(Math.log10(1+number)/Math.log10(2)))-1;
   if ((number & 1) != (((number >> digits) & 1)))
      return false;
   if ((number/2 >> 1) == 0)
      return true;
   if (((number >> 1) & 1) != (((number >> (digits - 1)) & 1)))
      return false;
   if ((number/2 >> 2) == 0)
      return true;
   if (((number >> 2) & 1) != (((number >> (digits - 2)) & 1)))
      return false;
   if ((number/2 >> 3) == 0)
      return true;
   if (((number >> 3) & 1) != (((number >> (digits - 3)) & 1)))
      return false;
   return true;
}

    必要に応じて、上記を 1 つのステートメントにまとめることもできます。

    実際の数値を変更できる場合は、上記のように最初と最後のビットをチェックすることもできますが、最初と最後のビットを取り除くように数値を変更して、最初と最後のビットだけをチェックできるようにします。数がゼロになるまで、最後のビットを繰り返します。

ライブデモ。

上記のいずれもビット変数を使用していないことに注意してください。おそらく、ビット変数は、数値が回文であるかどうかを追跡するためのフラグであることを単に意味しています。

于 2013-11-02T20:52:50.423 に答える