java 使用递归解决二进制差距

Solving Binary Gap using Recursion

提问by Zack

I am trying to solve binary gap problem using recursion. It can be easily solved without recursion. But I want to solve this with recursion.The below program takes an integer as input and finds the binary gap.

我正在尝试使用递归解决二进制间隙问题。不用递归就可以轻松解决。但是我想用递归来解决这个问题。下面的程序将一个整数作为输入并找到二进制间隙。

Example:

例子：

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

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

It finds the maximum number of zeros that occur between two 1's in the binary representation.

它找出二进制表示中两个 1 之间出现的最大零数。

I want to solve this in O(logn). Right now, the below program simply counts the total number of zeros and gives output 3 instead of 2. How do I correct this to get the right output?

我想在 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));
    }

}

回答by Fuping

In Java 8, you can use stream to solve this:

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

There is a good article about Streams: Processing Data with Java SE 8 Streams

有一篇关于 Streams 的好文章：Processing Data with Java SE 8 Streams

回答by saka1029

Try this.

试试这个。

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

and

和

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

output

输出

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

This is simple tail recursion. So you can write without recursion like this.

这是简单的尾递归。所以你可以像这样没有递归地编写。

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)removes trailing zeros in n.

n >>> Integer.numberOfTrailingZeros(n)删除 中的尾随零n。

回答by Yoda

As many people were facing problem in handling the trailing zeros condition of the solution. Below is my solution with 100% test cases passing.

由于许多人在处理解决方案的尾随零条件时面临问题。以下是我 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);
    }

}

回答by Jaumzera

My solution. 100% without recursion.

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

回答by hemantvsn

We can split the binaryString with 1 as the delimiter

我们可以用 1 作为分隔符分割 binaryString

Eg: N=1041 BinaryString = 10000010001

例如：N=1041 BinaryString = 10000010001

When its split based on 1 as delimiter we get [, 00000, 000]

当它基于 1 作为分隔符进行拆分时，我们得到 [, 00000, 000]

and then the subproblem becomes to find the array with largest length

然后子问题变成寻找长度最大的数组

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

回答by Mustafa Shahoud

This answer is tested on coditilty and it has got 100% for performance and correctness.

这个答案在 coditilty 上进行了测试，它的性能和正确性 100%。

Hope it will help someone.

希望它会帮助某人。

    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;

}

回答by enowmbi

Ruby Solution (No recursion - 100% correctness in Codility):

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

`

`

回答by Rakesh Kumar

def solution(N):

定义解决方案（N）：

  max_gap = 0
  current_gap = 0

  # Skip the tailing zero(s)
  while N > 0 and N % 2 == 0:
      N //= 2

  while N > 0:
      remainder = N % 2
      if remainder == 0:
          # Inside a gap
          current_gap += 1
      else:
          # Gap ends
          if current_gap != 0:
              max_gap = max(current_gap, max_gap)
              current_gap = 0
      N //= 2

  return max_gap

if __name__ == '__main__':
    solution(N)

// Test Cases:
// N = 9 (1001), Expected = 2
// N = 529 = (1000010001), Expected = 4
// N = 51272 (1100100001001000), Expected = 4
// N = 15 (1111), Expected = 0
// N = 53 (110101), Expected = 1
// N = 2147483647 (1111111111111111111111111111111), Expected = 0
// N = 2147483648 (10000000000000000000000000000000), Expected = 0
// N = 0 (0), Expected = 0
// N = -1 (null), Expected = 0
// N = "A" (null), Expected = 0
// N = null (null), Expected = 0
// N = [blank] (null), Expected = 0

回答by EduardoMPinto

I got this solution without using recursion.

我在不使用递归的情况下得到了这个解决方案。

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_

回答by Maestra

The optimal solutionthat takes in account the boundaries and exceptional scenarios like: Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps. But most code I have seen above will returns 5. Which is wrong. Here is an optimal solution that passes all tests:

考虑边界和例外情况的最佳解决方案，例如：给定 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;
    }