Regarded correct python solution with TLE


  • 0
    S
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 4:
            return n
        if n == 4:
            return 1
        res = dict()
        res[0] = 0
        res[1] = 1
        res[2] = 2
        res[3] = 3
        res[4] = 1
    
        for i in range(5,n+1):
            res[i] = sys.maxint
            j = 1
            while j*j <= i:
                if j*j == i:
                    res[i] = 1
                else:
                    res[i] = min(res[i], 1+res[i-j*j])
                j += 1 
        return res[n]
    

    I think my python solution is correct. And some test cases can be passed through "Custom TestCase", but not through submission. I am really confused....


  • 0
    P

    If using Python, you need to turn the array "res" as static, the code below is for your reference.

    class Solution(object):
    cache = [0] * 10001
    
    for i in range(1, 101):
        cache[i**2] = 1
    
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # DP
        # r = [0] * (n+1)
        # for i in range(1, int(n**0.5)+1):
        #     r[i**2] = 1
    
        for i in range(2, n+1):
            tmp = 10000
            if self.cache[i] != 0:
                continue
            for j in range(1, int(i ** 0.5) + 1) :
                idx = i - j**2
                # print idx, "i", r[idx]
                tmp = tmp if tmp < self.cache[idx] else self.cache[idx]
            self.cache[i] = tmp + 1
        
        return self.cache[n]

  • 0
    S

    I see. Thanks for your help.


Log in to reply
 

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