算法

823. 带因子的二叉树

2023-08-30  本文已影响0人  红树_

扩展生活的视野,主要靠开阔心胸。 - Hugh Black。

题目

LC每日一题,参考823. 带因子的二叉树,难度分1900。

解题思路

动态规划 + 双指针 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);
    }
}

复杂度分析

上一篇 下一篇

猜你喜欢

热点阅读