※ 引述《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
}