823. 带因子的二叉树
2023-08-30 本文已影响0人
红树_
扩展生活的视野,主要靠开阔心胸。 - Hugh Black。
题目
LC每日一题,参考823. 带因子的二叉树,难度分1900。
解题思路
-
动态规划 + 双指针或哈希表:首先肯定是排序,从小到大计算每一个数作为根节点的所有可能数,而因子叶节点肯定比当前数小,所以可以应用动态规划(也可以使用递归记忆化搜索),转移方程为
dp[i] = 1 + dp[left] * dp[right] * (1 +(left<right?1:0))(left和right为所有满足arr[left]*arr[right]=arr[i]的下标)
(具体解释和实现请参考以下注释和代码);对于所有可能的因子数,可以使用双指针查找或者使用哈希表判断因子数是否能被arr[i]
整除和被整除的数是否在哈希表里面。
动态规划 + 双指针 15ms
class Solution {
public int numFactoredBinaryTrees(int[] arr) {
int n = arr.length, MOD = (int)(1e9+7);
long ans = 0;
//首先肯定排序
Arrays.sort(arr);
//从值小的开始计算 应用动态规划
long[] dp = new long[n];
for(int i = 0; i < n; i++) {
dp[i] = 1; //本身1
//使用双指针找所有满足cur的因子叶节点 因为cur>=2所以范围0,i-1
int cur = arr[i];
int left = 0, right = i-1;
while(left <= right) {
//必须用long接收target否则溢出会计算不准确
long target = (long)arr[left] * arr[right];
if(target > cur) right--;//先判断大于是个技巧,有取模数一般很大,加大命中率
else if(target < cur) left++;
else {
//对于所有满足的因子都有left,right < i 所以可用前面的dp来求
dp[i] += dp[left] * dp[right] * (1 +(left<right?1:0));
left++;
right--;
}
}
ans += dp[i];
}
return (int)(ans%MOD);
}
}
复杂度分析
- 时间复杂度:
O(n^2)
,双重枚举循环,n
为数组长度。 - 空间复杂度:
O(n)
,动态规划所用空间。