Решение двоичного разрыва с использованием рекурсии

Question

Я пытаюсь решить проблему с двоичным разрывом с помощью рекурсии. Его можно легко решить без рекурсии. Но я хочу решить эту проблему с помощью рекурсии. Нижеследующая программа принимает целое число как входное и находит двоичный разрыв.

Пример:

input= 9, Binary form = 1001, Answer = 2 

input=37, Binary form = 100101, Answer = 2 

Он находит максимальное число нулей, которые происходят между двумя 1-й в двоичном представлении.

Я хочу решить это в O (logn). Прямо сейчас, приведенная ниже программа просто подсчитывает общее количество нулей и дает результат 3 вместо 2. Как мне исправить это, чтобы получить правильный результат?

class BinaryGap { 

    public int solution(int N){ 

    return solution(N, false, 0); 
    } 
    public int solution(int N, boolean prevFlag, int memo) { 

     if(N<2) 
      return 0; 

     int remainder = N%2 ; 


     if(prevFlag){ 
      if(remainder == 0){ 
       memo = 1 + solution(N/2, prevFlag, memo); 
      } else { 
       int newGap = solution(N/2, prevFlag, memo); 

       if(newGap > memo) 
        memo = newGap; 
      } 
     } else { 

      prevFlag = (remainder == 1); 
      return solution(N/2, prevFlag, 0); 
     } 

     return memo; 

    } 

    public static void main(String args[]){ 
     BinaryGap obj = new BinaryGap(); 

     System.out.println(obj.solution(37)); 
    } 

} 

Answer 1

Попробуйте это.

static int solution(int n) { 
    return solution(n, 0, 0); 
} 

static int solution(int n, int max, int current) { 
    if (n == 0) 
     return max; 
    else if (n % 2 == 0) 
     return solution(n/2, max, current + 1); 
    else 
     return solution(n/2, Math.max(max, current), 0); 
} 

и

int[] tests = { 9, 37, 0b1000001010001 }; 
for (int i : tests) 
    System.out.printf("input = %d, Binary form = %s, Answer = %d%n", 
     i , Integer.toBinaryString(i), solution(i)); 

выход

input = 9, Binary form = 1001, Answer = 2 
input = 37, Binary form = 100101, Answer = 2 
input = 4177, Binary form = 1000001010001, Answer = 5 

Это просто хвостовая рекурсия. Таким образом, вы можете писать без рекурсии.

static int solutionLoop(int n) { 
    int current = 0; 
    int max = 0; 
    while (n > 0) { 
     if (n % 2 == 0) 
      ++current; 
     else { 
      max = Math.max(max, current); 
      current = 0; 
     } 
     n /= 2; 
    } 
    return max; 
} 

Answer 2

В Java 8, вы можете использовать поток для решения этой проблемы:

static int calculateBinaryGap(int N) { 
    return Stream 
     .of(
      // integer to binary string 
      Integer.toBinaryString(N) 
       // trim 0(s) at the end 
       .replaceAll("0+$", "") 
       // split string with 1(s) 
       .split("1+")) 
     // lambda expressions: use filter to keep not null elements 
     .filter(a -> a != null) 
     // method references: convert string to integer by using the 
     // length of string 
     .map(String::length) 
     // method references: find the largest number in the stream by 
     // using integer comparator 
     .max(Integer::compare) 
     // return 0 if nothing matches after the process 
     .orElse(0); 
    } 

Существует хорошая статья о Streams: Processing Data with Java SE 8 Streams

Answer 3

Мы можем разделить binaryString с 1 в качестве разделителя

Например: N = 1041 BinaryString = 10000010001

Когда его разделение на основе 1 в качестве разделителей мы получаем [, 00000, 000]

, а затем подзадача становится найти массив с наибольшей длиной

private static int solution(int N) { 
     int gap = 0; 
     String binaryStr = Integer.toBinaryString(N); 

     String[] zeroArrays = binaryStr.split("1"); 
     System.out.println(Arrays.toString(zeroArrays)); 
     for(String zeroArray : zeroArrays) { 
      gap = zeroArray.length() > gap ? zeroArray.length() : gap; 
     } 
     return gap; 
    } 

Answer 4

Я думаю @ saka1029 почти нет, так же, как @xuesheng сказал, что решение не будет работать, если вход, например, являются 2 = 010, 4 = 100, 6 = 110.

Я хотел бы предложить сделать это ниже вместо

static int solution(int n) { 
    return solution(n, 0, 0, 0); 
} 

static int solution(int n, int max, int current, int index) { 
    if (n == 0) 
     return max; 
    else if (n % 2 == 0 && index == 0) 
     return 0; 
    else if (n % 2 == 0 && index > 0) 
     return solution(n/2, max, current + 1, index + 1); 
    else 
     return solution(n/2, Math.max(max, current), 0, index + 1); 
} 

Answer 5

