使用递归解决二进制间隙

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

在Java 8中,您可以使用stream来解决此问题:

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的好文章:使用Java SE 8 Streams处理数据

Answer 2

试试这个.

static int solution(int n) {
    return solution(n >>> Integer.numberOfTrailingZeros(n), 0, 0);
}

static int solution(int n, int max, int current) {
    if (n == 0)
        return max;
    else if ((n & 1) == 0)
        return solution(n >>> 1, max, current + 1);
    else
        return solution(n >>> 1, 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 max = 0;
    for (int i = n >>>= Integer.numberOfTrailingZeros(n), current = 0; i != 0; i >>>= 1) {
        if ((i & 1) == 0)
            ++current;
        else {
            max = Math.max(max, current);
            current = 0;
        }
    }
    return max;
}

Answer 3

由于许多人在处理解决方案的尾随零情况时遇到问题.以下是我的解决方案,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);
    }

}