呓语Beta 2.0 首页 镜头后 灶台前 捐赠者名单 有趣的小站

leetcode 264 Ugly Number II

文档信息

leetcode 264 Ugly Number II

解法一 TLE

class Solution(object):
    def nthUglyNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    arr = [False, True, True, True, True, True]
                                   
    if n < 6:
        return n
                                                
    n -= 5
    p = 6
    while (1):
        if p % 2 == 0:
            arr.append(arr[p / 2])
        elif p % 3 == 0:
            arr.append(arr[p / 3])
        elif p % 5 == 0:
            arr.append(arr[p / 5])
        else:
            arr.append(False)

        if arr[p] == True:
            n -= 1

        if n == 0: 
            return p

        p += 1

note

解法二

class Solution(object):
    def nthUglyNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    ugly = [1]
    i2, i3, i5 = 0, 0, 0
    while n > 1:
        u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5] # 不断构造新数字
        umin = min((u2, u3, u5)) # 选择构造出来最小的数字
        if umin == u2:
            i2 += 1
        if umin == u3:
            i3 += 1
        if umin == u5:
            i5 += 1
        ugly.append(umin)
        n -= 1
    return ugly[-1]

note

付费支持

由于本网站没有广告和任何形式的收入来源,希望获得您的资助。每篇技术性文章和每期shellcasts视频定价人民币1元,在您付费后可以任意观看和下载。

可以使用支付宝手机钱包扫描下方的二维码进行付款操作或者用支付宝转帐给richard.ma.19850509@gmail.com,谢谢!

Fork me on GitHub