LeetCode 625 最小因式分解 Minimum Factorization难度Medium会员题谷歌面试真题题目原文625. Minimum FactorizationGiven a positive integer num, find the smallest positive integer x such that the product of all digits of x is equal to num.If no such x exists OR the result exceeds the limit of 32-bit signed integer (231−121474836472^{31}-12147483647231−12147483647), return 0.中文题目描述给定一个正整数num找到最小正整数 x要求 x 的每一位数字相乘的乘积等于 num。如果不存在这样的 x或者得到的数字超出32位有符号整数上限2147483647返回 0。示例示例1输入num 48输出68解释6 × 8 48并且68是满足条件最小数字。对比48可以拆成 2226 → 2226很大或者344 →3446848 →6868最小示例2输入num 15输出353 × 5 15示例3输入num1输出1示例4输入num13质数大于9输出0因为13无法拆成2~9数字相乘费曼学习法讲解通俗讲给小白费曼核心用最简单语言讲清楚发现卡点补齐漏洞。第一步读懂问题把翻译成人话任务把数字num拆成若干单个数字2~9不能用0、1相乘然后拿这些数字拼成一个整数要让这个整数尽可能小如果拆不开返回0拼成的数太大超过2147483647也返回0。⚠️ 关键点1怎么拼数字最小比如拆出来数字是 [8,6]直接拼86排序变成[6,8]得到68。同样一组数字升序排列得到的整数最小例[2,2,2,6] →2226[3,4,4]→344[6,8]→68。对比68最小。⚠️ 关键点2怎么拆因子才能让因子个数最少数字位数越少整个数字一定更小。比如48拆2,2,2,6 →4个数字 →四位数2226拆3,4,4 →3个数字 →344拆6,8 →2个数字 →两位数68 ✅最优想因子数量尽可能少就要优先拿大的个位数因子所以我们从9往下试9,8,7…一直到2能整除就拿这个因子。举例子num48试948 ÷9 不能整除跳过试848 ÷86可以整除拿出因子8num变成6继续循环再试9到2此时num6试9不行…试6可以整除拿出因子6num1num等于1分解结束。收集到因子列表[8,6]排序 →[6,8]拼成68⚠️ 关键点3什么时候返回0分解完如果num≠1说明剩下的数是大于9的质数无法拆成单个数字。例 num139~2都不能整除循环结束num13≠1返回0。⚠️ 关键点4边界 32位整数上限2147483647。如果拼出来的数字 2147483647返回0。总结贪心策略一句话从9到2依次取因子收集所有因子升序排序拼接最后校验是否分解完成、是否溢出。第二步思路完整逻辑流程特殊情况num 10直接返回num本身就是单个数字创建空列表保存取出的因子循环d从9 downto 2while num可以被d整除把d加入因子列表num num // d循环结束判断如果num≠1 →无法分解 return 0因子列表从小到大排序把排序后的数字拼成整数判断是否超过32位上限超过返回0否则返回结果第三步反例测试验证思路测试 num13循环9~2全部不能整除因子列表为空num13≠1 →return0 ✅测试 num1直接返回1 ✅测试 num249不行824%80 →因子8num3继续9~2到33%30因子3num1因子列表 [8,3]排序→[3,8] →383×824 ✅Python完整代码每行详尽注释classSolution:defsmallestFactorization(self,num:int)-int: LeetCode 625 最小因式分解 :param num: 输入正整数 :return: 满足条件最小整数不存在/溢出返回0 # 边界情况num小于10本身就是个位数直接返回自己ifnum10:returnnum# 列表用来存放我们提取到的因子都是2~9的单个数字factor_digits[]# 贪心从9向下遍历到2优先拿大因子减少数字总位数# range(9,1,-1) 生成9,8,7,6,5,4,3,2fordinrange(9,1,-1):# 只要当前d可以整除num就持续提取这个因子whilenum%d0:# 将d存入因子列表factor_digits.append(d)# num除以d更新num整数除法numnum//d# 循环结束后如果num不等于1代表剩下的数是大于9的质数无法拆成单个数字ifnum!1:return0# 升序排序因子核心小数字放高位拼成的整数才最小factor_digits.sort()# 把因子列表拼成整数result0fordigitinfactor_digits:# 例如 [6,8]第一轮 result 0*10 66第二轮 result6*10868resultresult*10digit# 32位有符号整数上限 2^31 -1 2147483647INT32_MAX2**31-1# 如果结果超出上限返回0否则返回resultifresultINT32_MAX:return0else:returnresult# 测试示例 if__name____main__:solSolution()print(sol.smallestFactorization(48))# 预期输出68print(sol.smallestFactorization(15))# 预期输出35print(sol.smallestFactorization(13))# 预期输出0质数无法分解print(sol.smallestFactorization(1))# 预期输出1print(sol.smallestFactorization(24))# 预期输出38时间 空间复杂度分析时间复杂度O(log(num))O(log(num))O(log(num))。每次循环num不断被除数字快速变小排序最多只有很少个因子最多不超过log₂num个常数级别近似常数空间复杂度O(1)O(1)O(1)因子列表最多存放常数个数字。应用场景举例场景1密码生成业务需求给定一个乘积数字生成最短的数字密码密码每一位相乘等于给定乘积密码数值尽可能小。例如业务输入48生成最小密码68。场景2数字编码/商品编码规则一套编码规则编码每一位数字相乘等于产品编号要求编码最短且字典序最小。用这个算法生成编码。场景3面试数论基础模块谷歌、腾讯面试原题用来考察贪心算法 质因数分解思维。考察点能不能想到「优先取大因子减少位数排序得到最小数字」这个贪心思路。场景4数学游戏数字游戏给定N找最小数各位乘积N。直接套用该代码求解。拓展思考费曼查漏❓为什么不从2往9取因子如果从小到大取48会拿到一堆2[2,2,2,6] →2226数字很大不是最优解。贪心策略失效。所以必须从9到2取因子保证因子数量最少。❓为什么收集完因子之后要排序我们收集的时候拿到的是 [8,6]大的在前排序变成[6,8]小数放高位数字最小。比如[9,2] →29 比92更小。