LeetCode 264：丑数

链接

方法一：while

让n反复除以2、3、5 直到最后为1即为丑数，否则不是丑数；

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

或者：

class Solution {
    public boolean isUgly(int n) {
        if(n<1) return false;
        
        int[] a=new int[]{2,3,5};
        for(int k:a){

            if(n==1) break;
            while(n%k==0){
                n=n/k; // 更新n
            }
        }
        if(n==1){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

类似多叉树遍历； for遍历 2、3、5 ，让每轮得到的n去除以2、3、5；

方法二：dfs

class Solution {
    public boolean isUgly(int n) {
        // base case
        if(n<1){
            return false;
        }
        if(n==1){
            return true;
        }
        
        for(int k:new int[]{2,3,5}){
                if(n%k==0){
                    return isUgly(n/k);
                }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

或者设一个布尔标记a，更好理解；

class Solution {
        boolean a=false;
    public boolean isUgly(int n) {
        check(n);
        return a;
    }

    void check(int n){
        if(n<1){
            return;
        }
        if(n==1){
            a=true;
            return;
        }
        for(int k:new int[]{2,3,5}){
            if(n%k==0){ // 满足条件才递归
              check(n/k);  
            }
        }
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23