264. Ugly Number II

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

solution

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

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则会导致重复

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

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

• 与括号生成都是生成类

• 通过heap来回的pop, push过程中调整结果的一类题目