# 264 ugly number ii

### 264. Ugly Number II

http://stackoverflow.com/questions/4098179/anyone-know-this-python-data-structure

import collections
a = collections.deque()
a.append(2)
a.append(5)
a.append(7)
a.append(9)  #a  deque([2, 5, 7, 9])

import bisect
idx = bisect.bisect_left(a,3) #1
a.rotate(-idx) #deque([5, 7, 9, 2])

a.appendleft(3) #deque([3, 5, 7, 9, 2])

a.rotate(idx) # deque([2, 3, 5, 7, 9])


Rotate the deque n steps to the right. If n is negative, rotate to the left. Rotating one step to the right is equivalent to: d.appendleft(d.pop()).

import collections
import bisect

class FastTable:

def __init__(self):
self.__deque = collections.deque()

def __len__(self):
return len(self.__deque)

return self.__deque.popleft()

def tail(self):
return self.__deque.pop()

def peek(self):
return self.__deque[-1]

def insert(self, obj):
if obj in self.__deque:
return
index = bisect.bisect_left(self.__deque, obj)
self.__deque.rotate(-index)
self.__deque.appendleft(obj)
self.__deque.rotate(index)

class Solution(object):

def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
q = FastTable()
q.insert(1)
while n > 0:
q.insert(2*x)
q.insert(3*x)
q.insert(5*x)
n -= 1
return x


class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
else:
import collections
q2 = collections.deque()
q3 = collections.deque()
q5 = collections.deque()
q2.append(2)
q3.append(3)
q5.append(5)
while n > 1:
x = min(q2[0],q3[0],q5[0])
if x == q2[0]:
x = q2.popleft()
q2.append(2*x)
q3.append(3*x)
q5.append(5*x)
elif x == q3[0]:
x = q3.popleft()
q3.append(3*x)
q5.append(5*x)
else:
x = q5.popleft()
q5.append(5*x)
n -= 1
return x


apachecn/AiLearning