2023-08-29 LeetCode（带因子的二叉树）-Toy模板网

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

2023-08-29每日一题

一、题目编号

823. 带因子的二叉树

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

满足条件的二叉树一共有多少个？答案可能很大，返回对 109 + 7 取余的结果。

示例 1:
2023-08-29 LeetCode（带因子的二叉树）,LeetCode每日一题,leetcode,算法,数据结构
示例 2:

提示：

1 <= arr.length <= 1000
2 <= arr[i] <= 109
arr 中的所有值互不相同

四、解题代码

class Solution {
    const int mod = 1e9 + 7;
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        vector<long long> dp(n);
        long long res = 0;
        for(int i = 0; i < n; ++i){
            dp[i] = 1;
            int left = 0;
            int right = i - 1;
            while(left <= right){
                while(right >= left && (long long)arr[left] * arr[right] > arr[i]){
                    --right;
                }
                if(right >= left && (long long)arr[left] * arr[right] == arr[i]){
                    if(right > left){
                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                    } else{
                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                    }
                }
                ++left;
            }
            res = (res + dp[i]) % mod;
        }
    return res;
    }
};

五、解题思路

(1) 使用动态规划来解决问题。首先将arr按照从小到大来进行排序。设置状态，dp[i]表示以arr数组下标为i的结点为根结点的树有多少种。

(2) 利用双指针，left 等于 0， right 等于 i - 1， i为数组遍历到的下标。然后如果arr[left] * arr[right] 等于 arr[i] 的话，如果left等于right，那么dp[i] 应当加上 dp[left] 乘以 dp[right]。如果left 不等于 right，dp[i] 应当加上dp[left] 乘以 dp[right] 乘以 2。

(3) 因为结果较大，不要忘记进行取模运算。

(4) 最后返回结果即可。文章来源地址https://www.toymoban.com/news/detail-683243.html

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