题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

示例

输入：[1,2,3,4,5]
返回值：[120,60,40,30,24]

算法思路

构建前缀乘积 pre_mul[i] = A[0] * A[1] * …A[i]
构建后缀乘积 suf_mul[i] = A[n-1] * A[n-2] * …A[i]
B[i] = 前缀乘积 * 后缀乘积 B[i] = pre_mul[i-1] * suf_mul[i+1]

注意：
其实仔细想一想，它就是一个动态规划的题目。从代码的层面上看，就会明白我所说的意思了

代码实现

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        //1.构建前缀乘积 pre_mul[i] = A[0]*A[1]*...A[i]
        //2.构建后缀乘积 suf_mul[i] = A[n-1]*A[n-2]*...A[i]
        //3.前缀乘积 * 后缀乘积 B[i] = pre_mul[i-1] * suf_mul[i+1]
        int n = A.length;
        int [] B = new int[n];
        int [] pre_mul = new int[n];
        int [] suf_mul = new int[n];
        
        //1.构建前缀乘积
        pre_mul[0] = A[0];//第一个没有前缀，所以就是它本身
        for(int i=1;i<n;i++){
            pre_mul[i] = pre_mul[i-1] * A[i];
        }
        //2.构建后缀乘积
        suf_mul[n-1] = A[n-1];//最后一个没有后缀，所以就是它本身
        for(int i=n-2;i>0;i--){
            suf_mul[i] = suf_mul[i+1] * A[i];
        }
        //3.前缀乘积 * 后缀乘积
        B[0] = suf_mul[1];
        B[n-1] = pre_mul[n-2];
        for(int i=1;i<n-1;i++){
            B[i] = pre_mul[i-1] * suf_mul[i+1];
        }
        return B;
    }
}