Project Euler #169: Exploring th

暴力破解

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