上海松江水处理网站建设,关于seo网站优化公司,南昌模板建站定制,做海报创客贴同类网站目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
给出一个含… 目录链接
力扣编程题-解法汇总_分享记录-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 10002 arr[i] 109arr 中的所有值 互不相同 解题思路
从小到大排列后面的数字一定是前面数字的乘积。所以我们先求前面的值二叉树可能数量并且保存下来。后面的值如果存在两个数的乘积就是前面两个数的可能数量的乘积如果两个数不同则还需要乘以2因为左右位置可以调换。 代码
class Solution823
{
public:int numFactoredBinaryTrees(vectorint arr){sort(arr.begin(), arr.end());mapint, 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;}
};
