数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 中的因子组合
假设我们有一个数字。这个数字可以看作其因子的乘积。例如，8 = 2 x 2 x 2; = 2 x 4。我们需要编写一个函数，接收一个整数 n 并返回其所有可能的因子组合。
因此，如果输入是 12，则输出将是 [[2, 6], [2, 2, 3], [3, 4]]
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 solve()，它将接收 n、target 和 start。
定义一个名为 ret 的二维列表。
如果 n 等于 1，则：
返回 ret。
如果 n 不等于 target，则：
将 n 添加到 ret 的末尾。
对于 i 从 start 开始，当 i * i <= n 时，递增 i，执行以下操作：
如果 n mod i 等于 0，则：
other = solve(n / i, target, i)
对于 j 从 0 开始，当 j < other 的大小，递增 j，执行以下操作：
将 i 添加到 other[j] 的末尾。
将 other[j] 添加到 ret 的末尾。
返回 ret。
在主方法中执行以下操作：
返回 solve(n, n, 2)
示例
让我们来看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto< > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int< > solve(int n, int target, int start){
vector < vector <int< > ret;
if(n == 1){
return ret;
}
if(n != target){
ret.push_back({n});
}
for(int i = start; i * i <= n; i++){
if(n % i == 0){
vector < vector <int< > other = solve(n / i, target,i);
for(int j = 0; j < other.size(); j++){
other[j].push_back(i);
ret.push_back(other[j]);
}
}
}
return ret;
}
vector<vector<int<> getFactors(int n) {
return solve(n, n, 2);
}
};
main(){
Solution ob;
print_vector(ob.getFactors(16));
}输入
16
输出
[[8, 2, ],[4, 2, 2, ],[2, 2, 2, 2, ],[4, 4, ],]
更新于：2020-11-18
229 次浏览
广告