leetcode 823. Binary Trees With Factors 带因子的二叉树

Problem: 823. Binary Trees With Factors 带因子的二叉树

解题过程

排序，然后使用哈希表，每个数字初始化1，ump[i] = 1;，然后对每个数字，遍历 比它小的数字，若可以整除，且商也在数组内，则考虑累乘，因左右子树的数量需要相乘才行，就像[2, 4, 16]，16左右子树都是4,但是4存在两种可能，所以需要相乘，考虑到数值比较大， 所以使用了unsigned long long，最后累加以后，再取模

Code

class Solution { public: const int modulo = 1e9 + 7; unordered_map<int, unsigned long long> ump; void dfs(vector<int>& arr, int index, int number) { int rem, div; for(int i = 0; i < index; i++) { rem = number % arr[i]; div = number / arr[i]; if(rem == 0 && ump.find(div)!=ump.end()) { ump[number] += (ump[arr[i]] * ump[div]); // % modulo; } } } int numFactoredBinaryTrees(vector<int>& arr) { sort(arr.begin(), arr.end()); for(int& i : arr) { ump[i] = 1; } for(int i = 1; i < arr.size(); i++) { dfs(arr, i, arr[i]); } unsigned long long sum = 0; for(auto [k, l] : ump) { sum += l; } return (sum%modulo); } };