LeetCode 823. 带因子的二叉树

Categories:

题目描述
思路分析
1. 解法一：动态规划 + 哈希表（推荐）
相似题目

题目描述

✅ 823. 带因子的二叉树

思路分析

解法一：动态规划 + 哈希表（推荐）

核心思路：

排序数组后，定义 dp[i] 为以 arr[i] 为根节点的带因子二叉树数量

对于每个 arr[i]，枚举所有满足 arr[j] * arr[k] == arr[i] 的因子对

若 arr[i] % arr[j] == 0 且 arr[i] / arr[j] 也在数组中，则 dp[i] += dp[j] * dp[k]

初始值 dp[i] = 1（只有根节点本身），最终累加所有 dp[i] 取模后返回

复杂度分析：

时间复杂度：O(n²)，其中 n 表示数组长度，外层枚举每个元素，内层枚举其因子

空间复杂度：O(n)，哈希表和 dp 数组所需空间

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        int MOD = 1_000_000_007;
        Arrays.sort(arr);

        // 建立值到下标的映射，方便快速查找因子是否存在
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            indexMap.put(arr[i], i);
        }

        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                // 判断 arr[j] 是否为 arr[i] 的因子
                if (arr[i] % arr[j] == 0) {
                    int right = arr[i] / arr[j];
                    if (indexMap.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[indexMap.get(right)]) % MOD;
                    }
                }
            }
        }

        long ans = 0;
        for (long v : dp) {
            ans = (ans + v) % MOD;
        }
        return (int) ans;
    }
}

func numFactoredBinaryTrees(arr []int) int {
    const MOD = 1_000_000_007

    sort.Ints(arr)
    n := len(arr)

    // 建立值到下标的映射
    indexMap := make(map[int]int, n)
    for i, v := range arr {
        indexMap[v] = i
    }

    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            // 判断 arr[j] 是否为 arr[i] 的因子
            if arr[i]%arr[j] == 0 {
                right := arr[i] / arr[j]
                if k, ok := indexMap[right]; ok {
                    dp[i] = (dp[i] + dp[j]*dp[k]) % MOD
                }
            }
        }
    }

    ans := 0
    for _, v := range dp {
        ans = (ans + v) % MOD
    }
    return ans
}

相似题目

题目	难度	考察点
96. 不同的二叉搜索树	中等	动态规划
95. 不同的二叉搜索树 II	中等	动态规划/递归
279. 完全平方数	中等	动态规划
322. 零钱兑换	中等	动态规划
343. 整数拆分	中等	动态规划
509. 斐波那契数	简单	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/38614771