Skip to main content
 首页 » 编程设计

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

2024年11月24日9powertoolsteam

我正在研究 Perfect Squares - LeetCode

  1. 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 

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

如何重构那部分?

请您参考如下方法:

我认为 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是解决这个问题的更快的解决方案。