2023-08-29每日一题
一、题目编号
823. 带因子的二叉树
二、题目链接
点击跳转到题目位置
三、题目描述
给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。
示例 1:
示例 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) 最后返回结果即可。
