题目描述:
LeetCode 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:
Input: A = [2, 4] Output: 3 Explanation: We can make these trees: [2], [4], [4, 2, 2]
Example 2:
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
.
题目大意:
给定一组互不重复的正整数。
利用正整数构建二叉树,每一个非叶子节点都必须等于其子节点的乘积。
求可以构建多少种不同的二叉树。
解题思路:
动态规划(Dynamic Programming)
将A从小到大排序 dp[a] = sum(dp[m] * dp[n] * (1 + (m != n))) % MOD 其中,m * n == a 并且a % m == 0,m <= sqrt(a)
Python代码:
class Solution(object):
def numFactoredBinaryTrees(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
dp = collections.defaultdict(int)
MOD = 10 ** 9 + 7
for i, a in enumerate(A):
num = 0
for j in range(i):
m = A[j]
if m * m > a: break
if a % m: continue
n = a / m
num = (num + dp[m] * dp[n] * (1 + (m != n))) % MOD
dp[a] = num + 1
return sum(dp.values()) % MOD
本文链接:http://bookshadow.com/weblog/2018/04/22/leetcode-binary-trees-with-factors/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。