-
帶因子的二叉樹
題目
給出一個含有不重復整數(shù)元素的數(shù)組 arr ，每個整數(shù) arr[i] 均大于 1。
用這些整數(shù)來構建二叉樹，每個整數(shù)可以使用任意次數(shù)。其中：每個非葉結點的值應等于它的兩個子結點的值的乘積。
滿足條件的二叉樹一共有多少個？答案可能很大，返回 對 109 + 7 取余 的結果。
示例
示例 1:
輸入: arr = [2, 4]
輸出: 3
解釋: 可以得到這些二叉樹: [2], [4], [4, 2, 2]
示例 2:
輸入: arr = [2, 4, 5, 10]
輸出: 7
解釋: 可以得到這些二叉樹: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]
提示
1 <= arr.length <= 1000
2 <= arr[i] <= 109
arr 中的所有值 互不相同
思路
-
題目中要的是父親節(jié)點的val = 左孩子.val * 右孩子的val， 根據(jù)題目的意思，單節(jié)點也算
-
c = b*a，所有看看能不能枚舉c =》是可以枚舉的，將原有數(shù)組進行排序（升序）
-
當枚舉到下標的i的時候，有多少種呢？這里有一個dp數(shù)組來做存儲
-
定義dp數(shù)組 long[] dp ，當下表來到i的時候，滿足條件的二叉樹的個數(shù) dp[i] = xxx
-
具體的計算邏輯 arr[i] = arr[x] * arr[y]，只有在滿足這種條件的時候才能算一種
-
此時的值是 arr[i] , 題目中給出了每個元素都不一樣，所以要想在排序好的數(shù)組里面找到一個因子是屬于arr[i]的，那么這個因子arr[j]的下標 j < i，并且另外一個因子也是屬于arr的，此時就轉換成了一個因子拆分的問題，在拆分的過程中，需要將下標i之前的全部因子都看一遍
-
dp[i] = dp[j] * d[k] （arr[j], arr[k]） 都在arr中，這里為啥是乘法？左邊有m種，右邊有n種，總的就是m*n種文章來源：http://www.zghlxwxcb.cn/news/detail-693888.html
-
結果就是遍歷一下dp數(shù)組，將和加起來就ok了文章來源地址http://www.zghlxwxcb.cn/news/detail-693888.html
-
//對原有數(shù)組排序 Arrays.sort(arr); //記錄other的值，以及下 c = a/b，方便check Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < arr.length; i++) { map.put(arr[i], i); } //定義的dp數(shù)組 long[] dp = new long[arr.length]; //每個元素都會存在一種情況，這里就默認初始化成1 Arrays.fill(dp, 1); for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { //說明arr[j]是因子，并且另外一個因子也是在arr中的 if (arr[i] % arr[j] == 0 && map.containsKey(arr[i] / arr[j])) { int k = map.get(arr[i] / arr[j]); dp[i] += (dp[j] * dp[k]) % mod; } } } //計算結果 long res = 0; for (long j : dp) { res += j; res %= mod; //越界問題處理 } return (int) (res % mod);
到了這里，關于823.帶因子的二叉樹的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
