江西网站建设哪家公司好,广州新闻头条最新消息,瑞安联科网站建设,天津网站建设普斯泰823. 带因子的二叉树
题意
元素都大于1#xff0c;元素不重复。计数满足要求的二叉树#xff08;每个非叶结点的值应等于它的两个子结点的值的乘积#xff09;的数量。元素可以重复使用。
代码
自上而下动态规划。
所有元素大于1#xff0c;所以不会有 自己自己自己 的…823. 带因子的二叉树
题意
元素都大于1元素不重复。计数满足要求的二叉树每个非叶结点的值应等于它的两个子结点的值的乘积的数量。元素可以重复使用。
代码
自上而下动态规划。
所有元素大于1所以不会有 自己×自己自己 的情况元素本身就是一棵二叉树所以将 dp 初始化为全 1将数组 arr 排序后遍历数组 arr 当 arr[i] 为根节点时其子结点必然在 arr[0] ~ arr[i-1] 之间 在 arr[0] ~ arr[i-1] 之间寻找 (long long)arr[left] * arr[right] arr[i]。当 left right 时dp[i] dp[left] * dp[right]当 left right 时dp[i] 2 * dp[left] * dp[right]
class Solution {
public:int MAXN 1e9 7;int numFactoredBinaryTrees(vectorint arr) {sort(arr.begin(), arr.end());int n arr.size();vectorlong long dp(n1, 1); // 单个根节点的符合要求的二叉树数量就可能溢出用 longlong// dp[0] 1; // 最小的数只有一棵符合要求的二叉树for(int i 1; i n; i){// 子结点只能在 0 ~ i-1 之间因为元素都大于1int left 0, right i-1;while(left right) // 元素可被多次使用所以要 {if((long long)arr[left] * arr[right] arr[i]) // 可能溢出用 longlong{// if(arr[left] ! arr[right]) 元素不会重复可以直接比较下标if(left ! right){dp[i] 2 * dp[left] * dp[right];}else{dp[i] dp[left] * dp[right];}left;}else if((long long)arr[left] * arr[right] arr[i]) // 可能溢出用 longlong{left;}else{right--;}}}long long ans 0;for(int i 0; i n; i){ans dp[i];ans ans % MAXN;}return ans;}
};复杂度
时间复杂度O(N2)对每个元素遍历一次其之前的元素。 空间复杂度O(N)存储 dp 数组。
