823.带因子的二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了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 中的所有值 互不相同

思路

题目中要的是父亲节点的val = 左孩子.val * 右孩子的val，根据题目的意思，单节点也算
c = b*a，所有看看能不能枚举c =》是可以枚举的，将原有数组进行排序（升序）
当枚举到下标的i的时候，有多少种呢？这里有一个dp数组来做存储
定义dp数组 long[] dp ，当下表来到i的时候，满足条件的二叉树的个数 dp[i] = xxx
具体的计算逻辑 arr[i] = arr[x] * arr[y]，只有在满足这种条件的时候才能算一种
此时的值是 arr[i] , 题目中给出了每个元素都不一样，所以要想在排序好的数组里面找到一个因子是属于arr[i]的，那么这个因子arr[j]的下标 j < i，并且另外一个因子也是属于arr的，此时就转换成了一个因子拆分的问题，在拆分的过程中，需要将下标i之前的全部因子都看一遍
dp[i] = dp[j] * d[k] （arr[j], arr[k]）都在arr中，这里为啥是乘法？左边有m种，右边有n种，总的就是m*n种
结果就是遍历一下dp数组，将和加起来就ok了文章来源地址https://www.toymoban.com/news/detail-693888.html

        //对原有数组排序
        Arrays.sort(arr);
        //记录other的值，以及下 c = a/b，方便check
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }
        //定义的dp数组
        long[] dp = new long[arr.length];
        //每个元素都会存在一种情况，这里就默认初始化成1
        Arrays.fill(dp, 1);
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                //说明arr[j]是因子，并且另外一个因子也是在arr中的
                if (arr[i] % arr[j] == 0 && map.containsKey(arr[i] / arr[j])) {
                    int k = map.get(arr[i] / arr[j]);
                    dp[i] += (dp[j] * dp[k]) % mod;
                }
            }
        }
        //计算结果
        long res = 0;
        for (long j : dp) {
            res += j;
            res %= mod; //越界问题处理
        }
        return (int) (res % mod);