力扣 263. 丑数

题目说明

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

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

  • 提示：
    • -231 <= n <= 231 - 1

示例

例1

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

例2

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

例3

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

笔者理解

此题是一道数学算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题没有太多技巧，直接进行化解因子即可，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isUgly(int num) {
        if (num < 1) { return false; }

        // 直接将num进行化解因子操作，除去2，3，5剩下的数如果不为1即为非丑数
        while (num % 2 == 0) {
            num /= 2; 
        }
        while (num % 3 == 0) {
            num /= 3; 
        }
        while (num % 5 == 0) {
            num /= 5; 
        }
        return num == 1;
    }

时间和空间效率都还行，可见此解法还比较适合此题；

image.png

总结

本题是今天的每日一题，难度只有简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。