数据结构与算法-丑数

• 丑数

  给你一个整数n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。

• 丑数 II

  给你一个整数 n，请你找出并返回第 n个 丑数 。丑数 就是只包含质因数2、3 和/或5 的正整数。

丑数

解题思路

根据给定的题意 丑数 就是只包含质因数 2、3 和/或 5 的正整数。 ，第一个想到就是因式分解。一直做除法如果这个数除到最后等于1那么就是，如果不是那么就是非丑数

代码实现

迭代
class Solution {
    public boolean isUgly(int n) {
        while(n>=1){
            if (n%2==0){
                n/=2;
            }else if(n%3==0){
                n/=3;
            }else if(n%5==0){
                n/=5;
            }else{
                return n==1;
            }
        }
        return false;
    }
}
递归
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);
        }
        return false;
    }
}

丑数 II

解题思路

第一道题从数字n入手，一步步向下做除法，试探n是不是丑数。这里需要找到第n个丑数，代表我们的思维需要从下往上，从小的数值向大寻找。定义一个丑数数组，将所有的丑数三等分，定义a,b,c来标记分别标记被2，3，5整除的数据的下标从0开始，从1开始计算到n的丑数

代码实现

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);
        }
        return false;
    }
}