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]
思路：
1.動態規劃，如果 arr[i] = arr[j] * arr[k] 則他可以組成一個三個節點的二元樹
假設 dp(n) 表示這個數字共有幾種組合，每個數字都當根節點的話至少有一種組合，
所以我們把每個數字的組合初始化為 1。
2.我們可以先把 arr 從小到大排序，這樣只需要檢查比 i 小的 arr[j] 是否存在因數
arr[k]（檢查所有索引小於 i 的 arr），如果存在的話可以構建出
dp(arr[j]) * dp(arr[k]) 種樹，把他累加到 dp(arr[i])，因為我們排序過的關係，
所以處理到 i 的時候，dp(arr[j]) 和 dp(arr[k]) 一定已經計算完。
3.最後把 dp(arr[0], ....arr[n - 1]) 加總就是答案，因為數字很大所以要模 1e9+7。
Java Code：
--------------------------------------------------------
class Solution {
static final int MOD = 1000000007;
public int numFactoredBinaryTrees(int[] arr) {
Arrays.sort(arr);
Map<Integer, Long> map = new HashMap<>();
for (int num : arr) {
map.put(num, 1L);
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] % arr[j] == 0 && map.containsKey(arr[i] / arr[j]))
{
long sum = (map.get(arr[j]) * map.get(arr[i] / arr[j])) %
MOD;
map.put(arr[i], (map.get(arr[i]) + sum) % MOD);
}
}
}
long res = 0;
for (Map.Entry<Integer, Long> entry : map.entrySet()) {
res = (res + entry.getValue()) % MOD;
}
return (int)res;
}
}
----------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698329535.A.8B0.html
※ 編輯: Rushia (122.100.73.13 臺灣), 10/26/2023 22:15:53