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

Question

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

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

写一个函数：

整数解（整数 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();
    }

score 7 · Accepted Answer

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

您的代码中的问题：

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

score 3 · Accepted Answer

此解决方案不会将数字转换为二进制字符串，因为这是不必要的。1它从第一个设置位 ( )左侧的第一位开始，从右到左查看每个位。

n & -n返回一个只有最右边的n设置的掩码。将其乘以 2 得到左边的下一位，这是开始计数的合适位置。

对于每个位检查（即循环的每次迭代），它要么递增或重置current计数器，并使用它来跟踪迄今为止发现的最大连续部分。

public int solution(int n) {
    int max = 0;
    for (int mask = (n & -n) * 2, current = 0; mask < n; mask <<= 1)
        max = Math.max(max, (n & mask) == 0 ? ++current : (current = 0));
    return max;
}

score 2 · Accepted Answer

以上所有代码中最简单的代码，Codility 100% 正确性和分数，已验证！

Javascript中的解决方案：

function solution(N) {
  let binaryValue = (N >>> 0).toString(2);

  let lengthArr = [];
  let length = 1;

  for(let i = 0; i < binaryValue.length; i++){
    if(binaryValue[i] == 0){
      // Check if 1 is ending then push the lenght to array and reset the length
      if(binaryValue[i + 1] == 1){
        lengthArr.push(length);
        length = 0;
      }

      length++;
    }
  }

  return lengthArr.length ? Math.max(...lengthArr) : 0;

}

score 1 · Accepted Answer

无需将二进制字符串的内容放入数组中（当然除非这是要求），只需遍历字符串本身并使用 String.substring() 方法检索每个二进制数字的字符串表示值，如：

String digit = binaryString.substring(i, i+1);

这一切都归结为计算任何一组 1之间的 0 的数量，并通过使用每次遇到 0 时递增的整数数据类型变量来跟踪这些 0。每次遇到 1 时，此相同的变量都会重置为 0，但在重置之前，您会将其与另一个预定义的整数变量进行比较，该变量将保持遇到的 0 的最长运行，例如：

if(binaryString.substring(i, i+1).equals("1")) {
    if (zeroHit > longest) { longest = zeroHit; }
    zeroHit = 0;
}
else { zeroHit++; }

整个方法可能看起来像这样：

private static int solution(int intValue) {
    String binaryString = Integer.toBinaryString(intValue);
    int zeroHit = 0;
    int longest = 0;
    for (int i = 0; i < binaryString.length(); i++) {
        if(binaryString.substring(i, i+1).equals("1")) {
            if (zeroHit > longest) { longest = zeroHit; }
            zeroHit = 0;
        }
        else { zeroHit++; }
    }
    return longest;
}

score 1 · Accepted Answer

这是我适度的解决方案。现在我看到它看起来像是对 DevilsHnd 答案的修改。我测试了它

public int countZeros(int n) {
        String binaryRep = Integer.toBinaryString(n);
        char[] nChars = binaryRep.toCharArray();
        int nElemLength = Math.min(binaryRep.lastIndexOf('1') + 1, nChars.length);
        if (nElemLength <= 2) {
            return 0;
        }
        String[] elementsParts = binaryRep.substring(0, nElemLength).split("1");
        int zeroLength = 0;
        for (String elementsPart : elementsParts) {
            if (elementsPart.length() > zeroLength) {
                zeroLength = elementsPart.length();
            }
        }
        return zeroLength;
    }

score 1 · Accepted Answer

这个算法怎么样。时间表现是坏的还是好的？

int count = 0, prevCount = 0;

while (a > 1) {

  if (a % 2 == 0) {
     count++;
     if (count > prevCount)
        prevCount++;
     } else {
            count = 0;
        }    
        a = a/2;
    }

    if(a % 2 == 0)
       prevCount++;

score 1 · Accepted Answer

目标 C 解决方案 O(2n)

Codility给出的结果

任务分数：100%
正确性：100%
性能：未评估

时间复杂度

最坏情况的时间复杂度是 O(2n)

算法说明

事实

每个有效间隙都以“1”开头，并以另一个“1”结束，它们之间至少有一个“零”。

