数据结构
网络
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 次浏览
广告