Решения по hemantvsn велик за исключением того, завершающие нули, которые должны быть удалены

private static int solution(int N) { 
      int gap = 0; 
      String binaryStr = Integer.toBinaryString(N); 

      String[] zeroArrays = binaryStr.split("1"); 

      String[] zeroTruncated = new String[0]; 

      System.out.println(Arrays.toString(zeroArrays)); 
      if (Integer.lowestOneBit(N) != 1) { 
       zeroTruncated = Arrays.copyOf(zeroArrays, zeroArrays.length-1); 

      } 
      for(String zeroArray : zeroTruncated) { 
       gap = zeroArray.length() > gap ? zeroArray.length() : gap; 
      } 
      return gap; 
     } 

Answer 6

Как и многие люди сталкиваются с проблемой при обработке условия хвостовых нулей решения. Ниже приведено мое решение с передачей 100% тестовых случаев.

class Solution { 
    public int solution(int N) { 
     // write your code in Java SE 8 
     return binaryGap(N,0,0,0); 
    } 
    public int binaryGap(int n, int counter, int max, int index){ 
     if(n==0) 
      return max; 

     if(n%2==0 && index==0) 
      index=0; 

     else if(n%2==0) 
      counter ++; 
     else { 
      max = Math.max(counter, max); 
      index++; 
      counter =0; 
     } 
     n = n/2; 

     return binaryGap(n, counter, max, index); 
    } 

} 

Answer 7

Objective C Решение

int solution(int N) { 
    if (N==0) 
    { 
     return 0; 
    } 
    int maximumGap = -1; 
    int currentGap = 0; 
    while(N>0) 
    { 
     if (N%2 == 1) 
     { 
      if (currentGap>0) 
      { 
       maximumGap = maximumGap>currentGap?maximumGap:currentGap; 
      }else 
      { 
       maximumGap = 0; 
      } 
      currentGap = 0; 
     } 
     else if(maximumGap>-1) 
     { 
      currentGap++; 
     } 
     N=N/2; 
    } 
    return maximumGap; 
} 

Answer 8

Мое решение. 100% без рекурсии.

class Solution { 
     public int solution(int N) { 
      String binary = Integer.toString(N, 2); 
      int largestGap = 0; 
      for (int i = 1, gap = 0; i < binary.length(); i++) { 
       while (i < binary.length() && binary.charAt(i) == '0') { 
        i++; 
        gap++; 
       } 

       if (gap > largestGap && i < binary.length()) { 
        largestGap = gap; 
       } 

       gap = 0; 
      } 
      return largestGap; 
     } 
    } 

Answer 9

попробуйте это. Я использую tyring без использования рекурсивного.

private static int binaryGap(int N){ 
    int gap1 = 0, gap2 = 0, gapCounter = 0; 

    for(int i = N; i>=0; i--) 
    { 
     if(N < 1) break; 

     //binary 0 
     if(N%2 == 0) { 
      gap1++; 
     } 
     //binary 1 
     else 
     { 
      gap2 = gap2 > gap1 ? gap2 : gap1; 
      gap1 = 0; 
      gapCounter++; 
     } 
     if(gapCounter==1) gap2=0; 
     N = N/2; 
    } 
    return gap2; 
} 

Answer 10

// you can write to stdout for debugging purposes, e.g. 
// printf("this is a debug message\n"); 

int solution(int N) { 
    int b; 
    int zeroCounter = 0; 
    int prev = 0; 
    int c = -1; 
    while (N) { 
     b = N % 2; 
     N = N/2; 
     if ((b==1)||(c==0)) { 
      c=0; 

      //printf("%d", b); 
      if (b == 1) { 

       //printf("%d", b); 
       //checkTrailZero=prev; 
       if (prev < zeroCounter) { 
        prev = zeroCounter; 
       } 
       zeroCounter = 0; 
      } else { 

       zeroCounter++; 
      // printf("--%d--", zeroCounter); 
      } 
     } 
    } 
    //printf("longest%d", prev); 
    return prev;} 

Answer 11

Здесь работает код все тестовые примеры прошли,

package org.nishad; 

import java.util.Arrays; 

public class BinaryGap { 
    public static void main(String[] args) { 
     int N = 1; 
     int result; 
     //converting integer to binary string 
     String NString = Integer.toBinaryString(N); 
     //Removing the Trailing Zeros 
     NString = NString.replaceFirst("0*$",""); 
     //Split the binary string by one or more one(regex) for arrays of zeros 
     String[] NStrings = NString.split("1+"); 
     //Storing the array length 
     int length = NStrings.length; 

     if(length==0) // if length is zero no gap found 
      result = length; 
     else   
      { 
      //Sorting the array to find the biggest zero gap 
      Arrays.sort(NStrings, (a, b)->Integer.compare(a.length(), b.length())); 
      result = NStrings[length-1].length(); 
      } 


     System.out.println(NString); 

     System.out.println(result); 
    } 
}