シリコンバレー・エンジニアへの道

今回は「Longest Palindrome」という問題です。難易度は「Easy」です。Palindrome とは回文のことです。前後のどちらから読んでも同じように読める文です。 問題 与えられた文字列から作ることができる回文の最長の長さを求めよ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "abbccdde" から作ることができる最長の回文は "bcdadcb" や "cbdedbc" などである。これらの長さは 7 なので、7 を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: Hamming Weight 」の解答編です。模範解答に加え、Java が提供している便利なメソッドを使った解答を用意しました。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 模範解答である解答例１について解説する前に、解答例２の解法について簡単に述べます。この解法では、以前「 Power of Two の解答と解説 」と「 Hamming Distance の解答と解説 」で紹介した Integer.bitCount(int n) というメソッドを用いています。繰り返しになりますが、このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。つまり、このメソッドに整数を渡せばハミング重みが求まります。 解答例１は、整数 n の最下位の 1 ビットを取り出し、それが 1 のときに count をインクリメントしています。そして整数 n を 1 ビットずつ右にづらし、n が 0 になるまで繰り返します。ここまでは特に注意することはありません。 前回の問題出題時に「与えられる整数は正の整数であると問題文に指定されています。左端のビットが 1 である整数は負数をして扱っていないか注意してください。」と述べました。C 言語のように unsigned 修飾子を用いることによって正の整数を宣言することができますが、Java にはそのような修飾子はありません。そのため、特に特別な処理をしなければ Java では左端のビットが 1 の整数は符号あり整数、つまり負の整数になります。今回の問題では、これを符号なし整数、つまり常に正の整数として扱う必要があります。それでは Java でプログラムを記述する際に注意すべき点を 2 点挙げます。 1 つ目の注意点は、整数 n を右にシフトするとき、解答例１のように符号なしシフト演算子 ">>>" を用いることです。符号なしシフト演算子を用いると左端のビットが 1 の整数に対しても、シフト後に左端に 0 が挿入されます。一方、左端...

今回は「Hamming Weight」という問題です。日本語ではハミング重みです。以前出題し Hamming Distance  と類似の問題ですが、ビット演算のおさらいも兼ねて挑戦しましょう。難易度は「Easy」です。 問題 与えられた正の整数のハミング重みを返せ。ハミング重みとは整数を 2 進数で表したとき、符号が 1 となるビットの数である。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 5 が与えられた場合、5 は 2 進数だと 101 なので 2 を返す。 11 が与えられた場合、11 は 2 進数だと 1011 なので 3 を返す。 解答を見る前に 与えられる整数は正の整数であると問題文に指定されています。左端のビットが 1 である整数は負数をして扱っていないか注意してください。 それでは、解答と解説は 次の投稿 で。

「 問題演習: Add Binary Strings 」の解答編です。この問題のポイントとしては、文字列で表記された 2 進数を最下位のビットから計算する際に桁上げ処理を忘れずに行うことです。それでは解答例を見ていきましょう。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 7 行目で count という int 型の変数を用意しています。この変数は与えられた 2 つの 2 進数を走査するとき、各桁においてビットが 1 となる数を保持します。つまり、 1 つの 2 進数のi 番目の桁が 1 のとき、count に 1 を追加します。もう一方の 2 進数についても同様です。また、2 つの 2 進数の両方とも i - 1 番目の桁が 1 だった場合、i 番目のビットは 1 を加える必要があるため、count に 1 を追加します。 この処理を行うことで、下記のように最終的に求める 2 進数の各桁の値と桁上げ処理の有無を判断することができます。 count=0 のとき、i 番目のビットは 0 となり、桁上げは行わない。 count=1 のとき、i 番目のビットは 1 となり、桁上げは行わない。 count=2 のとき、i 番目のビットは 0 となり、桁上げを行う。 count=3 のとき、i 番目のビットは 1 となり、桁上げを行う。 つまり、count の値が 2 で割り切れるときは i 番目のビットは 0、そうでないときは 1 なので、15 行目のように "count % 2 + '0'" と記述することができます。また、count の値が 2 より大きい時に桁上げを行う必要があります。この処理は 16 行目のように "count /= 2" で行うことができます。 また、最後の桁を走査し終えてループを抜けた後も、最後の桁で桁上げが発生した場合には count の値に 1 が入っているはずです。そのための処理は 18 行目で行っています。 以上が今回の解説になります。

今回は「Add Binary Strings」という問題です。難易度は「Easy」です。 問題 2 つの 2 進数が文字列で与えられる。これらの和を 2 進数の文字列で返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "1" と "11" が与えられたとき "100" を返す。また、"101" と "111" が与えられたとき "1100" を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: Reverse Digits of Integer 」の解答編です。今回の解答では 2 つのポイントがありますので、それらを中心に解説します。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 問題出題時に入出力例として 12345 が与えられた場合は 54321 を返し、-12345 が与えられた場合は -54321 を返す必要があることを示しました。この例から分かることは、与えられた整数の正負は桁の反転によって変化することはないということです。整数の処理における正負の違いは混乱を生みやすくバグも入り込みやすいので、避けることが可能ならば積極的に避けましょう。解答例では入力時の整数の符号を初めに記憶しておき、桁の反転を行う際には常に正の整数であると仮定して処理を行います。最後に入力時と同じ正負の符号で出力しています。 また、この問題では反転後の整数が int 型に入らない場合は 0 を返す必要がありました。int 型の範囲に収まるかの判断は "result > Integer.MAX_VALUE / 10" で行うことができます。間違えて "result * 10 > Integer.MAX_VALUE" としてしまうと、左項が int 型の範囲を越えて負数になってしまい、思い通りの計算結果になりませんので注意しましょう。 以上が今回の解説になります。

今回は「Reverse Digits of Integer」という問題です。難易度は「Easy」です。 問題 与えられた整数の桁を反転せよ。ただし、負数も考慮し、反転後の整数が int 型に入らない場合は 0 を返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 例えば、12345 が与えられた場合は 54321 を返す。-12345 が与えられた場合は -54321 を返す。 それでは、解答と解説は 次の投稿 で。