Ugly number II python

https://leetcode.com/problems/ugly-number-ii/

The idea is to keep three pointers, each pointer points to a position in the stack
each number in the stack will be multiplied by 2,3,5

class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
d = {}
stack = [1]
p1,p2,p3 = 0,0,0
i = 1
ret = 1
while i<n:
u2,u3,u5 = [stack[p1]*2,stack[p2]*3,stack[p3]*5]
cmin = min(u2,u3,u5)
if cmin == u2:
p1 +=1
if cmin == u3:
p2+=1
if cmin == u5:
p3+=1
i+=1
stack.append(cmin)
return stack[-1]

The same solution can be used for super ugly number

def nthSuperUglyNumber(self, n, primes):
stack = [1]
l = len(primes)
assert(l!=0)
pointers = l*[0]
while n>1:
minnum = stack[pointers[0]]*primes[0]
for i,p in enumerate(pointers):
minnum = min(stack[p]*primes[i],minnum)
for i,p in enumerate(pointers):
if minnum == stack[p]*primes[i]:
pointers[i] +=1
stack.append(minnum)
n-=1
return stack[-1]

评论

此博客中的热门博文

Embedded System interview Question

MicroKernel & Exokernel 操作系统未来可能的发展

中国城市房地产分析