我针对Binary Gap的代码解决方案是否正确?我应该在那方面做些什么改进? [英] Is my code solution for Binary Gap is correct or not? What should I improved in that?

问题描述

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

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

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

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

编写函数:

int solution(int N); 在给定正整数N的情况下，将返回其最长二进制间隙的长度.如果N不包含二进制间隔，则该函数应返回0.

int solution(int N); that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

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

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 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();
    }

推荐答案

我尚未测试您的代码，但是如果您的目标只是计算最长的二进制间隔"，则效率似乎很低.

I haven't tested your code yet, but it seems very inefficient if your goal is just counting the longest 'binary gap'.

您的代码中的问题:

• 将java.lang.String设置为char时.制作对象比制作原始类型要慢得多.
• 在可以简单计数时列出清单.只要您只需要列表的大小，就可以将其计入整数变量中.
• 愚蠢的算法.字符串的子字符串不能长于原始的子字符串.我说的是第二个for循环.例如，假设您要计算1001的二进制间隔.然后，您的算法计算001和01的二进制间隙.您根本不需要计算第二个.发生这种情况的原因是您有两个for循环.

• Makes java.lang.String when it can be just char. Making objects is much slower than making primitive types.
• Makes a list when it's able to simply count. As long as you're only going to need size of the list, you can just count it in a integer variable.
• Stupid algorithm. A substring of a string can't be longer than the original one. I'm talking about the second for loop. For example, let's say you're counting binary gap of 1001. Then your algorithm counts binary gap of 001 and then 01. You don't need to count the second one at all. And it's happening becuase you have two for loops.

最大的问题是，有可能根本不将int转换为java.lang.String即可解决此问题.如果您从教科书中遇到了这个问题，我相信这是正确"的答案:使用按位运算符.

The biggest problem is, that it's possible to solve this problem without converting int into java.lang.String at all. And in case you got this problem from a textbook, I believe this is the 'correct' answer: To use bitwise operators.

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

这篇关于我针对Binary Gap的代码解决方案是否正确?我应该在那方面做些什么改进?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！