Python BFS


  • 0
    T

    Given n, graph will have node from n to 0. For example, if n ==4, then graph includes nodes{4,3,2,1, 0}. Each time we check current node's neighbors by looping edge_length from floort(sqrt(n)) to 1

    import math
    from collections import deque
    class Solution(object):
    def numSquares(self, n):
    """
    :type n: int
    :rtype: int
    """
    longest_edge = int(math.floor(math.sqrt(n)))
    Q = deque([(n, 0)])
    visited = set()
    while Q:
    cur, path = Q.popleft()
    for x in range(longest_edge, 0, -1):
    neighbor = cur - x**2
    if neighbor == 0:
    return path + 1
    elif neighbor > 0 and neighbor not in visited:
    Q.append((neighbor, path + 1))
    visited.add(neighbor)
    return -1


Log in to reply
 

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