Ugly-Number-series

前言

本章分为两个部分:

1. 如何判断一个数是不是丑数

2. 如何求第n个丑数

丑数-I

0x0 题目详情

测试用例:

0x1 解题思路

0x2 代码实现

0x3 课后总结

丑数-II

0x0 题目详情

编写一个程序，找出第 n 个丑数。 丑数就是质因数只包含 2, 3, 5 的正整数。

测试用例:

示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明: 1 是丑数。 n 不超过1690。

0x1 解题思路

这道题有两个思路,分别为动态规划和使用小根堆。

小根堆:

我们可以从第一个丑数开始,将最小的丑数分别乘以2、3或者5。这样新求出3个丑数入堆。然后再从堆中选择一个最小继续重复乘以2、3、5的操作。直到重读这个操作n次。

使用小根堆的原因是因为它能够帮助对求出的丑数进行排序,从而总是能够选出最小的丑数。但是新求的丑数有可能重复。例如丑数6,可以通过2X3得到,也可以通过3X2得到。这都是有可能发生的,所以从堆中弹出最小的丑数x后,要看看新的栈顶是否与x相同,如果相同,则需要将新的丑数弹出直至二者不等。

动态规划

小根堆是将丑数插入到结果集后再排序,而动态规划的方法时在在求出三个新丑数后,我们自己排序找到最小的丑数后插入结果集中。

我们可以声明一个一维dp数组,dp[i]表示第i个丑数。并且我们需要维护三个指针,p2、p3、p5。分别表示指向需要乘2的丑数,需要乘3的丑数,需要乘5的丑数。而指针的移动规则就有点巧妙了:如果新求出的丑数是通过p2指针指向的丑数求出来的,那么就将p2++,如果新求出的丑数是通过p3指针指向的丑数求出的,那么就将p3++。p5移动的规则类似。这是为什么呢?这里举个例子:

刚开始,我们只有一个丑数,p2=0,p3=0,p5=0,都指向1这丑数。那么新求的最小丑数dp[1]=Math.min(dp[p2]*2,dp[p3]*3,dp[p5]*5)=2。那么我们就将p2++。因为这表示1这个丑数再也不参与求新丑数的操作了,就将p2++。然后可以参与求新丑数的丑数包括1、2。那么我们就需要对这两个数分别乘以2、3、5从而才能决定最小的丑数到底是谁。

但是,2*3>1*3的,2*5>1*5。所以对于2这个丑数,它根本不用乘以3或者5,因为这些工作都由前面的丑数做了。

0x2 代码实现

class Solution {
    public int nthUglyNumber(int n) {
        if(n<0){
            return 0;
        }
        int[] dp=new int[n];
        dp[0]=1;
        int p2=0;
        int p3=0;
        int p5=0;
        for(int i=1;i<n;i++){
            dp[i]=Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5));
            //这三个if需要并且的原因是如果当前的丑数序列是1、2、3、4、5,p2指向3,p3指向2,p5指向2
            //如果三个if不是并列的,下一个丑数=min(dp[p2]*2=3*2=6,dp[p3]*3=6,dp[p5]*5=10)=6
            //注意如果不是并列的,那么只会移动p2,这是p3仍然指向2
            //下一轮,dp[p2]*2=4*2=8,dp[p3]*3=2*3,dp[p5]*5=2*5=10,这里又求出来一个6,重复了,而且竟然还会被认为是有效的添加至
            //dp数组中
            if(dp[i]==dp[p2]*2){
                p2++;
            }
            //不是并且的就是指这里采用else if
            if(dp[i]==dp[p3]*3){
                p3++;
            }
            //不是并且的就是指这里采用else
            if(dp[i]==dp[p5]*5){
                p5++;
            }
        }
        return dp[n-1];
    }
}

0x3 课后总结

这动态规划的做法,这...没做过谁想得到啊！