leetcode [#263]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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.

Example
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.

---

解决方案

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

---

注意事项

1. 以下暴力方法会超时，不可用：

   public class Solution {
       public boolean isUgly(int num) {
           if(num <= 0) return false;
           if(num == 1) return true;
           if(isPrime(num)){
               if(!(num == 2 || num == 3 || num == 5)){
                   return false;
               }
           }
           boolean result = true;
           List<Integer> list = new ArrayList<>();
           for(int i = 2; i <= num; i++){
               if(num % i == 0){
                   list.add(i);
               }
           }
           for(int j = 0;j<list.size();j++){
               if(isPrime(list.get(j))){
                   if(!(list.get(j) == 2 || list.get(j) == 3 || list.get(j) == 5)){
                       result = false;
                       break;
                   }
               }
           }
           return result;
       }
       private static boolean isPrime(int num){
           for(int i = 2; i <= Math.sqrt(num); i++){
               if(num % i == 0){
                   return false;
               }
           }
           if(num == 1) return false;
           return true;
       }
   }

2. 解决方案中的方法非常灵活巧妙。对于给定的数num，不断将其除以2,3,4,5（前提条件是能整除），该过程结束后，如果结果为1，说明num是由若干个2,3,5相乘得到的，这就满足ugly number的条件；而如果还未达到1，说明有其他不能被2,3,4,5整除的因子，也就是发现了不为2,3,5的质因子。

3. 除以4就相当于除以2，这里是为了循环条件连贯代码结构完整。