剑指 Offer 49. 丑数

in with 0 comment

剑指 Offer 49. 丑数

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

示例:

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

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

解题思路

  1. 动态规划,状态转移方程:
    1. dp[a - 1] * 2 > dp[i - 1] >= dp[a - 2] * 2
    2. dp[b - 1] * 3 > dp[i - 1] >= dp[b - 2] * 3
    3. dp[c - 1] * 5 > dp[i - 1] >= dp[c - 2] * 5
    4. dp[i] = min(dp[a- 1], min(dp(b- 1), dp(c - 1)))
    5. 初始化第一个丑数,dp[0] = 1
    6. 返回 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;
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(n2, Math.min(n3, n5));
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }
        return dp[n -1];
    }
}