Skip to content

264 ugly number ii

264. Ugly Number II

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

难度: Medium

思路:

暴力算法一定会超时

先看一个非常🐂的帖子,当我知道python 除了有list之外还有collections就已经被刷新了一次了,然后数据结构 x 数据结构,就展示了数据结构的魅力

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

看一下deque + rotate:

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 -是往左边rotate,看官网的介绍.

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()).

所以这样造成可以🐂的数据结构

用这个微调之后的fasttable来解决问题

import collections
import bisect

class FastTable:

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

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

    def head(self):
        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:
            x = q.head()
            q.insert(2*x)
            q.insert(3*x)
            q.insert(5*x)
            n -= 1
        return x

还可以优化: 根据页面hint 来做的

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


回到顶部