用枚举算法解决LeetCode第3348题最小可整除数位乘积II
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))运行实例一
pls input num=1234
pls input t=50
1255
运行实例二
pls input num=1123
pls input t=39
-1
运行实例三
pls input num=12345
pls input t=120
12345
感悟：
当解决问题无法继续下去时，应该停下来仔细分析问题，或许就有新的发现，进而完善自己的解决方法。
原文地址：https://blog.csdn.net/2302_79682652/article/details/143767869
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！