HELP!!! TLE, python


  • 0
    F
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            maxValue=2**31-1
            ref=[maxValue]*(n+1)
            ref[0]=0
            for i in range(1, n+1):
                if math.sqrt(i)==int(math.sqrt(i)):
                    ref[i]=1
                else:
                    j=1
                    while j**2 < i:
                        ref[i]=min(ref[i], ref[i-j**2]+1)
                        j+=1
            return ref[-1]

  • 0
    S

    I got the same problem. After testing a 40K number, the python needs 2.2s. This is indeed slow.
    I guess this is because every variable in python is an object, and the time and space efficiency of doing this is not high.


  • 0
    A

    Yes, It happens the same here. The same code in C++ is accepted but not in Python :(


Log in to reply
 

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