1001 - 是一个有效的间隙
00100 - 不是有效间隙
10100 - 是一个有效的间隙
11111 - 不是有效间隙

第1步

使用复杂度为 O(n) 的辅助方法获取 n 的位

第2步

迭代我们在第一步中得到的每一位
开始寻找第一个“1”——因为我们的标志“hasStartPattern”在第一次迭代中为假，我们将寻找第一个出现的“1”，这意味着我们有一个有效的开始模式，我们改变了标志“hasStartPattern” ' 对于下一次迭代，我们应该验证当前位是否为 '0' 并使用计数器，在本例中为 'candidates'。
仅当传入位中还有另一个“1”时，我们确定我们有一个有效的二进制间隙，然后我们将我们以前的“候选”与我们当前的“gapCounter”进行比较，以保持最高的。
如果没有另一个 '1' 来缩小差距，我们永远不会改变 'gapCounter' 的值并返回 0。

Xcode 解决方案在这里

+(int)solutionTwo:(int)n {    
    // STEP 1
    // O(n)
    NSString *bits = [self getBitsForNumber:n];

    BOOL hasStartPattern = NO;
    int candidates = 0;
    int gapCounter = 0;

    // STEP 2
    // O(n)
    for (int i=0; i < bits.length; i++) {

        char currentBit = [bits characterAtIndex:i];

        if ( hasStartPattern  && currentBit == '0' ) {
            candidates++;
        }
        else if ( hasStartPattern  && currentBit == '1' ) {
            // At least one '1' exist as a close pattern
            if (candidates > gapCounter) {
                gapCounter = candidates;
            }
            candidates = 0;
        }
        else if (currentBit == '1') {
            hasStartPattern = YES; // At least one '1' exist as an open pattern
        }

    }

    return gapCounter;
}

/*
Time Complexity:
- The worst case time complexity for this auxiliary method is O(n)
*/
+(NSString*)getBitsForNumber:(int)n {
    NSMutableString *bits = [NSMutableString string];
    while(n) {
        [bits insertString:((n&1)? @"1" : @"0") atIndex:0];
        n /= 2;
    }
    return bits;
}

score 1 · Accepted Answer

这是等效的 C# 代码

 public int solution(int N) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    int m;
    for (m=1;m>0;m<<=1){
        if((m&N) !=0){
        break;
        }
    }
    int i = 0;
    int j = 0;
    for (; m>0;m<<=1){
        if((m&N) !=0){
            j=i<j ? j:i;
            i=-1;
        }
        i++;
    }
    return j;
    }
}

score 1 · Accepted Answer

Python 中的单行：任务分数 100%，正确性 100%

def solution(N):
    b=bin(N)[2:]
    return len(max(b.strip('0').split('1'))) 
# here strip will remove all trailing 0's and split will create a list with splitting 1's and combining 0's which are together.

score 0 · Accepted Answer

我认为您的代码有点混乱，请检查这个。

public int solution(int n) {
    if (n <= 0) return 0;
    char[] chars = Integer.toBinaryString(n).toCharArray();
    ArrayList<Integer> arrayList = new ArrayList<>();
    int maxCount = 0;
    for (int i = 0; i < chars.length; i++) {
        while (chars[i] == '0' && i + 1 < chars.length) {
            maxCount++;
            i++;
            if (i + 1 == chars.length && chars[i] == '0')
                maxCount = 0;
        }
        if (maxCount != 0)
            arrayList.add(maxCount);
        maxCount = 0;
    }

    return arrayList.isEmpty() ? 0 : Collections.max(arrayList);
}

score 0 · Accepted Answer

嗨，这是我完成这项任务的解决方案。我有任务分数：100% 正确性：100%

public int solution(int N) {
    String binary = Integer.toBinaryString(N);
    int[] table = new int[binary.length()];

    for (int i=0;i<binary.length();i++){
        int number = Integer.parseInt(binary.substring(i,i+1));
        table[i] = number;
    }

    int resu = 0;
    int res = 0;
    for (int i=0;i<table.length;i++){
        if (table[i] == 1){
            if (resu > res){
                res = resu;
            }
            resu = 0;
        }else {
            resu++;
        }
    }

    return res;
}

