python - BFS 解决方案找到最不完美的正方形

Question

我正在研究 Perfect Squares - LeetCode

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

关键思想将其转换为在图中查找从 n 到 0 的最短路径

标准的 DFS 解决方案

class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        from collections import deque 
        #declare
        queue = deque()
        visited = set()
        #intitiate 
        step = -1
        queue.append(n)
        visited.add(n)

        while queue:
            step += 1
            size = len(queue)  

            for _ in range(size):
                cur = queue.popleft()
                if cur == 0: return step  #terminating checking 

                #strech to collect next nodes 
                i = 1
                next_ = cur - i**2 #
                while next_ >= 0:
                    if next_ not in visited:
                        queue.append(next_)
                        visited.add(next_)

                    i += 1
                    next_  = cur - i**2

Runtime: 2532 ms, faster than 40.71% of Python3 online submissions for Perfect Squares. Memory Usage: 14 MB, less than 18.25% of Python3 online submissions for Perfect Squares.

收集下一个节点的部分不是很简洁

                #strech to collect next nodes 
                i = 1
                next_ = cur - i**2 #
                while next_ >= 0:
                    if next_ not in visited:
                        queue.append(next_)
                        visited.add(next_)

                    i += 1
                    next_  = cur - i**2

试图将其修改为

            i = 1                  
            while  cur - i** 2 >= 0:
                next_ = cur - i ** 2:
                if next_ not in visited:
                    queue.append(next_)
                    visited.add(next_)
                i += 1

成功了，但超过了时间限制。

如何重构那部分？

Answer 1

我认为 TLE 的原因是你执行 cur - i** 2 两次，square 在这里很昂贵。我改成 cur - i * i，它通过了。

在大多数情况下，双重计算不会导致TLE，但是这里的DFS已经足够慢了(在我的测试中消耗了2560ms)，所以它在乎。

如果不想对next_赋值两次，而python比较不支持语法赋值，像这样:

while (next_ = cur - i**2) >= 0:

所以你可以试试这个(我认为这也很丑):

i = 1
while True:
    next_ = cur - i ** 2
    if next_ < 0:
        break

    if next_ not in visited:
        queue.append(next_)
        visited.add(next_)
    i += 1

顺便说一句，我只是注意到它与BFS无关，而BFS是解决这个问题的更快的解决方案。