LeetCode Ugly Number

本文主要是介绍LeetCode Ugly Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

中文描述：

中文：写程序判断指定数字是否为丑数

说明：丑数具有如下特征：1是丑数，丑数可以表示为有限个2、3、5的乘积

首先是一种复杂的做法，导致直接超时

public class Solution 
{
    boolean t = false;
    public boolean isUgly(int num) 
    {
        if(num == 1)
            t = true;
        else
        {
            for(int i = 2; i * i <= num; i++)
            {
                if(num % i == 0)
                {
                    if(i == 2 || i == 3 || i == 5)
                    {
                        while(num % i == 0)
                            num = num / i;
                    }
                    else
                    {
                        t = false;
                        break;
                    }
                }
            }
            if(num > 1)
            {
                if(num == 2 || num == 3 || num == 5)
                {
                    t = true;
                }
                else
                    t= false;
            }
        }
        return t;
    }
}

错误原因：Time Limit Exceeded，超时

而后在网上看了一种非常简单的方法，其实也很简单，因为只要判断给定的一个数的质因子中是否只含有2,3,5。那么可以每次直接用这三个数去除，如果发现最后这个数能被2,3,5整除，那么就是丑数，如果最后发现被这三个数不能整除，那么就说明还有其他质因子，所以不是丑数。

代码如下：

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

这篇关于LeetCode Ugly Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---