823. Binary Trees With Factors

二刷 08/2022

Version #1 DP

之前的做法是存num value和dp的值

这次的做法是存index 和value-index的mapping，明显更快

Time O(N^2)

Space O(N)

Runtime: 19 ms, faster than 99.42% of Java online submissions for Binary Trees With Factors.

Memory Usage: 46.9 MB, less than 53.76% of Java online submissions for Binary Trees With Factors.

class Solution {

    private int MOD = (int)(1e9 + 7);

    public int numFactoredBinaryTrees(int[] arr) {

        Arrays.sort(arr);

        // key-number, value-index

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {

            map.put(arr[i], i);

        }

        int sum = 0;

        // dp[i] - number of trees with numbers from arr[0, i]

        int[] dp = new int[arr.length];

        for (int j = 0; j < arr.length; j++) {

            dp[j] = 1;

            for (int i = 0; i <= j; i++) {

                int quotient = arr[j] / arr[i];

                if (quotient < arr[i]) {

                    break;

                }

                if (quotient * arr[i] == arr[j] && map.containsKey(quotient)) {

                    long product = (long)dp[i] * dp[map.get(quotient)] * (i == map.get(quotient) ? 1 : 2) % MOD;

                    dp[j] = (int)(dp[j] + product) % MOD;

                }

            }

            // System.out.printf("dp[%d]=%d\n", j, dp[j]);

            sum = (sum + dp[j]) % MOD;

        }

        return sum;

    }

}

一刷
Version #1 DP
Time O(n^2)
Space O(n)


17.09 %
class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        // key-number, valud-count of possible numFactoredBinaryTrees with root as current number
        Map<Integer, Long> dp = new HashMap<>();
        long mod = (long) (1e9 + 7);
        Arrays.sort(A);
        int len = A.length;
        for (int i = 0; i < len; i++) { // number
            int root = A[i];
            dp.put(root, 1l); // -> number itself can always be a tree
            for (int j = 0; j < i; j++) {
                int left = A[j];
                if (root % left == 0 && dp.containsKey(root / left)) {
                    dp.put(root, (dp.get(root) + dp.get(left) * dp.get(root / left)) % mod);
                }
            }
        }
        long result = 0;
        for (long count : dp.values()) {
            result = (result + count) % mod;
        }
        return (int)result;
    }
}