264. 丑数 II

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

示例:

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

1 是丑数。
n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

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

代码：

from leetcode_python.utils import *
import sys
import numpy as np


# 错误c++代码
"""
class Solution {
public:
    int nthSuperUglyNumber(int n, vector& primes) {
        vector dp(n + 1);
        dp[1] = 1;
        int m = primes.size();
        vector pointers(m, 1);
        for (int i = 2; i <= n; i++) {
            vector nums(m);
            int minNum = INT_MAX;
            for (int j = 0; j < m; j++) {
                nums[j] = dp[pointers[j]] * primes[j];
                minNum = min(minNum, nums[j]);
            }
            dp[i] = minNum;
            for (int j = 0; j < m; j++) {
                if (minNum == nums[j]) {
                    pointers[j]++;
                }
            }
        }
        return dp[n];
    }
};
"""

class Solution:
    def __init__(self):
        pass

    def nthUglyNumber(self, n: int) -> int:
        if n==0:return 1
        dp = [0] * (n + 1)
        dp[1] = 1
        p2 = p3 = p5 = 1
        for i in range(2, n + 1):
            min_p2, min_p3, min_p5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(min_p2, min_p3, min_p5)
            if dp[i] == min_p2:p2 += 1
            if dp[i] == min_p3:p3 += 1
            if dp[i] == min_p5:p5 += 1
        return dp[n]


    def nthUglyNumber_wrong(self, n: int) -> int:
        import numpy as np
        uglys=[2,3,5]
        points = [0,0,0]
        while n:
            find_min = {}
            ugly = np.prod([u ** p for u, p in zip(uglys, points)])
            for i in range(3):
                find_min[ugly*uglys[i]]=i
            points[find_min[min(find_min.keys())]]+=1
            print(n,points,find_min,min(find_min.keys()))
            n-=1
        return np.prod([u ** p for u, p in zip(uglys, points)])




    def nthUglyNumber_318(self, n: int) -> int:
        primes=[2,3,5]
        dp = [None for _ in range(n+1)]     # 丑数序列
        dp[1] = 1                             # 第一个是1
        nums = [None,None,None]
        pointers = [1,1,1]   # 指向该做乘积的那个丑数
        for i in range(2,n+1):
            min_newUgly = sys.maxsize
            for j in range(3):
                nums[j] = dp[pointers[j]]*primes[j]
                min_newUgly = min(min_newUgly,nums[j])
            dp[i] = min_newUgly
            for j in range(3):
                if min_newUgly==nums[j]:
                    pointers[j]+=1
        return dp[n]

def test(data_test):
    s = Solution()
    return s.nthUglyNumber(*data_test)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [1],
        [5],
        [10],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{time.time() - t0}s')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

备注：
GitHub：https://github.com/monijuan/leetcode_python

CSDN汇总：模拟卷Leetcode 题解汇总_卷子的博客-CSDN博客

可以加QQ群交流：1092754609

leetcode_python.utils详见汇总页说明
先刷的题，之后用脚本生成的blog，如果有错请留言，我看到了会修改的！谢谢！