823. Binary Trees With Factors

发表于 | 分类于 | |

823. Binary Trees With Factors

题目描述

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

1
2
3
Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

1
2
3
Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

  • 1 <= A.length <= 1000.
  • 2 <= A[i] <= 10 ^ 9.

题目大意

给定一数组，求最多能生成多少棵，满足左右子节点相乘等于根节点的树，结果最大为 10 ** 9 + 7

解题思路

动态规划
对 A 进行排序。
如果 m * n == a，并且 m * m < a, a % m == 0
则 a 能生成的树为 m * n 如果 m != n则再乘以 2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    func numFactoredBinaryTrees(_ A: [Int]) -> Int {
        var dp = [Int: Int]()
        let mod = Int(pow(10.0, 9.0)) + 7
        let sortedA = A.sorted()
        for (i, a) in sortedA.enumerated() {
            var num = 0
            for m in sortedA[0..<i] {
                if m * m > a { break }
                if a % m > 0 { continue }
                let n = a / m
                num = num + dp[m]! * (dp[n] ?? 0) * (m != n ? 2 : 1) % mod
            }
            dp[a] = num + 1
        }
        return dp.reduce(0, { (res, arg1) -> Int in
            let (_, v) = arg1
            return v + res
        }) % mod
    }
}
0%