Python common BFS with fewer lines


  • 3
    T

    Inspired by this

    def numSquares(self, n):
        queue = collections.deque([(0, 0)])
        visited = set()
        while queue:
            i, step = queue.popleft()
            step += 1
            for j in xrange(1, n + 1):
                k = i + j * j
                if k > n:
                    break
                if k == n:
                    return step
                if k not in visited:
                    visited.add(k)
                    queue.append((k, step))

  • 0
    C

    Hi tusizi, why I rewrite your code a little bit as follow, it got TLE, could you help me to figure out the bottleneck here? I think the time complexity should be the same as your code. Thanks.

    def numSquares(self, n):
        queue = collections.deque([(0, 0)])
        visited = set()
        while queue:
            val, dis = queue.popleft()
            if val == n:
                return dis
            for i in xrange(1, n+1):
                j = val + i*i
                if j > n:
                    break
                if j not in visited:
                    visited.add(j)
                    queue.append((j, dis+1))

  • 0
    W

    @caikehe Your code need to clculate the whole level values ( "val +i*i") before you actually check whether get "n", more redundancy.

    def numSquares(self, n):
        queue = collections.deque([(0, 0)])
        visited = set()
        while queue:
            val, dis = queue.popleft()
            # if val == n:
            #     return dis
            for i in xrange(1, n+1):
                j = val + i*i
                if j > n:
                    break
                if j == n:
                    return dis+1
                if j not in visited:
                    visited.add(j)
                    queue.append((j, dis+1))

Log in to reply
 

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