# 264. Ugly Number II

<https://leetcode.com/problems/ugly-number-ii/>

## solution

* heap: python小顶堆, 每次pop出来最小的

```python
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        heap = [1]
        start = 1
        s = set()

        for _ in range(n):
            while start in s:
                start = heapq.heappop(heap)
            s.add(start)
            for i in [2, 3, 5]:
                heapq.heappush(heap, i * start)
        return start
```

时间复杂度：O()\
空间复杂度：O()

* 动态规划
  * 从2、3、5三个序列中取最小，像一个三指针
  * 注意重复值，通过三个并列的if，如果if else则会导致重复

```python
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [0] * n
        i2 = i3 = i5 = 0
        res[0] = 1

        for i in range(1, n):
            res[i] = min(res[i2] * 2, res[i3] * 3, res[i5] * 5)

            if res[i] == res[i2] * 2:
                i2 += 1
            if res[i] == res[i3] * 3:
                i3 += 1
            if res[i] == res[i5] * 5:
                i5 += 1
        return res[n-1]
```

## follow up

[263. Ugly Number](https://leetcode.com/problems/ugly-number/)

```python
class Solution:
    def isUgly(self, n: int) -> bool:
        if n == 0:
            return False

        while n % 2 == 0:
            n /= 2
        while n % 3 == 0:
            n /= 3
        while n % 5 == 0:
            n /= 5
        return n == 1
```

时间复杂度：O()\
空间复杂度：O()

[1405. Longest Happy String](https://leetcode.com/problems/longest-happy-string/description/)

* 与[括号生成](https://longxingtan.gitbook.io/mle-interview/01_leetcode/07_dfs/22.-generate-parentheses)都是生成类
* 通过heap来回的pop, push过程中调整结果的一类题目

```python
```
