Ugly Numberシリーズ問題Python解法
1740 ワード
Leetcode 263. Ugly Number
Leetcode 264. Ugly Number II
Leetcode 313. Super 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