Painless
BinaryGap
整数のバイナリ表現でゼロの最長シーケンスを見つけよう。
タスクの説明
正の整数N内のバイナリギャップは、Nのバイナリ表現の両端が1で囲まれた連続するゼロの最大シーケンスです。
たとえば、番号9にはバイナリ表現1001があり、長さ2のバイナリギャップが含まれます。番号529にはバイナリ表現1000010001があり、長さ4と長さ3の2つのバイナリギャップが含まれます。番号20にはバイナリ表現10100があり、 長さ1の1つのバイナリギャップ。数値15にはバイナリ表現1111があり、バイナリギャップはありません。 数値32には2進表現100000があり、2進ギャップはありません。
Write a function:
class Solution { public int solution(int N); }
これは、正の整数Nが与えられると、最長の2進ギャップの長さを返します。 Nにバイナリギャップが含まれていない場合、関数は0を返す必要があります。
For example:
- N = 1041の場合、Nはバイナリ表現10000010001を持ち、その最長のバイナリギャップの長さは5であるため、関数は5を返す必要があります。
- N = 32の場合、Nにはバイナリ表現「100000」があり、バイナリギャップがないため、関数は0を返す必要があります。
次の仮定のための効率的なアルゴリズムを書く:
- Nは[1..2,147,483,647]範囲内の整数です。
解く【案１：Integer.toBinaryString】
Program
BinaryGap.java
public int solution(int N) {
int goal = 0;
String binaryN = Integer.toBinaryString(N);
char[] charsBinaryN = binaryN.toCharArray();
int counter = 0;
boolean counterSwitch = false;
for (int i = 0; i < charsBinaryN.length; i++) {
if (charsBinaryN[i] == '0') {
counterSwitch = true;
counter++;
} else if (charsBinaryN[i] == '1') {
if (counterSwitch) {
counterSwitch = false;
if (counter > goal) {
goal = counter;
}
counter = 0;
} else {
continue;
}
}
}
return goal;
}
junit
Report
解く【案２：シフト演算】
Program
BinaryGapShifter.java
public int solution(int N) {
int goal = 0;
int counter = 0;
boolean counterSwitch = false;
while (N > 0) {
if ((N & 1) == 1) {
if (counterSwitch) {
if (counter > goal) goal = counter;
counter = 0;
} else {
counterSwitch = true;
}
} else {
if (counterSwitch) counter++;
}
N = N >> 1;
}
return goal;
}