当前位置：首页 > article >正文

用枚举算法解决LeetCode第3348题最小可整除数位乘积II

article 2024/11/17 1:23:06

3348.最小可整除数位乘积II

难度：困难

问题描述：

给你一个字符串num，表示一个正整数，同时给你一个整数t。

如果一个整数没有任何数位是0，那么我们称这个整数是无零数字。

请你返回一个字符串，这个字符串对应的整数是大于等于num的最小无零整数，且各数位之积能被t整除。如果不存在这样的数字，请你返回"-1"。

示例1：

输入：num="1234",t=256

输出："1488"

解释：

大于等于1234且能被256整除的最小无零整数是1488，它的数位乘积为256。

示例2：

输入：num="12355",t=50

输出："12355"

解释：

12355已经是无零且数位乘积能被50整除的整数，它的数位乘积为150。

示例3：

输入：num="11111",t=26

输出："-1"

解释：

不存在大于等于11111且数位乘积能被26整除的整数。

提示：

2<=num.length<=2*105

num只包含['0','9']之间的数字。

num不包含前导0。

1<=t<=1014

问题分析及解题思路：

这个问题感觉是要用枚举算法来解决，从num整数开始，依次向后面列举，检验列举出来的整数是不是无零数字，如果是，再计算各数位之积，检验能否被t整除，如果能够被t整除，则就是所要寻找的数位之积能被t整除的大于等于num的最小整数。

但示例3又说到num="11111",t=26时，没有满足条件的无零数字，要输出-1。这个怎么办呢？很显然，从“11111”整数开始，依次向后面列举，是永远不能找出这样一个无零数字，使得其数位之积能被26整除的，所以如果用枚举算法，这就成了一个举不胜举无穷的死循环，问题得不到解决。

其实这个问题还是一个有趣的数字问题，我们发现t=26=2*13，要一个无零数字数位之积能够被26整除，说明这个无零数字的各数位之积必须要有一个因子是13，这样才能除尽，否则是永远不能被26整除的，但数位之积是各位数字的乘积，只能是1、2、......、9的乘积，不可能出现13这个因子，所以我们只要对t进行分解质因数，如果t中有大于10的质因数，则直接就可以判断，不存在这样的无零数字，其数位之积能够被t整除，直接输出-1即可。

根据上面的分析，解题思路如下：

编写检验整数字符串s是否是无零数字的函数isNozero(s)，如果s是无零数字，返回True，否则返回False
编写检验一个数字t是否有大于10的质因数的函数fj(t)，如果有大于10的质因数，返回True，否则返回False
编写寻找各数位之积大于等于num的最小无零数字的函数minInt(num,t)，如果没有找到，返回-1，如果找到，返回找到的无零整数字符串
最后编写主程序，调用各函数即可解决问题

程序如下：

from functools import reduce
#检验整数字符串s中有没有数字0，如果有，返回False，否则返回True
def isNozero(s):
    return False if '0' in s else True

#分解整数t，如果有大于10的质因子，返回True，否则返回False
def fj(t):
    for i in range(2,t+1):
        n=0
        while t%i==0:
            n=n+1
            t=t//i
        if n>=1 and i>10:
            return True
    else:
        return False

#找数位之积能被t整除的大于等于num的最小整数
def minInt(num,t):
    num=int(num)
    while True:
        if fj(t):
            return -1
        k=str(num)
        if isNozero(k):
            j=reduce(lambda x,y:x*y,list(map(int,list(k))))
            if j%t==0:
                return k
            else:
                num=num+1
        else:
            num=num+1
num=input('pls input num=')
t=int(input('pls input t='))
print(minInt(num,t))