因子的组合
难度:
标签:
题目描述
代码结果
运行时间: 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?
▷🦆
在递归过程中,如何确保每个因子组合都是唯一的?具体是如何实现去重的?
▷🦆
你的题解中提到使用了`functools.lru_cache`,能否解释这个装饰器如何优化递归调用的性能?
▷🦆
递归终止条件是当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