我的二进制间隙代码解决方案是否正确？我应该在这方面改进什么？

Question

正整数 N 内的二进制间隙是在 N 的二进制表示中两端被 1 包围的连续零的任何最大序列。

例如，数字 9 的二进制表示为 1001，并且包含长度为 2 的二进制间隙。数字 529 的二进制表示为 1000010001，并且包含两个二进制间隙：长度为 4 的一个和长度为 3 的一个。数字 20 的二进制表示为 10100，并且包含一个长度为 1 的二进制间隙。数字 15 具有二进制表示形式 1111，并且没有二进制间隙。

写一个函数：

int 解决方案（int N）；给定一个正整数 N，返回其最长二进制间隙的长度。如果 N 不包含二进制间隙，则该函数应返回 0。

例如，给定 N = 1041，该函数应返回 5，因为 N 的二进制表示为 10000010001，因此其最长的二进制间隙长度为 5。

public int solution(int n) {
        // write your code in Java SE 8
        String binaryRep = Integer.toBinaryString(n);
        System.out.println("Binary Representation of " + n + " = " + binaryRep);
        List<String> strList = new ArrayList<String>();
        int count = 0;
        for (int i = 0; i < binaryRep.length(); i++) { // Loop through the each number 
            String str = binaryRep.charAt(i) + ""; // getting one by one number
            if(str.equals("0")){
                for(int j = i;j<binaryRep.length();j++){ //Get each next element
                    String str1 = binaryRep.charAt(j) + "";
                    if(!str.equals("1") &&  str.equals(str1)){
                        if(!strList.isEmpty() && count >= strList.size()){
                            strList.add(str1);
                        }else if(strList.isEmpty()){
                            strList.add(str1);
                        }
                        count ++; 
                    }else{
                        count = 0;
                        break;
                    }
                }
           }   
        }
        return strList.size();
    }

Answer 1

我还没有测试过你的代码，但如果你的目标只是计算最长的“二进制差距”，这似乎效率很低。

您的代码中的问题：

• 使java.lang.String当它可以只是char。制作对象比制作原始类型慢得多。
• 当它能够简单地计数时制作一个列表。只要您只需要列表的大小，您就可以将它计入一个整数变量。
• 愚蠢的算法。字符串的子字符串不能长于原始字符串。我说的是第二个for循环。例如，假设您正在计算 的二进制间隙1001。然后你的算法计算二进制差距001然后01。你根本不需要计算第二个。这是因为你有两个 for 循环。

最大的问题是，可以在不转换int为的情况下解决这个问题java.lang.String。如果你从教科书中得到这个问题，我相信这是“正确”的答案：使用按位运算符。

public static int solution(int num) {
    int ptr; //Used for bitwise operation.
    for(ptr=1; ptr>0; ptr<<=1) //Find the lowest bit 1
        if((num&ptr) != 0)
            break;
    int cnt=0; //Count the (possible) gap
    int ret=0; //Keep the longest gap.
    for(; ptr>0; ptr<<=1) {
        if((num&ptr) != 0) { //If it's bit 1
            ret = cnt < ret ? ret : cnt; //Get the bigger one between cnt and ret
            cnt=-1; //Exclude this bit
        }
        cnt++; //Increment the count. If this bit is 1, then cnt would become 0 beause we set the cnt as -1 instead of 0.
    }
    return ret;
}