My Python DP solution beats 97% of Python submissions


  • 0
    S
    class Solution(object):
        def nthUglyNumber(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 0:
                return 0
            
            dpUgly = [None]  * n
            
            dpUgly[0] = 1
            index_2 = 0
            index_3 = 0
            index_5 = 0
            mul_2 = 2
            mul_3 = 3
            mul_5 = 5
            curMin = 1
            for i in xrange(1, n):
                curMin = min(mul_2, min(mul_3, mul_5))
                dpUgly[i] = curMin
                if mul_2 == curMin:
                    index_2 += 1
                    mul_2 = 2 * dpUgly[index_2]
                if mul_3 == curMin:
                    index_3 += 1
                    mul_3 = 3 * dpUgly[index_3]
                if mul_5 == curMin:
                    index_5 += 1
                    mul_5 = 5 * dpUgly[index_5]
            return dpUgly[n-1]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.