Cant get over TLE python?


  • 0
    H
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            cnt=[n+1]*(n+1)
            sqs=set()
            i=1
            while i*i<=n:
                sqs.add(i*i)
                i+=1
            sqso=sorted(sqs)
            ind=0 #my_xrange(0)
            sqsosub=[]
            for i in xrange(1,n+1):
                if i in sqs:
                    cnt[i]=1
                    ind+=1
                    sqsosub.append(sqso.pop(0))
                else:
                    for j in sqsosub:
                            cnt[i]=min(cnt[i],cnt[i-j]+1)
            return cnt[n]

Log in to reply
 

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