🟡 剑指 Offer 49. 丑数

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解 1_抄的妙方法.py

# https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/class Solution:    def nthUglyNumber(self, n: int) -> int:        dp = [1 for _ in range(n)]        # a表示idx=a之前的数都已经乘过2加到队列里了        a, b, c = 0, 0, 0                for idx in range(1, n):            dp[idx] = min(dp[a]*2, dp[b]*3, dp[c]*5)            if dp[idx] == dp[a]*2: a += 1            if dp[idx] == dp[b]*3: b += 1            if dp[idx] == dp[c]*5: c += 1        return dp[-1]

题解 2_抄的土方法.py

from heapq import *
class Solution:    def nthUglyNumber(self, n: int) -> int:        heap = [1]        seen = {1}        factors = [2, 3, 5]
        for _ in range(n-1):            curMin = heappop(heap)            for fac in factors:                newseen = fac * curMin                if newseen not in seen:                    seen.add(newseen)                    heappush(heap, newseen)                return heappop(heap)