数位之积

[编程题]数位之积

热度指数：7350 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现给定任意正整数 n，请寻找并输出最小的正整数 m（m>9），使得 m 的各位（个位、十位、百位 ... ...）之乘积等于n，若不存在则输出 -1。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

Java

softwareGxy

import java.util.*;


public class Solution {
    /**
     * 输入一个整形数值，返回一个整形值
     * @param n int整型 n>9
     * @return int整型
     */
    public int solution (int n) {
        // write code here
        if(n<10)
            return 10+n;
        else{
            int m=0,base=1;
            while (n>9) {
                int i;
                for (i = 9; i > 1; i--) {
                    if (n % i == 0) {//能被整除
                        m=m+i*base;
                        base=base*10;
                        n=n/i;
                        break;
                    }
                }
                if(n>9&&i==1) //可能是一个不能被2-9整除的数 例如13
                    break;
            }
            if(n<=9){
                m=m+n*base;  //加上位数最高的那位
                return m;
            }else
                return -1;
        }
    }
}

发表于 2020-06-06 19:41:50 回复(0)

Java

pigroar

分情况，看n和10的大小关系

小于10，十位必是1；

大于10，目的是分解到最少的因数，当然直接淘汰素数（或最大因子大于等于10的数）

最后逆序组合

public static int solution (int n) {
        // write code here
        List<Integer> m = new ArrayList<>();
        if (n < 10){
            return 10 + n;
        }

        while (n >= 10){
            for (int i = 9; i >= 2; i--) {
                if (0 == n % i){
                    m.add(i);
                    n = n / i;
                    break;
                }
                if (2 == i) return -1;
            }
        }

        m.add(n);
        int ans = 0;
        System.out.println(m);
        for (int i = 0; i < m.size(); i++) {
            ans += m.get(i) * Math.pow(10, i);
        }
        return ans;
    }

拙见，望指点~这算是贪婪算法的思想吗？

发表于 2020-03-30 21:55:01 回复(0)