823. 带因子的二叉树

扩展生活的视野，主要靠开阔心胸。 - 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)，动态规划所用空间。