score 0 · Accepted Answer

为了所有人的利益，这是我对二进制差距的解决方案，它使我的任务分数和任务正确性都达到了 100%：

class Solution {
    public int solution(int N) {
        String nStr = Integer.toBinaryString(N);

        boolean isCounting = false;
        int j=0;
        int[] seqs = new int[32];
        for (int i=0; i<nStr.length(); i++)
        {
            if ( nStr.charAt(i) == '1')
            {
                if (!isCounting)
                {
                    isCounting = true;
                    seqs[j] = 0;
                }
                else // isCounting, turn it off
                {
                    isCounting = false;
                    j++;
                }

            }
            else // nStr.charAt(i) == '0'
            {
                if (!isCounting)
                    isCounting = true;
                seqs[j]++;
            }

        }
        if (isCounting == true)
            seqs[j] = 0;

        int maxGap = 0;
        for (int k=0; k<seqs.length; k++)
            if (seqs[k] > maxGap)
                maxGap = seqs[k];
        return maxGap;
   }
}

score 0 · Accepted Answer

目标 C 解决方案 O(n)

Codility给出的结果

任务分数：100%
正确性：100%
性能：未评估

时间复杂度

最坏情况的时间复杂度是 O(n)

算法说明

事实

每个有效间隙都以“1”开头，并以另一个“1”结束，它们之间至少有一个“零”。

1001 - 是一个有效的间隙
00100 - 不是有效间隙
10100 - 是一个有效的间隙
11111 - 不是有效间隙

第1步

从右到左一一获取位表示。
这意味着，对于 n=4，我将首先得到一个零，然后是另一个零，然后是一个，最后是一个零。[0,1,0,0]
4 -> 0100

第2步

开始寻找第一个“1”——因为我们的标志“hasStartPattern”在第一次迭代中为假，我们将寻找第一个出现的“1”，这意味着我们有一个有效的开始模式，我们改变了标志“hasStartPattern” ' 对于下一次迭代，我们应该验证当前位是否为 '0' 并使用计数器，在本例中为 'candidates'。
仅当传入位中还有另一个“1”时，我们确定我们有一个有效的二进制间隙，然后我们将我们以前的“候选”与我们当前的“gapCounter”进行比较，以保持最高的。
如果没有另一个 '1' 来缩小差距，我们永远不会改变 'gapCounter' 的值并返回 0

Xcode 解决方案在这里

-(int)solutionOne:(int)n {

    BOOL hasStartPattern = NO;
    int candidates = 0;
    int gapCounter = 0;

    while(n){
        // STEP 1
        NSString *bit = (n & 1) ? @"1": @"0";
        n /= 2;

        // STEP 2
        if ( hasStartPattern  && [bit isEqualToString:@"0"]) {
            candidates++;
        }
        else if ( hasStartPattern  && [bit isEqualToString:@"1"]) {
            // At least one '1' exist as a close pattern
            if (candidates > gapCounter) {
                gapCounter = candidates;
            }
            candidates = 0;
        }
        else if ([bit isEqualToString:@"1"]) {
            hasStartPattern = YES; // At least one '1' exist as an open pattern
        }
    }
    return gapCounter;
}

score 0 · Accepted Answer

我认为这是一个非常小的代码

    public int solution(int N)
    {
        string binary = Convert.ToString(N, 2);
        binary = binary.TrimEnd(new Char[] { '0' });
        var gaps = binary.Split('1');
        int max = 0;
        foreach (var item in gaps)
        {
            if (!string.IsNullOrEmpty(item))
                if(item.Length > max)
                   max = item.Length;
        }            
        return max ;
    }

score 0 · Accepted Answer

这里是我的

public int solution(int N) {

    String binary = Integer.toBinaryString(N);

    LinkedList<Integer> gaps = new LinkedList<>();
    int countGap = 0;
    int j = 0;
    for (int i = 1; i < binary.length() - 1; i++) {
        if (binary.charAt(i) == '0') {
            countGap++;
        } else {

            gaps.add(j, countGap);
            j++;
            countGap = 0;
        }
    }

    gaps.add(j, countGap);

    if (binary.charAt(binary.length() - 1) == '0') {
        gaps.set(gaps.size() - 1, 0);
    }

    Collections.sort(gaps);

    return gaps.getLast();
}

