LeetCode.263 丑数

题目描述：

263. 丑数 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入： n = 6
输出： true
解释： 6 = 2 × 3

示例 2：

输入： n = 8
输出： true
解释： 8 = 2 × 2 × 2

示例 3：

输入： n = 14
输出： false
解释： 14 不是丑数，因为它包含了另外一个质因数 7 。

示例 4：

输入： n = 1
输出： true
解释： 1 通常被视为丑数。

提示：

• −231 <=n<=231 −1-2^{31} <= n <= 2^{31} - 1−231 <=n<=231 −1

思路分析

数学法

根据丑数的定义，0 和负整数一定不是丑数。

当 n>0 时，若 n 是丑数，则 n 可以写成 n=2a×3b×5cn = 2^a × 3^b × 5^cn=2a×3b×5c 的形式，其中 a,b,c 都是非负整数。

特别地，当 a,b,c 都是 0 时，n=1。

所以我们可以对 n 先除以2，当能除以 2，则更新 n = n / 2, 当 n 不能被 2 整除了，再看能否被 3 整除，如果能被 3 整除，就继续除 3，同理，不能被 2 或 3 整除了，继续看是否能被 5 整除，如果能被 5 整除，就继续除以 5，最后再看不能被 2、3、5 整除后，直接跳出循环，如果剩下的值不是1，那么说明 n 包含其他质因数，不是丑数。

AC代码

class Solution {
    fun isUgly(n: Int): Boolean {
        var n = n
        if (n <= 0) return false
        while (n % 2 == 0) n /= 2
        while (n % 3 == 0) n /= 3
        while (n % 5 == 0) n /= 5
        return n == 1
    }
}

优化下

class Solution {
    fun isUgly(n: Int): Boolean {
        var n = n
        if (n <= 0) return false

        val factors: IntArray = intArrayOf(2, 3, 5)
        factors.forEach {
            while (n % it == 0) n /= it
        }
        return n == 1
    }
}

总结

这题其实就是简单的数学题，当n为正整数的时候我们只要 n 执行 2 3 5 的整除操作即可，直到 n 被除干净就算丑数。

参考

丑数 - 丑数 - 力扣（LeetCode） (leetcode-cn.com)

【宫水三叶】简单的分情况讨论题，以及为啥先除哪个都可以 - 丑数 - 力扣（LeetCode） (leetcode-cn.com)