BinaryTreeWithFactors [source code]

public class BinaryTreeWithFactors {
static
/******************************************************************************/
class Solution {
    public int numFactoredBinaryTrees(int[] nums) {
        Arrays.sort (nums);
        int N = nums.length;
        long[] counts = new long[N];
        Arrays.fill (counts, 1);
        long sum = 1;
        for (int i = 1; i < N; i++) {
            countProduct (nums, i, 0, i - 1, counts);
            sum += counts[i];
        }
        return (int) (sum % 10000_00007);
    }

    void countProduct (int[] nums, int target, int lo, int hi, long[] counts) {
        while (lo <= hi) {
            if (nums[target] == nums[lo] * nums[hi]) {
                if (lo == hi) {
                    counts[target] += counts[lo] * counts[lo];
                } else {
                    counts[target] += 2 * counts[lo] * counts[hi];
                }
                // can't break here! think about find 18 in [2,3,6,9]
                hi--;
                lo++;
            } else if (nums[target] < nums[lo] * nums[hi]) {
                hi--;
            } else {
                lo++;
            }
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BinaryTreeWithFactors.Solution tester = new BinaryTreeWithFactors.Solution();
        int[][] inputs = {
            {2, 4}, {3},
            {2, 4, 5, 10}, {7}, 
            {18, 3, 6, 2}, {12},
            {45,42,2,18,23,1170,12,41,40,9,47,24,33,28,10,32,29,17,46,11,759,37,6,26,21,49,31,14,19,8,13,7,27,22,3,36,34,38,39,30,43,15,4,16,35,25,20,44,5,48}, {777},
            {46,144,5040,4488,544,380,4410,34,11,5,3063808,5550,34496,12,540,28,18,13,2,1056,32710656,31,91872,23,26,240,18720,33,49,4,38,37,1457,3,799,557568,32,1400,47,10,20774,1296,9,21,92928,8704,29,2162,22,1883700,49588,1078,36,44,352,546,19,523370496,476,24,6000,42,30,8,16262400,61600,41,24150,1968,7056,7,35,16,87,20,2730,11616,10912,690,150,25,6,14,1689120,43,3128,27,197472,45,15,585,21645,39,40,2205,17,48,136}, {509730797},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            int[] nums = inputs[2 * i];
            int ans = inputs[2 * i + 1][0], output = tester.numFactoredBinaryTrees (nums);
            System.out.printf ("%s\n%s\n%s\n", 
                Printer.array (nums), Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

感觉就是找乘法因子的过程, 好像有点recursion的东西在里面;

这题怎么看起来有点像2sum啊? 每一个数字找自己前面数字里面能够乘积等于自己的? 允许重复使用因子;

尝试写一下; 这题肯定要写的稍微有效一点, 不然会卡复杂度;

看起来这题sort一下应该比较合理, 所以如果写类2sum算法, 直接也写sort的那个版本就行了;

典型例子可以用10找5和2来参考; 然后最后再处理2,4这种情况(2能用两次);

写的过程中发现其实是一个DP题目, 而且root involvement很明显: root就是作为product, 或者说是subtree的root;

因为这题允许重复, 所以最后2pointer移动的时候很费脑筋;

卧槽, 漏看一个条件, 虽然一个数字可以复用, 但是题目规定这个数组本身里面没有重复; 那就简单很多了;

最后还是没有做出来啊, 看起来信心满满; 最后还是被一个大case被break掉了; 感觉是逻辑里面有什么漏洞没有考虑到;

好气啊, 最后就超时一分钟做出来了;

想想也难怪, medium题目作为压轴, 不挖点坑都对不起观众;

总结下来, 这题忽略条件其实也耽误了不少时间, 先是忽略了all unique这个条件, 然后最后那个取模操作也忽略了; 关键最后testcase里面居然还真的有测这个取模的: 导致我一些sum变量全部要换成long;

UNFINISHED

uwi:

class Solution {  
    public int numFactoredBinaryTrees(int[] a) {  
        Arrays.sort(a);  
        a = uniq(a);  
        int n = a.length;  
        int mod = 1000000007;  

        long[] dp = new long[n];  
        long ret = 0;  
        for(int i = 0;i < n;i++){  
            int p = i-1;  
            for(int j = 0;j < i;j++){  
                if(a[i] % a[j] == 0){  
                    while(p >= 0 && a[p] > a[i] / a[j])p--;  
                    if(p >= 0 && a[p] == a[i] / a[j]){  
                        dp[i] += dp[j] * dp[p];  
                        dp[i] %= mod;  
                    }  
                }  
            }  
            dp[i]++;  
            dp[i] %= mod;  
            ret += dp[i];  
        }  
        return (int)(ret%mod);  
    }  

    int[] uniq(int[] a)  
    {  
        int n = a.length;  
        int p = 0;  
        for(int i = 0;i < n;i++) {  
            if(i == 0 || a[i] != a[i-1])a[p++] = a[i];  
        }  
        return Arrays.copyOf(a, p);  
    }  
}

他5分钟做完的, 无语了; 果然这题是有一点DP性质在里面的;

没仔细看了, 不过说实话我自己这题的算法是相当ok了已经; 就是写的慢了;

Problem Description

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node's value should be equal to the product of the values of it's children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]  
Output: 3  
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]  
Output: 7  
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

• 1 <= A.length <= 1000.
• 2 <= A[i] <= 10 ^ 9.

Difficulty:Medium
Total Accepted:338
Total Submissions:1.5K
Contributor:ngoc_lam