java - 使用递归解决二进制间隙

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 中，你可以使用流来解决这个问题:

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