企业网站能不能个人备案,wordpress最好的编辑器,软件开发生命周期,wordpress获取图片原图3348.最小可整除数位乘积II
难度#xff1a;困难
问题描述#xff1a;
给你一个字符串num#xff0c;表示一个正整数#xff0c;同时给你一个整数t。
如果一个整数没有任何数位是0#xff0c;那么我们称这个整数是无零数字。
请你返回一个字符串#xff0c;这个字符…3348.最小可整除数位乘积II
难度困难
问题描述
给你一个字符串num表示一个正整数同时给你一个整数t。
如果一个整数没有任何数位是0那么我们称这个整数是无零数字。
请你返回一个字符串这个字符串对应的整数是大于等于num的最小无零整数且各数位之积能被t整除。如果不存在这样的数字请你返回-1。
示例1
输入num1234,t256
输出1488
解释
大于等于1234且能被256整除的最小无零整数是1488它的数位乘积为256。
示例2
输入num12355,t50
输出12355
解释
12355已经是无零且数位乘积能被50整除的整数它的数位乘积为150。
示例3
输入num11111,t26
输出-1
解释
不存在大于等于11111且数位乘积能被26整除的整数。
提示
2num.length2*105
num只包含[0,9]之间的数字。
num不包含前导0。
1t1014 问题分析及解题思路
这个问题感觉是要用枚举算法来解决从num整数开始依次向后面列举检验列举出来的整数是不是无零数字如果是再计算各数位之积检验能否被t整除如果能够被t整除则就是所要寻找的数位之积能被t整除的大于等于num的最小整数。 但示例3又说到num11111,t26时没有满足条件的无零数字要输出-1。这个怎么办呢很显然从“11111”整数开始依次向后面列举是永远不能找出这样一个无零数字使得其数位之积能被26整除的所以如果用枚举算法这就成了一个举不胜举无穷的死循环问题得不到解决。 其实这个问题还是一个有趣的数字问题我们发现t262*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,t1):n0while t%i0:nn1tt//iif n1 and i10:return Trueelse:return False#找数位之积能被t整除的大于等于num的最小整数
def minInt(num,t):numint(num)while True:if fj(t):return -1kstr(num)if isNozero(k):jreduce(lambda x,y:x*y,list(map(int,list(k))))if j%t0:return kelse:numnum1else:numnum1
numinput(pls input num)
tint(input(pls input t))
print(minInt(num,t)) 运行实例一
pls input num1234
pls input t50
1255 运行实例二
pls input num1123
pls input t39
-1 运行实例三
pls input num12345
pls input t120
12345 感悟
当解决问题无法继续下去时应该停下来仔细分析问题或许就有新的发现进而完善自己的解决方法。
