Ugly Numberシリーズ問題Python解法

1740 ワード

Leetcode 263. Ugly Number
class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        for i in [2,3,5]:
            while num % i == 0:
                num = num / i
        if num == 1:
            return True
        else:
            return False

Leetcode  264. Ugly Number II
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0
        if n == 1:
            return 1
        numbers = [1]
        i2, i3, i5 = 0, 0, 0
        for k in range(n-1):
            n2, n3, n5 = numbers[i2] * 2, numbers[i3] * 3, numbers[i5] * 5
            Min = min(n2, n3, n5)
            numbers.append(Min)
            i2 += (Min == n2)
            i3 += (Min == n3)
            i5 += (Min == n5)
        return Min

Leetcode 313. Super Ugly Number
class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        if n <= 0 or not primes:
            return 0
        if n == 1:
            return 1
        numbers = [1]
        k = len(primes)
        index = [0] * k
        m = [0] * k
        for nn in range(n-1):
            for kk in range(k):
                m[kk] = numbers[index[kk]] * primes[kk]
            Min = min(m)
            numbers.append(Min)
            for kk in range(k):
                index[kk] += (m[kk] == Min)
        return Min