LeetCode 823. 带因子的二叉树 C#
原题链接
中等
作者:
hpstory
,
2022-11-29 14:57:08
,
所有人可见
,
阅读 144
C# 代码
public class Solution {
public int NumFactoredBinaryTrees(int[] arr) {
int mod = 1000000007;
int n = arr.Length;
Array.Sort(arr);
long[] dp = new long[n];
Array.Fill(dp, 1);
Dictionary<int, int> dict = new Dictionary<int, int>();
long result = 0;
for (int i = 0; i < n; i++){
if (!dict.ContainsKey(arr[i])) dict.Add(arr[i], i);
for (int j = 0; j < i; j++){
if (arr[i] % arr[j] == 0 && dict.ContainsKey(arr[i] / arr[j])){
dp[i] = dp[i] + dp[j] * dp[dict[arr[i] / arr[j]]];
}
}
result = (result + dp[i]) % mod;
}
return (int)result;
}
}