Problema: Obtenga el máximo espacio binario.
Por ejemplo, la forma binaria de 9 es 1001, el espacio es 2.
Solución Java 1
Un entero x & 1 obtendrá el último dígito del entero.
public static int getGap(int N) { int max = 0; int count = -1; int r = 0; while (N > 0) { // get right most bit & shift right r = N & 1; N = N >> 1; if (0 == r && count >= 0) { count++; } if (1 == r) { max = count > max ? count : max; count = 0; } } return max; } |
El tiempo es O (n).
Solución Java 2
public static int getGap(int N) { int pre = -1; int len = 0; while (N > 0) { int k = N & -N; int curr = (int) Math.log(k); N = N & (N - 1); if (pre != -1 && Math.abs(curr - pre) > len) { len = Math.abs(curr - pre) + 1; } pre = curr; } return len; } |
El tiempo es O (log (n)).