剑指offer—丑数 解答

剑指offer—丑数

题目描述

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3
示例 2:

输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3:

输入: 14
输出: false 
解释: 14 不是丑数,因为它包含了另外一个质因数 7。
说明:

1 是丑数。
输入不会超过 32 位有符号整数的范围: [−231,  231 − 1]。

思路—迭代

迭代进行取余操作,对2/3/5取余,如果最后迭代出来则返回true,说明迭代结果为1,反之则返回false

代码

class Solution {
    public boolean isUgly(int num) {
        if(num<=0) return false;
        int n = num;
        while(n!=1){
            if(n%2==0){
                n = n/2;
                continue;
            }
            if(n%3==0){
                n = n/3;
                continue;
            }
            if(n%5==0){
                n = n/5;
                continue;
            }
            return false;
        }
        return true;
    }
}

扩展—打印第N个丑数

只需要用一个变量记录当前丑数的个数,每判断一个+1

  • 如果迭代结果为1说明是丑数,执行count+1,
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        int count = 1;
        int re = 1;
        for(int i=2;count<index;i++){
            int n = i;
            while(n!=1){
                if(n%2==0){
                    n = n/2;
                    continue;
                }
                if(n%3==0){
                    n = n/3;
                    continue;
                }
                if(n%5==0){
                    n = n/5;
                    continue;
                }
                break;
            }
            if(n==1){
                count++;
                re = i;
            }
        }
        return re;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/ugly-num.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!