823.带因子的二叉树

链接：823.带因子的二叉树
难度：Medium
标签：数组、哈希表、动态规划、排序
简介：给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。满足条件的二叉树一共有多少个？。

题解 1 - python

• 编辑时间：2023-08-29
• 执行用时：312ms
• 内存消耗：16.79MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 1000000007
        arr.sort()
        s = set()
        for num in arr:
            s.add(num)
        @cache
        def dfs(root: int) -> int:
            res = 1
            for num in arr:
                if num >= root: break
                if root % num != 0: continue
                if root // num not in s: continue
                res = (res + dfs(num) * dfs(root // num) % MOD) % MOD
            return res
        return sum(dfs(num) for num in arr) % MOD

题解 2 - cpp

• 编辑时间：2023-08-29
• 执行用时：52ms
• 内存消耗：8.66MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        int MOD = 1e9 + 7, n = arr.size(), res = 1;
        sort(arr.begin(), arr.end());
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) m[arr[i]] = i;
        vector<long long> list(n, 1);
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] % arr[j] == 0 && m.count(arr[i] / arr[j])) {
                    list[i] = (list[i] + list[j] * list[m[arr[i] / arr[j]]] % MOD) % MOD;
                }
            }
            res = (res + list[i]) % MOD;
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-08-29
• 执行用时：384ms
• 内存消耗：15.91MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 1000000007
        n = len(arr)
        res = 1
        arr.sort()
        m = {}
        for i in range(n):
            m[arr[i]] = i
        list = [1 for _ in range(n)]
        for i in range(1, n):
            for j in range(i-1, -1, -1):
                if arr[i] % arr[j] == 0 and arr[i] // arr[j] in m:
                    list[i] = (list[i] + list[j] *
                                list[m[arr[i] / arr[j]]] % MOD) % MOD
            res = (res + list[i]) % MOD
        return res

题解 4 - rust

• 编辑时间：2023-08-29
• 执行用时：20ms
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn num_factored_binary_trees(mut arr: Vec<i32>) -> i32 {
        const MOD: i64 = 1000000007;
        let n = arr.len();
        let mut res = 1;
        arr.sort();
        let mut m = std::collections::HashMap::<i32, usize>::new();
        for (i, num) in arr.iter().enumerate() {
            m.insert(*num, i);
        }
        let mut list = vec![1i64; n];
        for i in 1..n {
            for j in (0..i).rev() {
                if arr[i] % arr[j] == 0 && m.contains_key(&(arr[i] / arr[j])) {
                    let idx = m.get(&(arr[i] / arr[j])).unwrap();
                    list[i] = (list[i] + list[j] * list[*idx] % MOD) % MOD;
                }
            }
            res = (res + list[i]) % MOD;
        }
        res as i32
    }
}