【每日一题】823. 带因子的二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】823. 带因子的二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

823. 带因子的二叉树

题目描述

给出一个含有不重复整数元素的数组 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 中的所有值互不相同

解题思路

思路：求解满足条件的二叉树有多少个，该如何求解保证唯一性呢？枚举根节点！由于整数的因子必定比该整数小，故可以先对整数数组进行排序。由于求解时只会使用到以整数数组元素作为根节点的二叉树数目，故dfs(i)的i表示数组下标，记忆化数组memo[i]的i也表示数组下标。其中i=j*k，i是当前乘积，j是乘积因子且j<i，如何查找k呢？使用arr[i]/arr[j]对应的下标，故此时需要使用umap将数组元素与下标对应。总而言之，即先对数组排序，接着将数组元素与对应下标进行映射，然后枚举数组元素，求解以每一个元素作为根节点的二叉树数量并进行累加，对于以某一节点i为根节点的二叉树数量求解方法为，枚举<i的节点j，判断是否能够在数组中找到k使得i=j*k，此处可以加入记忆化。

// 超时递归
class Solution {
public:
    const int MOD=1e9+7;
    int numFactoredBinaryTrees(vector<int>& arr) {
        // 存储数组元素 用于O(1)存取
        unordered_set<int> s(arr.begin(),arr.end());
        function<long long (int)> dfs=[&](int val) -> long long{
            // 如果val无分解因子 则相当于return 1
            long long res=1;
            // 遍历查找因子
            for(int x:arr)
            {
                if(val%x==0&&s.count(val/x))
                    res+=dfs(x)*dfs(val/x);
            }
            return res;
        };
        long long res=0;
        // 枚举每一个根节点
        for(int x:arr)
            res+=dfs(x);
        return res%MOD;
    }
};

// 通过 记忆化
class Solution {
public:
    const int MOD=1e9+7;
    int numFactoredBinaryTrees(vector<int>& arr) {
        // 对数组排序 方便记忆化
        sort(arr.begin(),arr.end());
        int n=arr.size();
        // 记忆化数组 
        vector<long long> memo(n,-1);
        // 存储数组元素 用于O(1)存取
        unordered_map<int,int> s;
        // 将数组元素与数组下标映射
        for(int i=0;i<n;i++)
            s[arr[i]]=i;
        function<long long (int)> dfs=[&](int i) -> long long{
            // 已经计算过则直接返回
            if(memo[i]!=-1)
                return memo[i];
            // 如果val无分解因子 则相当于return 1
            long long res=1;
            int val=arr[i];
            // 遍历查找因子
            for(int j=0;j<i;j++)
            {
                int x=arr[j];
                if(val%x==0&&s.count(val/x))
                    res+=dfs(j)*dfs(s[val/x]);
            }
            return memo[i]=res;
        };
        long long res=0;
        // 枚举每一个根节点 根节点只有一个 每个根节点不同即为不同 根节点代表唯一性
        for(int i=0;i<n;i++)
            res+=dfs(i);
        return res%MOD;
    }
};

// 通过 动态规划
class Solution {
public:
    const int MOD=1e9+7;
    int numFactoredBinaryTrees(vector<int>& arr) {
        // 对数组排序 方便记忆化
        sort(arr.begin(),arr.end());
        int n=arr.size();
        // 记忆化数组 
        vector<long long> f(n,1);
        // 存储数组元素 用于O(1)存取
        unordered_map<int,int> s;
        // 将数组元素与数组下标映射
        for(int i=0;i<n;i++)
            s[arr[i]]=i;
        for(int i=0;i<n;i++)
        {
            int val=arr[i];
            // 遍历查找因子
            for(int j=0;j<i;j++)
            {
                int x=arr[j];
                if(val%x==0&&s.count(val/x))
                    f[i]+=f[j]*f[s[val/x]];
            }
        }
        long long res=0;
        // 枚举每一个根节点 根节点只有一个 每个根节点不同即为不同 根节点代表唯一性
        for(int i=0;i<n;i++)
            res+=f[i];
        return res%MOD;
    }
};

// 通过 动态规划+对称性
class Solution {
public:
    const int MOD=1e9+7;
    int numFactoredBinaryTrees(vector<int>& arr) {
        // 对数组排序 方便记忆化
        sort(arr.begin(),arr.end());
        int n=arr.size();
        // 记忆化数组 
        vector<long long> f(n,1);
        // 存储数组元素 用于O(1)存取
        unordered_map<int,int> s;
        // 将数组元素与数组下标映射
        for(int i=0;i<n;i++)
            s[arr[i]]=i;
        for(int i=0;i<n;i++)
        {
            int val=arr[i];
            // 遍历查找因子
            for(int j=0;j<i;j++)
            {
                int x=arr[j];
                // 算到一半即可
                if(1LL*x*x>val)
                    break;
                // 临界点
                if(x*x==val)
                {
                    f[i]+=f[j]*f[j];
                    break;
                }
                // 12 = 2*6 = 6*2
                if(val%x==0&&s.count(val/x))
                    f[i]+=f[j]*f[s[val/x]]*2;
            }
        }
        long long res=0;
        // 枚举每一个根节点 根节点只有一个 每个根节点不同即为不同 根节点代表唯一性
        for(int i=0;i<n;i++)
            res+=f[i];
        return res%MOD;
    }
};

总结：递归->记忆化搜索->动态规划->滚动数组。文章来源地址https://www.toymoban.com/news/detail-681666.html

到了这里，关于【每日一题】823. 带因子的二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！