题目描述
给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。
示例 1:
输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]
示例 2:
输入: arr = [2, 4, 5, 10]
输出: 7
解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
提示：
1 <= arr.length <= 10002 <= arr[i] <= 109arr 中的所有值 互不相同
解法
方法一：动态规划
我们可以枚举 $arr$ 中的每一个数 $a$ 作为二叉树的根节点（根节点一定最大），然后枚举枚举左子树的值 $b$，若 $a$ 能被 $b$ 整除，则右子树的值为 $a / b$，若 $a / b$ 也在 $arr$ 中，则可以构成一棵二叉树。此时，以 $a$ 为根节点的二叉树的个数为 $f(a) = f(b) \times f(a / b)$，其中 $f(b)$ 和 $f(a / b)$ 分别为左子树和右子树的二叉树个数。
因此，我们先将 $arr$ 排序，然后用 $f[i]$ 表示以 $arr[i]$ 为根节点的二叉树的个数，最终答案即为 $f[0] + f[1] + \cdots + f[n - 1]$。注意答案可能很大，需要对 $10^9 + 7$ 取模。
时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。其中 $n$ 为 $arr$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
mod = 10**9 + 7
n = len(arr)
arr.sort()
idx = {v: i for i, v in enumerate(arr)}
f = [1] * n
for i, a in enumerate(arr):
for j in range(i):
b = arr[j]
if a % b == 0 and (c := (a // b)) in idx:
f[i] = (f[i] + f[j] * f[idx[c]]) % mod
return sum(f) % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public int numFactoredBinaryTrees(int[] arr) {
final int mod = (int) 1e9 + 7;
Arrays.sort(arr);
int n = arr.length;
long[] f = new long[n];
Arrays.fill(f, 1);
Map<Integer, Integer> idx = new HashMap<>(n);
for (int i = 0; i < n; ++i) {
idx.put(arr[i], i);
}
for (int i = 0; i < n; ++i) {
int a = arr[i];
for (int j = 0; j < i; ++j) {
int b = arr[j];
if (a % b == 0) {
int c = a / b;
if (idx.containsKey(c)) {
int k = idx.get(c);
f[i] = (f[i] + f[j] * f[k]) % mod;
}
}
}
}
long ans = 0;
for (long v : f) {
ans = (ans + v) % mod;
}
return (int) ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
int numFactoredBinaryTrees(vector<int>& arr) {
const int mod = 1e9 + 7;
sort(arr.begin(), arr.end());
unordered_map<int, int> idx;
int n = arr.size();
for (int i = 0; i < n; ++i) {
idx[arr[i]] = i;
}
vector<long> f(n, 1);
for (int i = 0; i < n; ++i) {
int a = arr[i];
for (int j = 0; j < i; ++j) {
int b = arr[j];
if (a % b == 0) {
int c = a / b;
if (idx.count(c)) {
int k = idx[c];
f[i] = (f[i] + 1l * f[j] * f[k]) % mod;
}
}
}
}
long ans = 0;
for (long v : f) {
ans = (ans + v) % mod;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | func numFactoredBinaryTrees(arr []int) int {
const mod int = 1e9 + 7
sort.Ints(arr)
f := make([]int, len(arr))
idx := map[int]int{}
for i, v := range arr {
f[i] = 1
idx[v] = i
}
for i, a := range arr {
for j := 0; j < i; j++ {
b := arr[j]
if c := a / b; a%b == 0 {
if k, ok := idx[c]; ok {
f[i] = (f[i] + f[j]*f[k]) % mod
}
}
}
}
ans := 0
for _, v := range f {
ans = (ans + v) % mod
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | function numFactoredBinaryTrees(arr: number[]): number {
const mod = 10 ** 9 + 7;
arr.sort((a, b) => a - b);
const idx: Map<number, number> = new Map();
const n = arr.length;
for (let i = 0; i < n; ++i) {
idx.set(arr[i], i);
}
const f: number[] = new Array(n).fill(1);
for (let i = 0; i < n; ++i) {
const a = arr[i];
for (let j = 0; j < i; ++j) {
const b = arr[j];
if (a % b === 0) {
const c = a / b;
if (idx.has(c)) {
const k = idx.get(c)!;
f[i] = (f[i] + f[j] * f[k]) % mod;
}
}
}
}
return f.reduce((a, b) => a + b) % mod;
}
|