leetcode题解-264-丑数Ⅱ

发表于 | 更新于 | 分类于

题目

  1. 用STL实现小根堆

按理说应该实现些其它功能，比如：

  • vecotor中是否包含multiple elements
  • 堆的一些常用功能，如：heapify
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
class Solution {
public:
    int nthUglyNumber(long n) {
        vector<long> vi = {1};

        make_heap(vi.begin(), vi.end(), greater<>());
        long top;
        for (long i = 0; i < n; ++i)
        {
            pop_heap(vi.begin(), vi.end(), greater<>());
            
            top = vi.back();
            vi.pop_back();

            if (find(vi.begin(), vi.end(), top*2) == vi.end())
            {
                vi.push_back(top*2);
            }
            if (find(vi.begin(), vi.end(), top*3) == vi.end())
            {
                vi.push_back(top*3);
            }
            if (find(vi.begin(), vi.end(), top*5) == vi.end())
            {
                vi.push_back(top*5);
            }

            make_heap(vi.begin(), vi.end(), greater<>());
        }

        return top;
    }
};

实际上效率低了，因为用原生的make_heap需要重新构造一次堆，但是用heapify这种调整堆结构会快很多。

  1. DP实现

状态转移方程： \[ dp[i] = min(2*dp[l_2], 3*dp[l_3], 5*dp[l_5]) \]

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
class Solution {
public:
    int nthUglyNumber(long n) {
        vector<long> dp(n+1);

        dp[1] = 1;
        long l2 = 1, l3 = 1, l5 = 1;

        for (long i = 2; i <= n; ++i)
        {
            dp[i] = min(2*dp[l2], min(3*dp[l3], 5*dp[l5]));

            if (dp[i] >= 2*dp[l2])
            {
                l2 += 1;
            }
            if (dp[i] >= 3*dp[l3])
            {
                l3 += 1;
            }
            if (dp[i] >= 5*dp[l5])
            {
                l5 += 1;
            }
        }

        return dp[n];
    }
};

Reference

powcai解