数据结构与算法-丑数

丑数给你一个整数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; }}