带因子的二叉树

823. 带因子的二叉树

给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回对 10⁹ + 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] <= 10⁹
arr 中的所有值 互不相同

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int numFactoredBinaryTrees(vector<int>& arr) { } };

python3 解法, 执行用时: 256 ms, 内存消耗: 16.3 MB, 提交时间: 2023-08-29 09:12:06

# 1:1翻译成递推
class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        arr.sort()
        idx = {x: i for i, x in enumerate(arr)}
        f = [1] * len(arr)
        for i, val in enumerate(arr):
            for j in range(i):  # val 的因子一定比 val 小
                x = arr[j]
                if val % x == 0 and val // x in idx:  # 另一个因子 val/x 必须在 arr 中
                    f[i] += f[j] * f[idx[val // x]]
        return sum(f) % (10 ** 9 + 7)

python3 解法, 执行用时: 288 ms, 内存消耗: 17.7 MB, 提交时间: 2023-08-29 09:11:29

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        arr.sort()
        idx = {x: i for i, x in enumerate(arr)}
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            res = 1
            val = arr[i]
            for j in range(i):  # val 的因子一定比 val 小
                x = arr[j]
                if val % x == 0 and val // x in idx:  # 另一个因子 val/x 必须在 arr 中
                    res += dfs(j) * dfs(idx[val // x])
            return res
        return sum(dfs(i) for i in range(len(arr))) % (10 ** 9 + 7)

golang 解法, 执行用时: 32 ms, 内存消耗: 3.6 MB, 提交时间: 2023-08-29 09:07:28

func numFactoredBinaryTrees(A []int) int {
    sort.Ints(A)
    K:=1000000007
    m:=make(map[int]int,0)
    m[A[0]]=1
    ans:=1
    for i:=1;i<len(A);i++{
        m[A[i]]=1
        for j:=i-1;j>=0;j--{
            if A[i]%A[j]==0{
                m[A[i]] = (m[A[i]]+(m[A[j]]*m[A[i]/A[j]])% K)%K
            }
        }
        ans=(ans+m[A[i]])%K
    }
    return ans
}

golang 解法, 执行用时: 20 ms, 内存消耗: 3.6 MB, 提交时间: 2023-06-07 10:58:01

/**
 * 动态规划, 先排序，i 遍历数组，以 arr[i] 作为根节点， 寻找其左右因子作为左右子树， 
 * 因此比 arr[i]/2 大的数忽略， 哈希记录组成 arr[i] 为根节点的种类， 
 * 左右因子种数相乘，累加到 hash[arr[i]] 中， 得到最终二叉树种类数。
 **/
func numFactoredBinaryTrees(arr []int) int {
    // 动态规划
    var ans int
    sort.Ints(arr)
    hasVal := make(map[int]int)
    // 确定根节点 arr[i] >= 2
    for i := range arr {
        hasVal[arr[i]]++
        for j := 0; j<i && arr[j] <= arr[i]/2; j++ {
            // 确定左子树 为 arr[j]， 右子树为 arr[i] / arr[j]
            if arr[i] % arr[j] == 0 && hasVal[arr[i]/arr[j]] != 0 {
                hasVal[arr[i]] += hasVal[arr[j]] * hasVal[arr[i]/arr[j]]
            }
        }
        ans += hasVal[arr[i]]
    }
    return ans % (1e9+7)
}

golang 解法, 执行用时: 32 ms, 内存消耗: 3.7 MB, 提交时间: 2023-06-07 10:57:01

func numFactoredBinaryTrees(A []int) int {
    sort.Ints(A)
    K:=1000000007
    m:=make(map[int]int,0)
    m[A[0]]=1
    ans:=1
    for i:=1;i<len(A);i++{
		m[A[i]]=1
    	for j:=i-1;j>=0;j--{
    		if A[i]%A[j]==0{
				m[A[i]] = (m[A[i]]+(m[A[j]]*m[A[i]/A[j]])% K)%K
			}
		}
		ans=(ans+m[A[i]])%K
	}
	return ans
}

golang 解法, 执行用时: 64 ms, 内存消耗: 3.6 MB, 提交时间: 2023-06-07 10:56:31

import "sort"

func numFactoredBinaryTrees(A []int) int {
	o := 0
	m := map[int]int{}
	sort.Ints(A)
	for i, a := range A {
		m[a] = 1
		for j := 0; j < i; j++ {
			b := A[j]
			c := a / b
			if _, ok := m[c]; ok && a%b == 0 {
				m[a] = (m[a] + m[b]*m[c]) % 1000000007
			}
		}
	}
	for _, a := range m {
		o = (o + a) % 1000000007
	}
	return o
}

python3 解法, 执行用时: 276 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-07 10:55:40

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

        return sum(dp) % MOD

java 解法, 执行用时: 28 ms, 内存消耗: 41.8 MB, 提交时间: 2023-06-07 10:53:41

/**
 * 动态规划
 * dp[i] 表示以 A[i] 为树根的树的种类数
 **/ 
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);
    }
}

上一题

下一题

详情