資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝
法律C++ 中的因數二叉樹
假設我們有一個列表，包含大於 1 的正整數。可使用這些整數建立一棵二叉樹，並且每個數字可按需要使用多次。每個非葉節點應為其子節點的乘積。因此，我們要找出可以建立多少棵樹？答案將以模 10^9 + 7 返回。因此，如果輸入類似 [2,4,5,10]，則答案將為 7，因為我們可以建立 7 棵樹，比如 [2]、[4]、[5]、[10]、[4,2,2]、[10,2,5]、[10,5,2]
若要解決這個問題，我們將遵循以下步驟 -
- 定義對映 dp
- 對陣列 A 進行排序，n := 陣列 A 的大小，ret := 0
- 對於 i 從 0 到 n – 1
- 增加 dp[A[i]] 1
- 對於 j 從 0 到 j – 1
- 如果 A[i] 模 A[j] = 0，則
- dp[A[i]] := dp[A[i]] + (dp[A[j]] * dp[A[i]] / dp[A[j]])
- 如果 A[i] 模 A[j] = 0，則
- ret := ret + dp[A[i]]
- 返回 ret
讓我們看看下面的實現，以便更深入地瞭解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
int add(lli a, lli b){
return ((a % MOD) + (b % MOD)) % MOD;
}
int mul(lli a, lli b){
return ((a % MOD) * (b % MOD)) % MOD;
}
class Solution {
public:
int numFactoredBinaryTrees(vector<int>& A) {
unordered_map <int, int> dp;
sort(A.begin(), A.end());
int n = A.size();
int ret = 0;
for(int i = 0; i < n; i++){
dp[A[i]] += 1;
for(int j = 0; j < i; j++){
if(A[i] % A[j] == 0){
dp[A[i]] = add(dp[A[i]], mul(dp[A[j]], dp[A[i] / A[j]]));
}
}
ret = add(ret, dp[A[i]]);
}
return ret;
}
};
main(){
vector<int> v1 = {2,4,5,10};
Solution ob;
cout << (ob.numFactoredBinaryTrees(v1));
}輸入
[2,4,5,10]
輸出
7
更新時間：04-May-2020
172 次瀏覽
廣告