我正在研究 Perfect Squares - LeetCode
- 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是解决这个问题的更快的解决方案。
