时间：2020-07-01 题目： 给定一个数组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]分成左右两部分，假设：
left[i] = A[0]*...*A[i-1] right[i] = A[i+1]*...*A[n-1]所以：
B[i] = left[i] * right[i]这样就避免使用了除法。但是如果对每个B[i], 0<=i<n,都这么求，显然时间复杂度太高。我们把整个结果画到下面矩阵中，left和right相当于矩阵的上、下三角阵： 可得到递推公式：（动态规划）
left[i+1] = left[i] * A[i] right[i] = right[i+1] * A[i+1]所以，我们可以先正向把left[i]求出，然后倒向把所有的right[i]求出。
Java代码：
/** * @author LiMin * @Title: Multiply * @Description: 给定一个数组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];） * @date 2020/7/1 16:19 */ public class Multiply { public int[] multiply(int[] A) { int[] B = new int[A.length]; if (A.length == 0) return B; B[0] = 1; for (int i = 1; i < A.length; i++) { B[i] = B[i - 1] * A[i - 1]; } int temp = 1; for (int i = A.length - 2; i >= 0; i--) { temp = temp * A[i + 1]; B[i] *= temp; } return B; } }