python - 寻找最不完美二乘的 BFS 解决方案

Question

我正在研究一个完美的正方形 - LeetCode

279. 完美的正方形

给定一个正整数n1, 4, 9, 16, ... ，找出总和为n的最小完美平方数（例如） 。

示例 1：

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

示例 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

运行时间：2532 毫秒，比 Perfect Squares 的 Python3 在线提交的 40.71% 快。内存使用：14 MB，不到 Perfect Squares 的 Python3 在线提交的 18.25%。

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

                #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

它有效，但超过了时间限制。

如何重构那部分？

标签： python

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是解决此问题的更快解决方案。