美文网首页
Java 算法 - Minimum Factorization

Java 算法 - Minimum Factorization

作者: 琼珶和予 | 来源:发表于2018-04-02 20:19 被阅读0次

题意

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

相关文章

  • Java 算法 - Minimum Factorization

    题意 样例 1.解题思路   这道题我知道的是有两种解法:一种是递归的方式,另一种解法的比较巧妙。  简单的介绍一...

  • FM算法

    FM算法(Factorization Machine) 因子分解机(Factorization Machine, ...

  • 分解机(Factorization Machines)推荐算法

    1 分解机(Factorization Machines)推荐算法原理 1.1 分解机(Factorization...

  • 02-21:FM算法

    FM算法 回头看其实FM算法也是非常简单啊 1、算法原理 因子分解机(Factorization Machine,...

  • 非负矩阵分解(NMF)应用于scRNAseq的细胞分群

    NMF算法简介 非负矩阵分解(Non-negative Matrix Factorization, NMF)的思想...

  • ORID34 binary search

    [1482] Minimum Number of Days to Make m Bouquets 解题报告 算法 ...

  • 最小生成树(MST)

    算法导论 Exercises 23.1-8 Let T be a minimum spanning tree of...

  • 2018-05-19

    《算法》 射击气球 题目要求:https://leetcode.com/problems/minimum-numb...

  • 矩阵分解和FM

    矩阵分解(Matrix Factorization,MF)是推荐系统中非常经典的一个算法,虽然现今工业界直接使用的...

  • FM算法介绍

    概述 FM (Factorization Machine) 算法可进行回归和二分类预测,它的特点是考虑了特征之间的...

网友评论

      本文标题:Java 算法 - Minimum Factorization

      本文链接:https://www.haomeiwen.com/subject/rfaxhftx.html