score 0 · Accepted Answer

这是我的解决方案。（斯卡拉）

它是 100/100。

 object Solution {
  def solution(n: Int): Int = {
   val regex = raw"(?=(10*1))".r
   val result = regex.findAllMatchIn(n.toBinaryString).map(_.group(1)) match {
    case re:Iterator[String] if !re.isEmpty => (re.toList.map(Integer.parseInt(_, 2)).sorted.last.toBinaryString.length - 2)
    case _ => 0
  }
  result
  }
}

score 0 · Accepted Answer

我使用 JavaScript 的解决方案，经过 100% 的测试。

function solution(N) {
    N = N.toString(2);
    let numberOfOnes = 0;
    let binaryGap = 0;
    let binaryZeros = 0;
    for(let i=0; i<N.length; i++) {
        if(N[i] > 0) {
            numberOfOnes++;
        }
    }
    if(numberOfOnes) {
        for(let j=0; j<N.length; j++) {
            if(N[j] > 0) {
                if(binaryZeros) {
                    if(binaryZeros > binaryGap) {
                        binaryGap = binaryZeros;
                    }
                }
                binaryZeros = 0;
            }
            if(N[j] < 1) {
                binaryZeros++;
            }
        }
    } else {
        binaryGap = 0;
    }
    return binaryGap;
}

score 0 · Accepted Answer

我用PHP调整了 @minary 解决方案，它工作正常。

  function maxZeros($N){
    $ptr = 0; //Used for bitwise operation.
     for($ptr = 1; $ptr > 0; $ptr <<= 1) //Find the lowest bit 1
      if(($N & $ptr) != 0)
        break;

    $cnt = 0; //Count the (possible) gap
    $ret = 0; //Keep the longest gap.
     for(; $ptr > 0; $ptr <<= 1) {
      if(($N & $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 because we set the cnt as -1 instead of 0.
     }
    return $ret;
   }

  //Run the function below, for example N = 32
   $N = 32; 
   echo (maxZeros($N));

score 0 · Accepted Answer

public static int solution(int N) {
    int longestBinaryGap = 0;
    String binary= Integer.toBinaryString(N);
    if(!binary.contains("01")){
        return 0;
    }

    binary = binary.replaceAll("0*$", "");
    String[] gaps = binary.split("1");


    for (String g:gaps) {
        if(g.length()>longestBinaryGap){
            longestBinaryGap = g.length();
        }
    }

    return longestBinaryGap;
}

score 0 · Accepted Answer

这是我用 Javascript 写的，有人可以批评一下吗，它在 Codility 上得分 100%。

const binaryGap = (intN)=>{
    const binary = Array.from(intN.toString(2)).map(item=>parseInt(item))
    
    const newArrayGroup = []

    const arrLength = binary.length

    let zeroGroup = []

    for (let index = 0; index < arrLength; index++) {

        const parsedInt = binary[index]

        if ( parsedInt == 0 ) {

            zeroGroup.push(parsedInt)   
        }else{
            if (zeroGroup.length>0) {
                newArrayGroup.push(zeroGroup.length)
            }
            zeroGroup = []
        }
    }

    return newArrayGroup.length == 0 ? 0 : Math.max(...newArrayGroup)
}

score 0 · Accepted Answer

这是我在 C# 中的答案：


class Solution {
    public int solution(int N) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
         string Nbin = Convert.ToString(N, 2);
            string[] arr = Nbin.Split('1');
            int maxZ = 0;
            if (arr.Length > 2 && arr[arr.Length - 1] == " ")
            {
                foreach (var item in arr)
                {
                    if (item.Length > maxZ)
                    {
                        maxZ = item.Length;
                    }
                }
            }
            else
            {
                for (int i = 0; i < arr.Length - 1; i++)
                {
                    if (arr[i].Length > maxZ)
                    {
                        maxZ = arr[i].Length;
                    }
                }
            }
            return maxZ;
    }
}

score 0 · Accepted Answer

这是我的简单解决方案

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        String b = Integer.toBinaryString(N);

        char[] binaryArr = b.toCharArray();
        int max = 0;
        int internalCount = 0;
        for(int index=1; index< binaryArr.length; index++){
            if(binaryArr[index] =='0')
                internalCount++;
            else{

                if (max<internalCount) max = internalCount;
                internalCount =0;

            }
        }


        return max;
    }
}

