使用递归解决二进制间隙问题

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));
    }

}

- Zack

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处理数据

- Fuping

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;
}

n >>> Integer.numberOfTrailingZeros(n) 可以去掉 n 的尾部零。

- user4910279

---

它可以运行。你能告诉我一些好的资源，帮助我提高递归编写技巧吗？ - Zack

但是你的解决方案对于例如100这样的情况无效。它应该明确返回0。 - xuesheng

无法处理以零结尾的数字，例如：8。 - Leninkumar Koppoju

我会首先添加这样的代码：while (n % 2 == 0 && n > 0) n >>= 1; - jjnunog

测试输入为：100010000，但返回结果为6，这是错误的。 - Praveen Shendge

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);
    }

}

- Yoda

Answer 4

我的解决方案。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;
        }
    }

- Jaumzera

---

这部分代码 else { pos++; } 是必须的吗？因为二进制数总是以1开头，所以它似乎不可能有非0值，并且只有在出现1值时才从内部循环中跳出。或者它考虑到了手动键入字符串二进制而不是从解析中获取的情况。 - Michał Ziobro

嗯，@MichałZiobro...你是对的...我又犯了同样的错误。 - Jaumzera

Answer 5

我们可以使用1作为分隔符来拆分binaryString。

例如： 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;
    }

- hemantvsn

---

如果二进制是：1000100000？您的代码返回5，这是不正确的。它应该返回3。因为最后一组零没有以1结尾约束。 - Kishor Prakash

在 for 循环 中，检查 zeroArray 是否以 0 结尾，如果是，则不予考虑。 - Dixit Singla

Answer 6

这个答案在Codility上经过测试，性能和正确性都获得了100%的评分。

希望它能帮助到某些人。

    public static int solution(int N) {
    int binaryGap = 0;

    String string = Integer.toBinaryString(N).replaceAll("0+$", "");

    String[] words = string.split("1+");

    Arrays.sort(words);

    if(words.length != 0) {
        binaryGap = words[words.length -1].length(); 
    }

    return binaryGap;

}

- Mustafa Shahoud

---

欢迎来到Stack Overflow！请不要仅仅回答源代码，尽量提供一个关于你的解决方案如何工作的好描述。参见：https://stackoverflow.com/help/how-to-answer。谢谢！ - Matt Ke

Answer 7

Ruby解决方案（无递归 - Codility 100％正确性）：

`

def binary_gap(number)
      remainder = []
      while number > 0
        remainder << number % 2
        number = number / 2
      end
      binary_number = remainder.reverse.join('')
      biggest_gap = 0
      current_gap = 0
      status ='stop'
      binary_number.reverse.each_char do |char|
        if char =='1'
          status = 'start'
          current_gap = 0
        elsif char == '0' && status =='start'
          current_gap +=1
        end
        if current_gap > biggest_gap
          biggest_gap = current_gap
        end
      end

      return biggest_gap

    end

`

- Enow B. Mbi

Answer 8

最优解需要考虑边界和特殊情况，例如：给定N = 32时，函数应该返回0，因为N的二进制表示为“100000”，因此没有二进制间隙。但是我看到的大多数代码都会返回5。这是错误的。 以下是通过所有测试的最优解：

public int solution(int N) {
        int result = 0;
        while (N > 0) {
            if ((N & 1) == 1) {
                int temp = 0;
                while ((N >>= 1) > 0 && ((N & 1) != 1)) {
                    temp++;
                }
                result = Math.max(result, temp);
            } else {
                N >>= 1;
            }
        }
        return result;
    } 

- Maestra

Answer 9

我使用了非递归的方法得到了这个解决方案。

def solution(N):
    number = str(bin(N))[2:]

    current = 0
    max_ = 0
    started = False
    for e in number[::-1]:
        if e == '1':
            started = True
            if current > max_:
                max_ = current
            current = 0
        else:
            if started:
                current = current + 1
    return max_

- EduardoMPinto

Answer 10

Java解决方案（无递归 - 在Codility中100％正确）：

public static int solution(Integer number) {

    String binary = Integer.toBinaryString(number);

    String[] gaps = binary.split("1");

    String biggestGap ="";
    for (int i = 0; i < (binary.endsWith("1") ? gaps.length: gaps.length-1); i++) {

        if (gaps[i].contains("0") && gaps[i].length()>biggestGap.length())
        biggestGap = gaps[i];

    }

    return biggestGap.length();
}

- Cristian Guedes