LeetCode 剑指 Offer 66. 构建乘积数组 (动态规划,表格分区)

原题链接

class Solution {
    /**
     * 动态规划
     *      left[i] 为 a[i] 左边元素的乘积 (不包含 a[i])
     *      right[i] 为 a[i] 右边元素的乘积 (不包含 a[i])
     *      则结果 res[i] = left[i] * right[i]
     *      
     * @param a
     * @return
     */
    public int[] constructArr(int[] a) {
        int len = a.length;

        int[] left = new int[len];

        if (len <= 1) return left;

        int[] right = new int[len];

        left[0] = 1;
        for(int i = 1; i < len; i++){
            left[i] = left[i - 1] * a[i - 1];
        }

        right[len - 1] = 1;
        for(int i = len - 2; i >= 0; i--){
            right[i] = right[i + 1] * a[i + 1];
            left[i] *=  right[i];
        }

        return left;
    }
}
上一篇:mruby实战-001


下一篇:新手必备:JavaScript 、常用算法 资料汇总66篇