企业官网建设流程全解析

LeetCode 625 最小因式分解 Minimum Factorization

难度：Medium（会员题，谷歌面试真题）

题目原文

625. Minimum Factorization
Given 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−1=21474836472^{31}-1=2147483647231−1=2147483647), return 0.

中文题目描述

给定一个正整数num，找到最小正整数 x，要求 x 的每一位数字相乘的乘积等于 num。
如果不存在这样的 x，或者得到的数字超出32位有符号整数上限（2147483647），返回 0。

示例

示例1：
输入：num = 48
输出：68
解释：6 × 8 = 48，并且68是满足条件最小数字。

对比：48可以拆成 2226 → 2226（很大）；或者344 →344；68=48 →68，68最小

示例2：
输入：num =15
输出：35，3 × 5 = 15

示例3：
输入：num=1
输出：1

示例4：
输入：num=13（质数，大于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，能整除就拿这个因子。

举例子：num=48

1. 试9：48 ÷9 不能整除，跳过
2. 试8：48 ÷8=6，可以整除，拿出因子8，num变成6
3. 继续循环，再试9到2，此时num=6
   试9不行…试6，可以整除，拿出因子6，num=1
4. num等于1，分解结束。收集到因子列表：[8,6]
5. 排序 →[6,8]，拼成68

⚠️ 关键点3：什么时候返回0？
分解完，如果num≠1，说明剩下的数是大于9的质数，无法拆成单个数字。
例 num=13：9~2都不能整除，循环结束num=13≠1，返回0。

⚠️ 关键点4：边界 32位整数上限：2147483647。
如果拼出来的数字 >2147483647，返回0。

总结贪心策略一句话：
从9到2依次取因子，收集所有因子，升序排序拼接；最后校验是否分解完成、是否溢出。

第二步：思路完整逻辑流程

1. 特殊情况：num < 10，直接返回num（本身就是单个数字）
2. 创建空列表保存取出的因子
3. 循环d从9 downto 2：
   while num可以被d整除：
   把d加入因子列表
   num = num // d
4. 循环结束，判断：如果num≠1 →无法分解 return 0
5. 因子列表从小到大排序
6. 把排序后的数字拼成整数
7. 判断是否超过32位上限：超过返回0，否则返回结果

第三步：反例测试验证思路

测试 num=13：
循环9~2，全部不能整除，因子列表为空，num=13≠1 →return0 ✅

测试 num=1：直接返回1 ✅

测试 num=24：
9不行，8：24%8=0 →因子8，num=3；
继续9~2，到3，3%3=0，因子3，num=1；
因子列表 [8,3]，排序→[3,8] →38，3×8=24 ✅

Python完整代码，每行详尽注释

classSolution:defsmallestFactorization(self,num:int)->int:""" LeetCode 625 最小因式分解 :param num: 输入正整数 :return: 满足条件最小整数，不存在/溢出返回0 """# 边界情况：num小于10，本身就是个位数，直接返回自己ifnum<10: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%d==0:# 将d存入因子列表factor_digits.append(d)# num除以d，更新num，整数除法num=num//d# 循环结束后，如果num不等于1，代表剩下的数是大于9的质数，无法拆成单个数字ifnum!=1:return0# 升序排序因子！！核心：小数字放高位，拼成的整数才最小factor_digits.sort()# 把因子列表拼成整数result=0fordigitinfactor_digits:# 例如 [6,8]：第一轮 result = 0*10 +6=6；第二轮 result=6*10+8=68result=result*10+digit# 32位有符号整数上限 2^31 -1 = 2147483647INT32_MAX=2**31-1# 如果结果超出上限返回0，否则返回resultifresult>INT32_MAX:return0else:returnresult# ========== 测试示例 ==========if__name__=="__main__":sol=Solution()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更小。