剑指offer：构建乘积数组
2021-02-11 18:18
标签：lock 部分 思路 技术 code 重复 alt block tip 给定一个数组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];） 通过题意可知：B[i] = A[0]累乘到A[n-1] / A[i]，但是题意要求不能使用除法。 将每层的数组分为两部分，【0，i）与（i，len-1】，将两部分进行累乘计算。 但是每层都要重复计算大部分相同的值，唯一区别在于A【i】的不同。 以对象线为分界线，将数组分成两部分：左下角与右上角。分别对下三角和上三角进行求解。 下三角：Bn=Bn-1 * An-1 上三角：从n-2向上计算。 剑指offer：构建乘积数组 标签：lock 部分 思路 技术 code 重复 alt block tip 原文地址：https://www.cnblogs.com/le-le/p/12733929.html题意描述
解题思路
一、双层循环
public int[] multiply(int[] A) {
int[] B = new int[A.length];
if (A == null || A.length == 0) return B;
int len = A.length;
for (int i = 0; i 二、巧解法
public int[] multiply(int[] A) {
int[] B = new int[A.length];
if(A==null||A.length==0){
B[0]=1;
//计算下三角
for (int i = 1; i =0; i--) {
temp=temp*A[i+1];
B[i]=B[i]*temp;
}
}
return B;
}