题目
暴力破解
package com.company;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int fn = in.nextInt();
int n = (int) (Math.log((double) fn) / Math.log((double) 2));
LinkedList<ArrayList<Integer>> outputList = new LinkedList<ArrayList<Integer>>();
int size = (int) (Math.pow(3, n + 1));
for (int i = 0; i < size; i++) {
int number = i;
ArrayList<Integer> innerList = new ArrayList<Integer>();
for (int j = n; j >= 0; j--) {
int div = (int) (Math.pow(3, j));
int result = number / div;
innerList.add(result);
number = number % div;
}
outputList.add(innerList);
}
for (int i = 0; i < outputList.size(); i++) {
int calculateResult = 0;
for (int j = 0; j < outputList.get(i).size(); j++) {
calculateResult += ((int) (Math.pow(2, outputList.get(i).size() - 1 - j))) * outputList.get(i).get(j);
}
if (calculateResult != fn) {
outputList.remove(i);
i = i - 1;
}
}
System.out.println(outputList.size());
}
}
递归
类似于斐波那契数列
if (n == 0)
return 1;
if (n % 2 ==1)
return f(n / 2) + f(n/2 - 1);
return f(n / 2);
package com.company;
import java.util.Scanner;
public class Solution {
static long div2_total = 0;
static long minus1_total = 0;
static long f_total = 0;
static long f1_total = 0;
static long f2_total = 0;
static long f3_total = 0;
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
String n = in.nextLine();
long time = System.currentTimeMillis();
f(n);
f_total = System.currentTimeMillis()-time;
System.out.println("f_total="+f_total);
System.out.println("div2_total="+div2_total);
System.out.println("minus1_total="+minus1_total);
System.out.println("other_total="+(f_total-div2_total-minus1_total));
System.out.println("f1_total="+f1_total);
System.out.println("f2_total="+f2_total);
System.out.println("f3_total="+f3_total);
}
public static int f(String n) {
char lastNum = n.charAt(n.length() - 1);
if (n.equals("0")) {
return 1;
} else if ((lastNum == '0') ||
(lastNum == '2') ||
(lastNum == '4') ||
(lastNum == '6') ||
(lastNum == '8')) {
return f(div2(n)) + f(div2minus1(n));
} else {
return f(div2(n));
}
}
public static String div2(String n) {
long time = System.currentTimeMillis();
if (n.equals("1") || n.equals("0")) {
div2_total += System.currentTimeMillis() - time;
return "0";
}
String output = "";
int tmp = 0;
for (int i = 0; i < n.length(); i++) {
if (!(i == 0 && ((tmp * 10 + Integer.parseInt(String.valueOf(n.charAt(i)))) / 2) == 0)) {
output = output + ((tmp * 10 + Integer.parseInt(String.valueOf(n.charAt(i)))) / 2);
}
if (i != (n.length() - 1) && ((tmp * 10 + Integer.parseInt(String.valueOf(n.charAt(i)))) % 2 != 0)) {
tmp = 1;
} else {
tmp = 0;
}
}
div2_total += System.currentTimeMillis() - time;
return output;
}
public static String div2minus1(String n) {
String output = div2(n);
return minus1(output);
}
public static String minus1(String n) {
long time = System.currentTimeMillis();
if (n.equals("1") || n.equals("0")) {
return "0";
}
int[] numbers = new int[n.length()];
for (int i = 0; i < n.length(); i++) {
numbers[i] = Integer.parseInt(n.charAt(i) + "");
}
if (numbers[numbers.length - 1] == 0) {
for (int i = numbers.length - 1; i >= 0; i--) {
if (numbers[i] != 0) {
numbers[i] = numbers[i] - 1;
for (int j = i + 1; j < numbers.length; j++) {
numbers[j] = 9;
}
break;
}
}
} else {
numbers[numbers.length - 1] = numbers[numbers.length - 1] - 1;
}
String output = "";
boolean isHead = true;
for (int i = 0; i < numbers.length; i++) {
if (isHead) {
if (numbers[i] == 0) {
continue;
} else {
isHead = false;
}
}
output += numbers[i];
}
minus1_total += System.currentTimeMillis() - time;
return output;
}
}
官方答案
package com.company;
import java.math.BigInteger;
import java.util.*;
public final class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String n = in.nextLine();
System.out.println(new Solution().run(new BigInteger(n)));
}
public String run(BigInteger number) {
return countWays(number, number.bitLength() - 1, 2).toString();
}
/*
* ways(n, i, j) is the number of ways that the number n can be expressed as
* an unordered sum of powers of 2 such that all these conditions are true:
* - The highest possible power is 2^i
* - The 2^i term is used between 0 and j times
* - All lower powers of 2 are used no more than 2 times
*/
// Memoization
private Map<List<BigInteger>,BigInteger> ways = new HashMap<>();
private BigInteger countWays(BigInteger number, int exponent, int repetitions) {
List<BigInteger> key = Arrays.asList(number, BigInteger.valueOf(exponent), BigInteger.valueOf(repetitions));
if (ways.containsKey(key))
return ways.get(key);
BigInteger result;
if (exponent < 0)
result = number.equals(BigInteger.ZERO) ? BigInteger.ONE : BigInteger.ZERO;
else {
result = countWays(number, exponent - 1, 2);
BigInteger pow = BigInteger.ONE.shiftLeft(exponent);
BigInteger upper = pow.multiply(BigInteger.valueOf(repetitions + 2));
if (repetitions > 0 && pow.compareTo(number) <= 0 && number.compareTo(upper) < 0)
result = result.add(countWays(number.subtract(pow), exponent, repetitions - 1));
}
ways.put(key, result);
return result;
}
}
