Leetcpde -- 263.264 Ugly Number(Recur) + II(DP)

263.264 Ugly Number + II
easy/medium

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

263 I. only need to decide if ugly number, return true/false.
思路： keep mod and divide 2,3,5 till base case.

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

264 II.
思路1： use dp[n] to track next ugly number

public class Solution {
    public int nthUglyNumber(int n) {
        int i1 = 0, i2 = 0, i3 = 0;
        int num1 = 2,num2 = 3,num3 = 5;//ugly number: 1,2,3,5,
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = Math.min(num1, Math.min(num2, num3));
            if(dp[i] == num1){
                i1++;
                num1 = 2*dp[i1];
            }
            if(dp[i] == num2){
                i2++;
                num2 = 3*dp[i2];
            }
            if(dp[i] == num3){
                i3++;
                num3 = 5*dp[i3];
            }
        }
        return dp[n-1];
    }
}

思路2： use heap to return the min, keep adding min*2, min*3, min*5 and minus n, till n == 0
slow

ublic class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        long res = 0;
        heap.add((long)1);
        while(!heap.isEmpty() && n > 0){
            while(res == heap.peek()){
                heap.poll();
                continue;
            }
            res = heap.poll();
            heap.add(res * 2);
            heap.add(res * 3);
            heap.add(res * 5);
            n--;
        }
        return (int)res;
    }
}