※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: https://leetcode.com/problems/binary-trees-with-factors/description/
: 823. Binary Trees With Factors
: 给你一个阵列 arr，里面的数字不重复且大于 1，我们可以不限制次数的使用这些
: 数字构建出一个二元树，这个二元树需要满足左右节点的值相乘等于父节点，求出
: 共有几种组合。
: Example 1:
: Input: arr = [2,4]
: Output: 3
: Explanation: We can make these trees: [2], [4], [4, 2, 2]
思路：
动态规划基本题
判断两个节点有没有都在arr里面
有的话就把两个child的可能性乘起来
另外宣告一个Set
可以让判断乘数有没有在阵列中的时候不用再找整个阵列一次
因为Set的时间复杂度是O(1)
原本想说可以不用理会乘数跟被乘数交换的状况
反正最终都会轮到
但是后来看了别人的解答后
发现我没有考虑到数字很大的情况下
n跟sqrt(n)会差很大
有加上这个判断可以让时间复杂度从O(n^2)降到O(n*sqrt(n))
TS code:
function numFactoredBinaryTrees (arr: number[]): number {
const sortedArr = arr.sort((a, b) => (a - b))
const set = new Set(sortedArr)
const dp: number[] = new Array(arr.length)
for (let i = 0; i < sortedArr.length; i++) {
const element = sortedArr[i]
dp[i] = 1
for (let j = 0; j < i; j++) {
const lChild = sortedArr[j];
if (lChild > Math.sqrt(element)) break
if (element % lChild === 0) {
const rChild = element / lChild
if (rChild === lChild) {
dp[i] = (dp[i] + dp[j] * dp[j]) % 1000000007
} else if (set.has(rChild)) {
dp[i] = (dp[i] + dp[j] * dp[sortedArr.indexOf(rChild)] * 2) %
1000000007
}
}
}
}
let result = 0
for (let i = 0; i < dp.length; i++) {
const dpItem = dp[i]
result = (result + dpItem) % 1000000007
}
return result
}