Google foobar challenge
Level 3:起初的想法是用dp来解，但是问题来了，input的数可以最多有309位数字，是一个非常大的数，但是一个array 或者 arraylist的 limits 是 2^31 - 1， 也就是说根本无法储存，所以要引入BigInteger 类来处理此问题。
Here is the solution：
import java.math.BigInteger;
public class main {
public static void main(String[] args){
String x = "13";
BigInteger leng = new BigInteger(x);
BigInteger one = new BigInteger("1");
BigInteger _one = new BigInteger("-1");
// leng = leng.add(_one);
// System.out.println(leng.toString(2));
String test = leng.toString(2);
// System.out.println(leng.toString(2));
//
// System.out.println(leng.bitLength());
int count = 0;
while(leng.bitLength() !=1){
int lowestSetbit = leng.getLowestSetBit();
// System.out.println(check_add(leng.toString(2)));
if(check_add(leng.toString(2))&& leng.bitLength() != 2){
// System.out.println(1);
leng = leng.add(one);
count = count + 1 ;
}
else{
if(lowestSetbit >= 1){
count++;
leng = leng.shiftRight(1);
// System.out.println(leng.toString(2));
// System.out.println(lowestSetbit);
}
else{
leng = leng.add(_one);
count = count + 1;
// System.out.println(leng.toString(2));
}
}
}
System.out.println(count);
// return count;
}
private static boolean check_add(String x){
boolean need_add = true;
for(int i = 0 ; i < x.length(); i++){
// System.out.println(x.substring(i,i+1));
if(Integer.parseInt(x.substring(i,i+1)) != 1){
// System.out.println("22222");
need_add = false;
}
}
return need_add;
}
}
页:
[1]