分裂二進制字符串，使它是5的冪

Question

我想分割一個二進制字符串，這樣可以將字符串切成最小的正整數，它們中的每一個都是5的冪。如果沒有這樣的件返回-1代替。

public class Power { 
    public int numsOfWays(String s) { 
     long[] f = new long[s.length() + 1]; 
     f[0] = 0; 
     for (int i = 1; i <= s.length(); ++i) { 
      f[i] = Integer.MAX_VALUE; 
      for (int j = 1; j <= i; ++j) { 
       if (s.charAt(j - 1) == '0') { 
        continue; 
       } 
       int num = Integer.parseInt(s.substring(j - 1, i), 2); 
       if (isPower(num)) { 
        f[i] = Math.min(f[i], f[j - 1] + 1); 
       } 
      } 
     } 
     return f[s.length()] == Integer.MAX_VALUE ? -1 : (int) f[s.length()]; 
    } 

    private boolean isPower(long val) { 
     if (val == 0) { 
      return false; 
     } 
     int n = (int) (Math.log(val)/Math.log(5)); 
     return Math.pow(5, n) == val; 
    } 

    public static void main(String[] args) { 

     Power b = new Power(); 
     System.out.println(b.numsOfWays("111011100110101100101110111")); 
    } 
} 

我收到此錯誤： -

Exception in thread "main" java.lang.NumberFormatException: For input string: "11101110011010110010111011100000" 
    at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65) 
    at java.lang.Integer.parseInt(Integer.java:583) 
    at abc.Power.numsOfWays(Power.java:13) 
    at abc.Power.main(Power.java:33) 

Answer 1

問題是在你的代碼的第13行： 行：

int num = Integer.parseInt(s.substring(j - 1, i), 2); 

有一個問題，因爲該值太高渴望處理。

將其更改爲：

long num = Long.parseLong(s.substring(j - 1, i), 2); 

，它應該工作。

編輯：整個代碼看起來是這樣的：

public class Power { 
    public int numsOfWays(String s) { 
     long[] f = new long[s.length() + 1]; 
     f[0] = 0; 
     for (int i = 1; i <= s.length(); ++i) { 
      f[i] = Integer.MAX_VALUE; 
      for (int j = 1; j <= i; ++j) { 
       if (s.charAt(j - 1) == '0') { 
        continue; 
       } 
       long num = Long.parseLong(s.substring(j - 1, i), 2); 
       if (isPower(num)) { 
        f[i] = Math.min(f[i], f[j - 1] + 1); 
       } 
      } 
     } 
     return f[s.length()] == Integer.MAX_VALUE ? -1 : (int) f[s.length()]; 
    } 

    private boolean isPower(long val) { 
     if (val == 0) { 
      return false; 
     } 
     int n = (int) (Math.log(val)/Math.log(5)); 
     return Math.pow(5, n) == val; 
    } 

    public static void main(String[] args) { 
     Power b = new Power(); 
     System.out.println(b.numsOfWays("111011100110101100101110111")); // 5 
     System.out.println(b.numsOfWays("11111111111111111111111111111111111111111111111111")); // 50 
    } 
} 

，輸出是：

5 
50