2023-08-29每日一題
一、題目編號(hào)
823. 帶因子的二叉樹
二、題目鏈接
點(diǎn)擊跳轉(zhuǎn)到題目位置
三、題目描述
給出一個(gè)含有不重復(fù)整數(shù)元素的數(shù)組 arr ，每個(gè)整數(shù) arr[i] 均大于 1。
用這些整數(shù)來(lái)構(gòu)建二叉樹，每個(gè)整數(shù)可以使用任意次數(shù)。其中：每個(gè)非葉結(jié)點(diǎn)的值應(yīng)等于它的兩個(gè)子結(jié)點(diǎn)的值的乘積。
滿足條件的二叉樹一共有多少個(gè)？答案可能很大，返回 對(duì) 109 + 7 取余 的結(jié)果。
示例 1:
示例 2:
提示：
- 1 <= arr.length <= 1000
- 2 <= arr[i] <= 109
- arr 中的所有值 互不相同
四、解題代碼
class Solution {
const int mod = 1e9 + 7;
public:
int numFactoredBinaryTrees(vector<int>& arr) {
sort(arr.begin(), arr.end());
int n = arr.size();
vector<long long> dp(n);
long long res = 0;
for(int i = 0; i < n; ++i){
dp[i] = 1;
int left = 0;
int right = i - 1;
while(left <= right){
while(right >= left && (long long)arr[left] * arr[right] > arr[i]){
--right;
}
if(right >= left && (long long)arr[left] * arr[right] == arr[i]){
if(right > left){
dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
} else{
dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
}
}
++left;
}
res = (res + dp[i]) % mod;
}
return res;
}
};
五、解題思路
(1) 使用動(dòng)態(tài)規(guī)劃來(lái)解決問(wèn)題。首先將arr按照從小到大來(lái)進(jìn)行排序。設(shè)置狀態(tài)，dp[i]表示以arr數(shù)組下標(biāo)為i的結(jié)點(diǎn)為根結(jié)點(diǎn)的樹有多少種。
(2) 利用雙指針，left 等于 0， right 等于 i - 1， i為數(shù)組遍歷到的下標(biāo)。然后如果arr[left] * arr[right] 等于 arr[i] 的話，如果left等于right，那么dp[i] 應(yīng)當(dāng)加上 dp[left] 乘以 dp[right]。如果left 不等于 right，dp[i] 應(yīng)當(dāng)加上dp[left] 乘以 dp[right] 乘以 2。
(3) 因?yàn)榻Y(jié)果較大，不要忘記進(jìn)行取模運(yùn)算。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-683243.html
(4) 最后返回結(jié)果即可。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-683243.html
到了這里，關(guān)于2023-08-29 LeetCode（帶因子的二叉樹）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
