LeetCode 264. Ugly Number II

Posted on | In |
Words count in article: 141 | Reading time ≈ 1

题目

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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

1
2
3
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

  • 1 is typically treated as an ugly number.
  • n does not exceed 1690.

思路

DP.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            return 0
        dp = [1] * n
        L1, L2, L3 = 0, 0, 0
        for i in range(1, n):
            dp[i] = min(dp[L1]*2, dp[L2]*3, dp[L3]*5)
            if dp[i] == dp[L1]*2:
                L1 += 1
            if dp[i] == dp[L2]*3:
                L2 += 1
            if dp[i] == dp[L3]*5:
                L3 += 1
        return dp[n-1]