​LeetCode解法汇总823. 带因子的二叉树

 目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

描述：

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

解题思路：

从小到大排列，后面的数字，一定是前面数字的乘积。所以我们先求前面的值二叉树可能数量，并且保存下来。后面的值如果存在两个数的乘积，就是前面两个数的可能数量的乘积，如果两个数不同，则还需要乘以2，因为左右位置可以调换。

代码：

class Solution823
{
public:int numFactoredBinaryTrees(vector<int> &arr){sort(arr.begin(), arr.end());map<int, long long> numMap;long long sum = 0;int index = 0;long long mod = 1e9 + 7;while (index < arr.size()){int i = 0;long long num = 1;int currentValue = arr[index];while (arr[i] <= (currentValue / arr[i])){if (currentValue % arr[i] != 0){i++;continue;}int value = currentValue / arr[i];if (numMap.find(value) == numMap.end()){i++;continue;}if (value == arr[i]){num = (num + numMap[value] * numMap[value]) % mod;}else{num = (num + (numMap[value] * numMap[arr[i]] * 2)) % mod;}i++;}sum = (sum + num) % mod;numMap[currentValue] = num;index++;}return sum;}
};