leetcode 823. 带因子的二叉树(dp+双指针+Long类型)-Toy模板网

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

leetcode 823. 带因子的二叉树(dp+双指针+Long类型)

题目表述

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

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

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

思路

dp+双指针比较好想
难点有两个：
1、两个子树相同的节点值的时候，不应该是数量相乘再乘2（正常不同值结点计算 $s u m = n * m * 2$ ），应该是 $sum=c^2_n+n=n^2$ 。
2、对于Java中long的使用，如果使用int的范围超过 $- 2147483648 至 2147483647$ int会自动截断然后放到int里。
例子：

 System.out.println((18865777)*(36451879));
 System.out.println(((long)(18865777)*(36451879)));

会输出

36878647
687693020444983

处理方法就如上述所示，把其中一个数强转为long，这样运算结果会自动强转为long，运算过程也会扩展为long。

注意点

1、Long不支持带e的赋值方法

long x = 10e9+5 //不支持

2、 $2 <= arr[i] <= 10^9$ 所以可以在双指针进入循环前提前判断值的大小问题，超过 $10^9$ 可以筛掉，此题的数据集应该是最后的大数的量比较多，所以这个点会让速度快一些
leetcode 823. 带因子的二叉树(dp+双指针+Long类型),java
下面一个是加了这个筛选的结果。

ac代码

Java:

class Solution {

    public int numFactoredBinaryTrees(int[] arr) {
        long result=0;
        int begin,end;
        long mod = 1000000007;
        Arrays.sort(arr);
        long[] sum = new long[arr.length];
        Arrays.fill(sum,1);
        for (int i=1;i<arr.length;i++)
        {
            begin = 0;
            end = i-1;
            while(begin<=end)
            {
            if((long)arr[begin]*arr[end]>=mod)
                {
                    end--;
                    continue;
                }
                if ((long)arr[begin]*arr[end]==arr[i]) {
                    sum[i]+=((long)sum[begin]*sum[end]*2);
                    if (begin==end)
                        sum[i]-=((long)sum[begin]*sum[end]);
                    begin++;
                    sum[i]%=mod;
                }
                else if ((long)arr[begin]*arr[end]<arr[i])
                    begin++;
                else
                    end--;

            }
        }
        for (long x:sum)
        {
            result += x;
            result%=mod;
        }
        return (int)result;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-trees-with-factors/description/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。文章来源地址https://www.toymoban.com/news/detail-683959.html

到了这里，关于leetcode 823. 带因子的二叉树(dp+双指针+Long类型)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！