剑指Offer-面试题49-丑数

2020-05-01

题目描述

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第n个丑数。

示例：

1
2
3

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

说明

1是丑数
n不超过1690

思路

状态定义：
- 设动态规划列表dp，dp[i]代表第 i+1 个丑数。
转移方程：
- 当索引a，b，c满足一下条件时，dp[i]为三种情况的最小值。
- 每轮计算dp[i]后，需要更新索引a，b，c的值，使其始终满足方程条件，以便下轮计算。实现方法：分别独立判断。
- dp[a]*2 > dp[i-1] >= dp[a-1]*2
- dp[b]*3 > dp[i-1] >= dp[b-1]*3
- dp[c]*5 > dp[i-1] >= dp[c-1]*5
dp[i] = min(dp[a]*2,dp[b]*3,dp[c]*5)
初始状态；
- dp[0]=1，即第一个丑数为1。
返回值：
- dp[n-1]，即返回第n个丑数。

代码

class Solution{
    public int nthUglyNumber(int n){
        int[] dp = new int[n];
        dp[0] = 1;
        int a = 0,b = 0, c =0;  //设置三个索引
        int n2 = 0,n3 = 0,n5 = 0;   //分别代表dp[a/b/c] * 2/3/5
        for(int i=1;i<n;i++){
            n2 = dp[a] * 2;
            n3 = dp[b] * 3;
            n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2,n3),n5);   //找到其中的最小值
            if(dp[i] == n2){    //索引++
                a++;
            }
            if(dp[i] == n3){
                b++;
            }
            if(dp[i] == n5){
                c++;
            }
        }
        return dp[n - 1];
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。