leetcode
leetcode 201 ~ 250
因子的组合

因子的组合

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 0.0 MB


import java.util.*;
import java.util.stream.*;
 
public class Solution {
    /**
     * This method finds all factor combinations of a given number using Java Streams.
     * 
     * @param n the target number
     * @return a list of lists containing factor combinations
     */
    public List<List<Integer>> getFactors(int n) {
        return IntStream.rangeClosed(2, n)
                        .filter(i -> n % i == 0)
                        .boxed()
                        .flatMap(i -> getFactors(n / i).stream()
                        .filter(list -> list.isEmpty() || i <= list.get(0))
                        .map(list -> {
                            List<Integer> newList = new ArrayList<>(list);
                            newList.add(0, i);
                            return newList;
                        }))
                        .collect(Collectors.toList());
    }
 
    /**
     * Overloaded method to include a default start factor.
     * 
     * @param n the target number
     * @param start the starting factor
     * @return a list of lists containing factor combinations
     */
    private List<List<Integer>> getFactors(int n, int start) {
        if (n <= 1) return Arrays.asList(Collections.emptyList());
        return IntStream.rangeClosed(start, n)
                        .filter(i -> n % i == 0)
                        .boxed()
                        .flatMap(i -> getFactors(n / i, i).stream()
                        .filter(list -> list.isEmpty() || i <= list.get(0))
                        .map(list -> {
                            List<Integer> newList = new ArrayList<>(list);
                            newList.add(0, i);
                            return newList;
                        }))
                        .collect(Collectors.toList());
    }
}
 

解释

方法:

这个题解使用递归的方式来求解所有可能的因子组合。主要思路如下: 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)

代码细节讲解

🦆
为什么在求解因子组合时,只需要遍历到sqrt(n)而不是n?
当寻找一个数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`,能否解释这个装饰器如何优化递归调用的性能?
`functools.lru_cache`是一个装饰器,用于缓存函数的返回值。当函数使用相同的参数再次被调用时,不需要重新执行函数,而是直接从缓存中获取结果。在递归过程中,尤其是处理具有重复子问题的递归,这可以显著减少计算量,提高性能。LRU(最近最少使用)策略会在缓存满时移除最久未使用的数据,以保持缓存的有效性。在这个题解中,使用lru_cache来存储已经计算过的n的因子组合,避免重复的计算工作。
🦆
递归终止条件是当n为1时返回空列表,为什么选择这个条件作为递归终止?
在因子组合问题中,当n为1时,意味着不能再进行任何因子分解(1不是一个有效的因子)。因此,将n为1作为递归的终止条件,表示当前分支不能再进一步分解,应该停止递归。返回空列表表示这个分支没有找到任何有效的因子组合。这是递归算法设计中的一种常见策略,用于处理基本情况,避免无限递归。

相关问题

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

 

示例 1:

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

 

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40