LeetCode 题解工作台
丑数
丑数 就是只包含质因数 2 、 3 和 5 的 正 整数。 给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。 示例 1： 输入： n = 6 输出： true 解释： 6 = 2 × 3 示例 2： 输入： n = 1 输出： true 解释： …
1
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数学·driven
答案摘要
class Solution: def isUgly(self, n: int) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
丑数 就是只包含质因数 2、3 和 5 的 正 整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3
示例 2：
输入：n = 1 输出：true 解释：1 没有质因数。
示例 3：
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
提示：
-231 <= n <= 231 - 1
解题思路
方法一
class Solution:
def isUgly(self, n: int) -> bool:
if n < 1:
return False
for x in [2, 3, 5]:
while n % x == 0:
n //= x
return n == 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) due to repeatedly dividing `n` by 2, 3, and 5. Space complexity is O(1) as no extra data structures are used. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate quickly identifies the need for prime factorization.
- question_mark
Candidate efficiently handles edge cases like `n = 1`.
- question_mark
Candidate optimizes the solution with early termination when `n` is reduced.
常见陷阱
外企场景- error
Failing to check edge cases like `n = 1`.
- error
Mistaking non-ugly numbers with factors greater than 5 for ugly numbers.
- error
Not reducing `n` completely by 2, 3, or 5 before returning `true`.
进阶变体
外企场景- arrow_right_alt
Implement a solution with a different time complexity for larger inputs.
- arrow_right_alt
Optimize using bit manipulation or other low-level techniques.
- arrow_right_alt
Explore the problem with larger constraints, where the approach may need to scale.