823. 带因子的二叉树 - Kotlin 动态规划+双指针

Problem: 823. 带因子的二叉树

思路

设dp[i]为以arr[i]为根节点能够构建出的二叉树数量，对于任意a、b满足arr[a]*arr[b]==arr[i]，考虑以下两种情况：

• 当a==b时，能够构建出的二叉树数量为dp[a]*dp[b]
• 当a!=b时，能够构建出的二叉树数量为dp[a]*dp[b]*2，因为a和b可以调换左右位置形成一轮新的组合情况，而当a==b时调换左右位置是没有意义的

由于数据范围规定了arr[i]>=2，能够保证满足arr[a]*arr[b]==arr[i]的a和b必定在这个范围中，考虑到后效性，我们将arr进行升序排序，这样当我们遍历到arr[i]时，保证任意索引大于i的元素都不会影响到dp[i]的计算

与此同时，当我们用双指针遍历查找满足arr[a]*arr[b]==arr[i]的a和b时，由于数组是升序排序的，当arr[a]*arr[b]>arr[i]时，右指针继续右移只会让乘积越来越大，可以直接break

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution 
fun Solution.numFactoredBinaryTrees(arr: IntArray): Int {
    val dp = LongArray(arr.size) { 1 }
    arr.sort()
    for ((index, value) in arr.withIndex()) {
        for (left in 0..index) {
            for (right in left..index) {
                if ((arr[left]).toLong() * (arr[right]).toLong() == (value).toLong()) {
                    dp[index] = (dp[index] + dp[left] * dp[right] * (if (left != right) 2 else 1)) % (1e9 + 7).toLong()
                } else if ((arr[left]).toLong() * (arr[right]).toLong() > (value).toLong()) {
                    break
                }
            }
        }
    }
    return (dp.fold((0).toLong()) { sum, value -> (sum + value) % (1e9 + 7).toLong() }).toInt()
}