Python Accepted Solution


  • 13
    D

    I've seen that the dp solution is not accepted in Python. Some use static dp in order to use it. And we can also solve it using number theory knowledge. But what if in a competition we don't know that theory? What if we are not allowed to use static dp? Here is an accepted solution using BFS:

    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
           
            q1 = [0]
            q2 = []
            level = 0
            visited = [False] * (n+1)
            while True:
                level += 1
                for v in q1:
                    i = 0
                    while True:
                        i += 1
                        t = v + i * i
                        if t == n: return level
                        if t > n: break
                        if visited[t]: continue
                        q2.append(t)
                        visited[t] = True
                q1 = q2
                q2 = []
                    
            return 0

  • 1

    Very nice, finally someone did it :-)

    You inspired me to write one as well, it's simpler but takes almost twice as much time as yours (688 ms yours, 1295 ms mine (average of three submissions)).

    def numSquares(self, n):
        sums = {0}
        while n not in sums:
            sums = {sum + i*i
                    for sum in sums
                    for i in xrange(1, int((n - sum)**0.5 + 1))}
        return min(sums)
    

  • 0
    A

    Hi, can you explain this algorithm? I have no idea..


  • 1
    D

    As I wrote, the algorithm is Breadth First Search (BFS). Imagine that you have a graph where vertices are numbers from 0 to n. 2 vertices are connected dirrectly if their values are different by a square number. for example: 1 and 2 connected, 2 and 3 connected, 2 and 6 connected, 2 and 11 connected, 1 and 5 connected, 1 and 10 connected, etc.

    So starting from vertex 0, you look for the vertex n by BFS. The distance is exactly what we need to return.


  • 1
    Y

    My code, improved the readability, runtime: 484 ms

    class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        edges = [i*i for i in range(1, int(n**0.5)+1)]
        visited = [False] * (n+1)
        level = 0
        children = [0]
        while True:
            level += 1
            parents = children
            children = []
            for parent in parents:
                for edge in edges:
                    child = parent + edge
                    if child == n:
                        return level
                    if child > n:
                        break
                    if visited[child]:
                        continue
                    visited[child] = True
                    children.append(child)
    

    And here is a improved version, saving the edge between the node and parent, only use edges which are equal or bigger than the saved edge when calculating children, runtime: 420 ms

    class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        edges = [i*i for i in range(1, int(n**0.5)+1)]
        edgesCount = len(edges)
        visited = [False] * (n+1)
        level = 0
        children = {0:0}
        while True:
            level += 1
            parents = children
            children = {}
            for parentV in parents:
                startIndex = parents[parentV]
                for edgeIndex in range(startIndex, edgesCount):
                    childV = parentV + edges[edgeIndex]
                    if childV == n:
                        return level
                    if childV > n:
                        break
                    if visited[childV]:
                        continue
                    visited[childV] = True
                    child = {childV:edgeIndex}
                    children.update(child)

  • 0
    D

    Inspired by u, I made some changes and the run time is improved to ~330 ms.

    Consider it as a shortest path problem . See my explanation in the code.

    The main performance improvement comes from using non-decreasing sequence of square numbers.
    e.g., when checking 13, for the two possible sequences (4, 9) and (9, 4) only the former is checked.

    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            distance, q1, q2, label = 1, [(0, 1)], [], [10] * (n + 1)
            '''
            Shortest Path
            Imagine a graph whose vertices are numbers from 0 to n. The lengths of all edges are 1.
            Two vertices differ by any perfect square numbers are connected.
            Starting from vertex 0, the shortest path to reach vertex n is the answer.
            Since the length of all edges are the same, we can use a queue instead of heap to store
            the vertices to be explored in each step.
            Another improvement is that we only check non-decreasing sequence of square numbers, e.g.:
            13 --> (4, 9), not (9, 4)
            '''
            while True:
                for node, length in q1:
                    # non-decreasing sequence only
                    for edge in xrange(length, n+1):
                        next_node = node + edge*edge
                        if next_node == n:
                            return distance
                        elif next_node > n:
                            break
                        elif label[next_node] > distance:
                            label[next_node] = distance
                            # add node and the edge used last
                            q2.append((next_node, edge))
                q1, q2 = q2, []
                distance += 1
    

  • 0
    G

    nice code.
    is it slow because set runs slow than using the list visited ?


  • 0

    I guess that plays a role, yes, but also the xrange and the **0.5. Don't know what has the biggest impact.


Log in to reply
 

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