使用遞歸求解二進制間隙

我想用遞歸來解決二進制間隙問題。無需遞歸即可輕鬆解決。但我想用遞歸來解決這個問題。下面的程序將一個整數作爲輸入並找出二進制間隔。使用遞歸求解二進制間隙

實施例：

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

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

它發現在二進制表示2點1的之間發生的零的最大數目。

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

}

來源

2016-02-21 Zack

試試這個。

static int solution(int n) { 
    return solution(n, 0, 0); 
} 

static int solution(int n, int max, int current) { 
    if (n == 0) 
     return max; 
    else if (n % 2 == 0) 
     return solution(n/2, max, current + 1); 
    else 
     return solution(n/2, Math.max(max, current), 0); 
}

和

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

輸出

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

這是簡單尾遞歸。所以你可以寫這樣沒有遞歸。

static int solutionLoop(int n) { 
    int current = 0; 
    int max = 0; 
    while (n > 0) { 
     if (n % 2 == 0) 
      ++current; 
     else { 
      max = Math.max(max, current); 
      current = 0; 
     } 
     n /= 2; 
    } 
    return max; 
}

來源

2016-02-21 03:37:33 saka1029

它的工作原理。你能告訴我一些我可以用來提高遞歸寫作技巧的好資源嗎？ – Zack

但是，例如，您的解決方案不適用於100。它肯定應該返回0。 – xuesheng

它不適用於用零跟隨的數字。例如。 8 –

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

還有關於流的好文章：Processing Data with Java SE 8 Streams

來源

2016-12-05 23:52:12 Fuping

我們可以1拆binaryString作爲分隔符

例如： N = 1041 BinaryString = 10000010001

當其分割基於1作爲分隔符我們得到[，00000，000]

，然後將子問題變得找到與最大長度的陣列

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

來源

2017-01-06 06:51:22 hemantvsn

如果二進制是：1000100000？你的代碼返回5，這是不正確的。它應該返回3.因爲最後一組零在末尾不受1限制。 –

我覺得@ saka1029是幾乎沒有，就像@xuesheng表示，如果例如輸入是2 = 010，4 = 100，6 = 110

我想建議的解決方案是行不通的做到這一點下面代替

static int solution(int n) { 
    return solution(n, 0, 0, 0); 
} 

static int solution(int n, int max, int current, int index) { 
    if (n == 0) 
     return max; 
    else if (n % 2 == 0 && index == 0) 
     return 0; 
    else if (n % 2 == 0 && index > 0) 
     return solution(n/2, max, current + 1, index + 1); 
    else 
     return solution(n/2, Math.max(max, current), 0, index + 1); 
}

來源

2017-02-17 10:08:46 Edi

通過hemantvsn的解決方案是偉大的，除了在需要對尾隨零被刪除

private static int solution(int N) { 
      int gap = 0; 
      String binaryStr = Integer.toBinaryString(N); 

      String[] zeroArrays = binaryStr.split("1"); 

      String[] zeroTruncated = new String[0]; 

      System.out.println(Arrays.toString(zeroArrays)); 
      if (Integer.lowestOneBit(N) != 1) { 
       zeroTruncated = Arrays.copyOf(zeroArrays, zeroArrays.length-1); 

      } 
      for(String zeroArray : zeroTruncated) { 
       gap = zeroArray.length() > gap ? zeroArray.length() : gap; 
      } 
      return gap; 
     }

來源

2017-03-17 00:23:47

由於很多人都在處理解決方案的尾隨零狀態下面臨的問題。以下是我通過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); 
    } 

}

來源

2017-05-07 10:52:27 Yoda

Objective C的解決方案

int solution(int N) { 
    if (N==0) 
    { 
     return 0; 
    } 
    int maximumGap = -1; 
    int currentGap = 0; 
    while(N>0) 
    { 
     if (N%2 == 1) 
     { 
      if (currentGap>0) 
      { 
       maximumGap = maximumGap>currentGap?maximumGap:currentGap; 
      }else 
      { 
       maximumGap = 0; 
      } 
      currentGap = 0; 
     } 
     else if(maximumGap>-1) 
     { 
      currentGap++; 
     } 
     N=N/2; 
    } 
    return maximumGap; 
}

來源

2017-08-04 07:27:57

我的解決辦法。 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; 
     } 
    }

來源

2017-09-19 00:55:06 Jaumzera

is this part else {pos ++; }需要？似乎沒有其他0的值，因爲二進制數始終以1開頭，並且從內部循環跳轉到有1個值時。或者它考慮到某些人手動不是從解析中手動輸入String binary。 –

那麼@MichałZiobro......你是對的......我又做了一遍。 – Jaumzera

試試這個。我沒有使用遞歸。

private static int binaryGap(int N){ 
    int gap1 = 0, gap2 = 0, gapCounter = 0; 

    for(int i = N; i>=0; i--) 
    { 
     if(N < 1) break; 

     //binary 0 
     if(N%2 == 0) { 
      gap1++; 
     } 
     //binary 1 
     else 
     { 
      gap2 = gap2 > gap1 ? gap2 : gap1; 
      gap1 = 0; 
      gapCounter++; 
     } 
     if(gapCounter==1) gap2=0; 
     N = N/2; 
    } 
    return gap2; 
}

來源

2017-10-17 07:04:41 Ikhsan

// you can write to stdout for debugging purposes, e.g. 
// printf("this is a debug message\n"); 

int solution(int N) { 
    int b; 
    int zeroCounter = 0; 
    int prev = 0; 
    int c = -1; 
    while (N) { 
     b = N % 2; 
     N = N/2; 
     if ((b==1)||(c==0)) { 
      c=0; 

      //printf("%d", b); 
      if (b == 1) { 

       //printf("%d", b); 
       //checkTrailZero=prev; 
       if (prev < zeroCounter) { 
        prev = zeroCounter; 
       } 
       zeroCounter = 0; 
      } else { 

       zeroCounter++; 
      // printf("--%d--", zeroCounter); 
      } 
     } 
    } 
    //printf("longest%d", prev); 
    return prev;}

來源

2017-11-19 01:36:17

測試得分codility 100％使用 100出100 points.Programming語言：用c 總時間：70分鐘使用有效時間：70分鐘注：沒有定義尚未任務時間表 –

歡迎SO。請在答案中編輯您的附加信息。另外，考慮添加幾行解釋。 – yacc

這裏正在代碼所有測試用例通過，

package org.nishad; 

import java.util.Arrays; 

public class BinaryGap { 
    public static void main(String[] args) { 
     int N = 1; 
     int result; 
     //converting integer to binary string 
     String NString = Integer.toBinaryString(N); 
     //Removing the Trailing Zeros 
     NString = NString.replaceFirst("0*$",""); 
     //Split the binary string by one or more one(regex) for arrays of zeros 
     String[] NStrings = NString.split("1+"); 
     //Storing the array length 
     int length = NStrings.length; 

     if(length==0) // if length is zero no gap found 
      result = length; 
     else   
      { 
      //Sorting the array to find the biggest zero gap 
      Arrays.sort(NStrings, (a, b)->Integer.compare(a.length(), b.length())); 
      result = NStrings[length-1].length(); 
      } 


     System.out.println(NString); 

     System.out.println(result); 
    } 
}

來源

2018-02-12 15:09:21 Nishad

使用遞歸求解二進制間隙

回答

相關問題