Python directed graph BFS solution


  • 0

    The idea is to generate a directed graph with the root as the target number, the other node as the current values during subtraction and edge has the value of the square number that has been subtracted from the previous node.

    Use a hash table to store the graph.

    Do the BFS starting from the root recording the depth, when the visited node has value 0, return the depth.

    from collections import deque
    import numpy as np
    
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            graph = {}
            for i in range(n,0,-1):
            	sqrts = np.array(range(1, int(np.sqrt(i)) + 1))
            	sqaures = sqrts * sqrts
            	graph[i] = np.array([i] * len(sqaures)) - sqaures
    
            q = deque([(n,0)])
            s = set([n])
            while q:
            	current = q.popleft()
            	num, depth = current
            	if num == 0:
            		return depth
            	for child in graph[num]:
            		if child not in s:
            			q.append((child, depth+1))
            			s.add(child)
    

Log in to reply
 

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