原文链接: https://leetcode-cn.com/problems/binary-trees-with-factors

英文原文

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 109 + 7.

 

Example 1:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: arr = [2,4,5,10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

 

Constraints:

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 109
• All the values of arr are unique.

中文题目

给出一个含有不重复整数元素的数组 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 <= 1000
• 2 <= arr[i] <= 109
• arr 中的所有值 互不相同

通过代码

官方题解

方法 1：动态规划

想法

最大值 v 一定会被用在树的根节点上，设 dp(v) 是以 v 为根节点的树种类数。

如果树根节点有孩子 x 和 y 满足 x * y == v，那么就有 dp(x) * dp(y) 种方法构造这棵树。

总共会有 $\sum_{x * y = v} \text{dp}(x) * \text{dp}(y)$ 种方法构造以 v 为根的树。

算法

实际上，令 dp[i] 表示已 A[i] 为树根的树的种类数。

在上面的例子中我们知道 x < v 和 y < v，我们可以用动态规划的方法按照升序值计算 dp[i] 的值。

对于树根值 A[i]，需要找到所有可能的孩子节点取值 A[j] 和 A[i] / A[j]（显然要有 A[j] * (A[i] / A[j]) = A[i]）。为了快速的计算，我们使用 index 数组快速查找：如果 A[k] = A[i] / A[j]，那么 index[A[i] / A[j]] = k。

之后，我们将所有可能的值 dp[j] * dp[k]（其中 j < i, k < i）加入结果 dp[i] 中。在 Java 实现中，我们谨慎的使用了 long 类型避免溢出错误。

[]
class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        int MOD = 1_000_000_007;
        int N = A.length;
        Arrays.sort(A);
        long[] dp = new long[N];
        Arrays.fill(dp, 1);

        Map<Integer, Integer> index = new HashMap();
        for (int i = 0; i < N; ++i)
            index.put(A[i], i);

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < i; ++j) {
                if (A[i] % A[j] == 0) { // A[j] is left child
                    int right = A[i] / A[j];
                    if (index.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                    }
                }
            }

        long ans = 0;
        for (long x: dp) ans += x;
        return (int) (ans % MOD);
    }
}

[]
class Solution(object):
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        N = len(A)
        A.sort()
        dp = [1] * N
        index = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for j in xrange(i):
                if x % A[j] == 0: #A[j] will be left child
                    right = x / A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

        return sum(dp) % MOD

复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N$ 是 A 的长度。这是由于两层循环 i 和 j。
• 空间复杂度：$O(N)$，dp 和 index 使用的空间。

统计信息

通过次数	提交次数	AC比率
3146	7332	42.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言