数位之积

[编程题]数位之积

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

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

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

Python

牛客140978407号

python 67ms

class Solution:
    dig = [9, 8, 7, 6, 5, 4, 3, 2]
    n = 11
    res = 0
    out = []
    su = False

    def f1(self, n):
        # global mul,su
        for i in self.dig:
            if n % i == 0:
                self.out.append(i)
                self.f1(n / i)
                return self.out
        if n > 9:
            self.su = True

    def solution(self, n):
        if n < 10:
            print(10 + n)
        else:
            outt = self.f1(n)
            if self.su:
                self.res = -1
            else:
                for j in range(len(outt)):

                    self.res =self.res+ 10 ** j * outt[j]
            return self.res

发表于 2021-11-12 10:44:26 回复(0)

Python

_Dexter·

关键思想就是要从大到小遍历，因为要保证输出的位数越少越好，所以用越大的因子会用越少的位数除完，而相同的位数内，高位的数字越大，低位的就越小，倒序输出时的数就越小。
class Solution:
    def solution(self , n ):
        # write code here
        def search(n,temp):
            for i in range(9,1,-1):
                res = n/i
                if n%i==0:
                    temp = temp*10+i
                    if res==1:
                        b= 0
                        while temp !=0:
                            a = temp%10
                            b= b*10+a
                            temp = temp//10
                        return b

                    else:
                        return search(res,temp)
        temp=0
        return search(n,temp)

发表于 2020-06-06 20:16:16 回复(0)

Python

Jaylynn

python3 非递归版本【我是递归怂 T.T】

思路重点：

逆向思维，即将n分解求能组成的最小整数
分解时从9到2分解，这样获得的数可直接组成最小整数

class Solution:
    def solution(self , n ):
        numL = []
        while True:
            num = self.getNum(n)
            if num == -1:
                return -1
            numL.append(num)
            n = n/num
            if n == 1:
                break
        res = 0
        for i in range(len(numL)):
            res += numL[i]*10**i
        return res
    
    def getNum(self,n):
        for i in range(9,1,-1):
            if n%i == 0:
                return i
        return -1

发表于 2020-03-31 23:35:17 回复(0)