資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告