计算二进制间隙时无限循环

Question

我目前正在解决二进制间隙问题（计算两个 1 之间的 0 的数量，并返回找到的 0 的最大间隙），我的解决方案首先从将整数 N 转换为字符串开始N 的二进制形式，工作正常。

从概念上讲，我正在做的（或者至少我认为我正在做的）是计算 0 直到我达到 1 字符，然后将其与变量 gap 下的当前 0 计数进行比较，然后我将我的零计数器清零 zero_count，我还添加了一个 if 语句来检查它到达二进制字符串末尾的情况，如果没有则返回 0，如果找到则返回 1。

出于某种原因，我得到了一个无限循环，我想我已经将它缩小到索引值不递增，但我不确定为什么。如果有人能解释一下，我将不胜感激！

这是在 Java 中完成的。

import java.util.*;

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        String binary = "";

        int power = 31;

        //double expo = Math.pow(2,power);
        while(power !=-1){
            if(N - Math.pow(2,power) > -1){
                binary += "1";
                N -= Math.pow(2,power);
            }
            else{binary += "0";}
            power--;
        }
        System.out.println(binary);
        
        //above works
        int  gap = 0;
        int zero_count = 0;
        int index = 0;
        for( int i = 0; i < binary.length(); i++){
            if(binary.charAt(i) == '1'){
                index= i+1;
                while(binary.charAt(index) =='0'){
                    index++;
                    zero_count++;
                    if(index == binary.length()-1){
                        return 0;
                    }
                }
            }
            if(zero_count > gap){
                gap = zero_count;
            zero_count = 0;
            }
            i = index;
        }
        return gap;
    }
}

Answer 1

循环太多..

将 main 添加到 drive/run 代码；您可以删除方法上的静态。

import java.util.*;

class Solution {
    public static void main(String[] args) {
            System.out.println("the max gap is: "+ Solution.solution(103241));
        }

    
    public static int solution(int N) {
        // write your code in Java SE 8
        String binary = "";

        int power = 31;

        //double expo = Math.pow(2,power);
        while(power !=-1){
            if(N - Math.pow(2,power) > -1){
                binary += "1";
                N -= Math.pow(2,power);
            }
            else{binary += "0";}
            power--;
        }
        System.out.println(binary);
        
        //above works
        int  max_gap = 0;
        int zero_count = 0;
        int index = 0;
        //boolean 
        for( int i = 0; i < binary.length(); i++){
            if(binary.charAt(i) == '0') {
                zero_count++;
            }
            else {
                if (zero_count > max_gap){
                    max_gap = zero_count;
                }
                zero_count = 0;
            }           
        }
        return max_gap;
    }
}

Answer 2

嵌套 while 循环中存在几个问题：

在比较 index 处的字符时应检查 binary 的长度以避免 StringOutOfBoundsException
到达字符串末尾时不应 return 0 - 结果可能不正确
index 应该在离开 while 循环时递减
前导 0s 应该完全跳过以避免无限循环此外，构建 binary string:
它不能正确转换负数也就是说，以下代码解决了上述问题：

public static int solution(int N) {
    // write your code in Java SE 8
    String binary = "";

    if (N == 0) {
        binary = "0"; // shortcut for 0
    } else {
        N &= Integer.MAX_VALUE; // remove sign bit for negative numbers
        while(N != 0) {
            binary = (N & 1) + binary; // get rid of leading zeros
            N >>= 1;
        }
    }
    
    //above works
    int gap = 0;
    int zero_count = 0;
    
    for (int i = 0, len = binary.length(); i < len; i++) {
        if (binary.charAt(i) == '1') {
            i++;
            while (i < len && binary.charAt(i) == '0') {
                zero_count++;
                if (i == len - 1) {
                    zero_count = 0;
                }
                i++;
            }
            i--;
        }
        if (zero_count > gap) {
            gap = zero_count;
            zero_count = 0;
        }
    }

    return gap;
}

但是，可以使用 Java 8 中可用的以下工具来实施更简单的解决方案：

Integer::toBinaryString 获取不带前导零的二进制字符串
String::replaceAll 删除尾随零
Pattern::splitAsStream 将剩余的字符串除以 1 并得到 Stream<String>
common Stream API mapToInt, max 获取仅由零组成的子串的最大长度:

static int maxZeroGap(int n) {
    return Pattern.compile("1")
        .splitAsStream(
            Integer.toBinaryString(n).replaceAll("0+$", "")
        )
        .mapToInt(String::length)
        .max()
        .orElse(0);
}

测试：

int[] nums = {
    0, 1, -1, -1023, Integer.MIN_VALUE, 0b10, 0b11, 0b101, 0b1001, 0b100101, 0b101000, 0b1000000100001
};
for (int i : nums) {
    System.out.printf("%d -> %s%n", i, Integer.toBinaryString(i));
    int z = maxZeroGap(i);
    System.out.println("max zeros = " + z + "; solution=" + solution(i));
    System.out.println("--------------------");
}

输出

0 -> 0
max zeros = 0; solution=0
--------------------
1 -> 1
max zeros = 0; solution=0
--------------------
-1 -> 11111111111111111111111111111111
max zeros = 0; solution=0
--------------------
-1023 -> 11111111111111111111110000000001
max zeros = 9; solution=9
--------------------
-2147483648 -> 10000000000000000000000000000000
max zeros = 0; solution=0
--------------------
2 -> 10
max zeros = 0; solution=0
--------------------
3 -> 11
max zeros = 0; solution=0
--------------------
5 -> 101
max zeros = 1; solution=1
--------------------
9 -> 1001
max zeros = 2; solution=2
--------------------
37 -> 100101
max zeros = 2; solution=2
--------------------
40 -> 101000
max zeros = 1; solution=1
--------------------
4129 -> 1000000100001
max zeros = 6; solution=6
--------------------

计算二进制间隙时无限循环

Infinite while loop while counting binary gap

java

infinite-loop