呓语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

捐赠支持

可以使用支付宝转帐给richard.ma.19850509#gmail.com(请将#替换为@),谢谢!

Fork me on GitHub