标签: 回溯
难度: Medium
Submission
运行时间: 36 ms
内存: 0.0 MB
import functools
class Solution:
@functools.lru_cache(maxsize=None)
def getFactors(self, n: int) -> List[List[int]]:
if n == 1:
return []
ans = []
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
ans.append([i, n // i])
for f in self.getFactors(n // i):
tmp = sorted([i] + f)
if tmp not in ans:
ans.append(tmp)
return ans
Explain
这个题解使用递归的方式来求解所有可能的因子组合。主要思路如下： 1. 从2开始遍历到sqrt(n)，对于每个数i，如果i能整除n，则将[i, n//i]加入结果。 2. 对于每个满足条件的i，递归调用getFactors(n//i)，获取n//i的所有因子组合，将i加入每个组合的开头，并去重后加入结果。 3. 为了避免重复计算，使用@functools.lru_cache装饰器来缓存递归调用的结果。 4. 当n为1时，返回空列表作为递归的终止条件。
时间复杂度: O(logn)
空间复杂度: O(n)
import functools
class Solution:
@functools.lru_cache(maxsize=None)
def getFactors(self, n: int) -> List[List[int]]:
if n == 1:
return [] # 递归终止条件
ans = []
for i in range(2, int(math.sqrt(n)) + 1): # 遍历从2到sqrt(n)的所有数
if n % i == 0: # 如果i能整除n
ans.append([i, n // i]) # 将[i, n//i]加入结果
for f in self.getFactors(n // i): # 递归调用getFactors(n//i)
tmp = sorted([i] + f) # 将i加入每个组合的开头
if tmp not in ans: # 去重
ans.append(tmp)
return ans
Explore
当寻找一个数n的因子时，如果存在因子i使得i乘以j等于n，则必有一个因子不大于sqrt(n)，另一个因子不小于sqrt(n)。因此，只需遍历到sqrt(n)，对于每个i，可以计算出相应的j（即n/i）。这样可以减少不必要的重复遍历，提高效率。如果遍历到n，会重复计算因子对（i, j）和（j, i），其中i和j大于sqrt(n)。
在递归过程中，为了确保每个因子组合都是唯一的，题解中使用了两种方式：首先，通过将组合排序来保证每个组合内部的因子顺序一致；其次，在添加新的组合到结果列表之前，检查这个组合是否已经存在于结果列表中。具体实现是，通过对每次递归得到的组合添加当前因子i，并排序生成新的组合tmp，然后在添加到最终答案之前，检查tmp是否已经存在于答案列表中，从而避免重复。
`functools.lru_cache`是一个装饰器，用于缓存函数的返回值。当函数使用相同的参数再次被调用时，不需要重新执行函数，而是直接从缓存中获取结果。在递归过程中，尤其是处理具有重复子问题的递归，这可以显著减少计算量，提高性能。LRU（最近最少使用）策略会在缓存满时移除最久未使用的数据，以保持缓存的有效性。在这个题解中，使用lru_cache来存储已经计算过的n的因子组合，避免重复的计算工作。
在因子组合问题中，当n为1时，意味着不能再进行任何因子分解（1不是一个有效的因子）。因此，将n为1作为递归的终止条件，表示当前分支不能再进一步分解，应该停止递归。返回空列表表示这个分支没有找到任何有效的因子组合。这是递归算法设计中的一种常见策略，用于处理基本情况，避免无限递归。