题意

Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a.

If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.

样例

Given a = 48, return 68.
Given a = 15, return 35.

1.解题思路

  这道题我知道的是有两种解法：一种是递归的方式，另一种解法的比较巧妙。
  简单的介绍一下递归的思路，当n能整除i时，取a = i,b = n / i,然后递归求解a，b的值，最后将a b两个数字组合起来，但是注意a与b左右的情况。
  另一种方法比较巧妙，我们从9到2，让n不断的求解，求ta里面分贝有几个 2 ~ 9，然后从小到大的打印就行了。为什么这里是这样的，想一想，我们化解一个数字，无非化成2 ~ 9中的数字。同时，我们在除以8时，相当于同时除以2、4，6也是这样的。

2.代码

(1).递归（内存超出）

   public int smallestFactorization(int a) {
        int res = ergodic(a);
        return res == Integer.MAX_VALUE || res == -1 ? 0 : res;
    }

    private int ergodic(int n) {
        if (check(n) || n < 10) {
            if (n > 10) {
                return -1;
            }
            return n;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int a = n / i;
                int b = i;
                int num1 = ergodic(a);
                int num2 = ergodic(b);
                if(num1 == -1 || num2 ==-1){
                    return -1;
                }
                min = Math.min(min, Integer.valueOf(num1 + "" + num2));
                min = Math.min(min, Integer.valueOf(num2 + "" + num1));
            }
        }
        return min;
    }

    private boolean check(int n) {
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

(2).不知道什么方法

    public int smallestFactorization(int a) {
        int arr[] = new int[10];
        for (int i = 9; i >= 2; i--) {
            while (a % i == 0) {
                arr[i]++;
                a = a / i;
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 2; i <= 9; i++){
            for(int j = 0; j < arr[i]; j++){
                stringBuilder.append(i);
            }
        }
        if(stringBuilder.toString().equals("")){
            return 0;
        }
        return Long.valueOf(stringBuilder.toString()) > Integer.MAX_VALUE ? 0:Integer.valueOf(stringBuilder.toString());
    }