丑数

发表于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，263. 丑数

先看题目描述

cakvZD.png

算法和思路

递归

思路大概就是先判断该数是否大于 0，若小于等于 0，则直接返回 false；然后判断 n 能够被 2 或 3 或 5 整除，若其中一个数能整除，则用那个数整除 n，再对新产生的数字递归的调用该函数即可。递归的出口是数字等于 1时，返回 true；若数字不能被 2 或 3 或 5 整除，则返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        if (n % 2 == 0) {
            return isUgly(n / 2);
        } else if (n % 3 == 0) {
            return isUgly(n / 3);
        } else if (n % 5 == 0) {
            return isUgly(n / 5);
        } else {
            return false;
        }
    }
}

下面是题解的代码，是用的一个迭代的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        int[] factors = {2, 3, 5};
        for (int factor : factors) {
            while (n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }
}