score 0 · Accepted Answer

这是我在 PHP 中的简短解决方案（任务分数：100%，正确性：100%）

function solution($N) {
    $gaps = array();
    $s = explode('1', trim(decbin($N),'0'));
    foreach($s as $g){
        $gaps[] = strlen($g);
    }
    return max($gaps);
}

score 0 · Accepted Answer

对于 Javascript 这是我的解决方案。

function solution(N){
      N = N.toString(2);
      var totalOnes = 0;
      var binaryGap = 0;
      var binaryZero = 0;
      const foundBinaryZero = []

      for(let i=0; i<N.length; i++) {
        if(N[i] > 0) {
            totalOnes++;   
            foundBinaryZero.push(binaryZero);
            binaryZero = 0;
           
        }else{
            binaryGap = 0;
            binaryZero = binaryZero + 1;
          
        }
    }

    foundBinaryZero.sort();


    return (foundBinaryZero[foundBinaryZero.length - 1]);

}

score 0 · Accepted Answer

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

大家好，我刚刚解决了这个问题，希望对大家有帮助。

    public int solution(int N) {
          
        String toBinary = Integer.toBinaryString(N);
        char[] ch = toBinary.toCharArray();
        int maxCount = 0;
        int count = 0;
        boolean flag = false;
          
        for(int i=0; i < ch.length; i++){
            if(ch[i] == '1'){
                if(count > maxCount){
                 maxCount = count;
                }
             count = 0;
            } else
              count ++;
        }
         return maxCount;
    }
}

score 0 · Accepted Answer

我添加了这个解决方案，Codility 得分为 100%。

public int solution(int N) {
    String s = Integer.toBinaryString(N);
    s = removeTrailingZeros(s);
    System.out.println(s);
    String arrayBinary[] = s.split("1");
    int x = 0;
    for (String abc : arrayBinary) {
        if (abc.length() > x)
            x = abc.length();
    }
    return x;
}

private String removeTrailingZeros(String s) {
    if (s.endsWith("0")) {
        s = s.substring(0, s.length() - 1);
        return removeTrailingZeros(s);
    }
    return s;
}

执行的测试集

score 0 · Accepted Answer

如果二进制数以0then结尾，number % 2 == 0则number % 2 == 1使用此规则我们可以很容易地解决它。

def solution(N: int):
  prev = 0
  current = 0
  
  # remove leading zeros
  while N % 2 == 0:
    N >>= 1

  # shift to right until its reaches 1
  while N != 1:
  
    if N % 2 == 0:
      current += 1
    else:
      prev = max(current, prev)
      current = 0

    N >>= 1
  return max(prev , current)

score -1 · Accepted Answer

这是我的解决方案。

它是 100/100。

我认为它可以抛光。

    class Solution {
      public int solution(int N) {

       String s = Integer.toBinaryString(N);
       int ctr = 0;

       for (int x = 0; x < s.length(); x++){

           if (s.substring(x,x+1).equals("1")){

               ctr++;
           }

       }


       int result[] = new int[ctr];

       boolean flag = false;
       int fCtr = 0;
       for(int y = 0; y < s.length(); y++){
           if(s.substring(y,y+1).equals("1")){
               flag = true;
               if(flag == true){
                    fCtr++;
               }

               }
           else if (s.substring(y,y+1).equals("0") && flag == true && fCtr < ctr){
               result[fCtr]++;
           }
         } 

        int ans = 0;
        for (int d = 0; d < result.length; d++){
            if (ans <= result[d]){
                ans = result[d];
            }
        }

       return ans;
    }
}

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

28 回答 28

Related

Reference