UglyNumber [source code]

public class UglyNumber {
static
/******************************************************************************/
public class Solution {
    public boolean isUgly(int num) {
        if (num == 0) return false;
        if (num == 1) return true;
        return (num % 2 == 0 && isUgly(num / 2)) ||
         (num % 3 == 0 && isUgly(num / 3)) ||
          (num % 5 == 0 && isUgly(num / 5));
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        UglyNumber.Solution tester = new UglyNumber.Solution();
        int[] inputs = {1,2,3,5,6,8,14};
        for (int i : inputs) System.out.println(i + " " + tester.isUgly(i));
    }
}

这个问题刚拿到手, 一个直观的想法肯定是用 recursion/DP 来做, 不过速度肯定是不合格的; 这个题目给 tag 到 math 下面了, 感觉应该是有什么不知道的性质;

试了一下, DP 果然是overflow 了;
那么可以改成循环来做:

public class Solution {  
    public boolean isUgly(int num) {  
        if (num == 0) {  
            return false;  
        }  
        int[] divisors = {2, 3, 5};  
        for (int divisor : divisors) {  
            while(num % divisor == 0) {  
                num /= divisor;  
            }  
        }  
        return num == 1;  
    }  
}

这个技术以前已经遇到过一次了. 就是如果stack overflow, 就改成 iterative 的代码就行了; 另外这里的逻辑还是要清楚, 要判断 mod 之后等于0, 因为这个" mod 等于0"的意思就是,比如, mod 2 == 0, 意思就是2 is a factor. 只有知道了2是一个 factor 之后, n / 2是否 ugly 对于 n 是否 ugly 才有意义;

他这里这个算法写的还是比较干净整洁的, 就是分别对三个 factor, 除, 除到完全没有为止. 这个算法最后的时间是O(lgn). 严格来说,这个算法并不是我的算法的简单翻译;

这个问题的这个算法, 尤其是下面的那个 iterative 的算法, 按理是应该能够想到的, 结果并没有. 只能说还是没有很好的落实先想笨办法的方针. 这个方针不仅是为了让面试官了解你的思考过程, 更重要的是很多时候最优解就是在你写笨办法的时候突然就迸发出来的;

修改了一下我的算法, 最后还是 AC 了, 我原来是少了一个 base case:

if (num == 0) return false;

本来以为这个是没有必要的, 不过仔细想想, 是有必要的. 刚开始我脑子里想的例子全都是1, 2这样的例子, 认为只要%2是0, 那么/2就不可能是0. 但是有一个特例, 就是0自己, 0%2是0, 但是0/2也是0. 所以如果这里没有加0的 base case 就会stack overflow;

当然这个算法最后就可以精简成为一个 oneliner:

public class Solution {  
    public boolean isUgly(int num) {  
        return (num <= 1) ? (num == 1) : (num % 2 == 0 && isUgly(num / 2)) ||  
         (num % 3 == 0 && isUgly(num / 3)) ||  
          (num % 5 == 0 && isUgly(num / 5));  
    }  
}

Problem Description

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.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:39.02%
Contributor: LeetCode
Related Topics
math
Similar Questions
Happy Number Count Primes Ugly Number II