[1,2,3,4,5]
[120,60,40,30,24]
[100,50]
[50,100]
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] dp1 = new int[A.length];
int[] dp2 = new int[A.length];
int[] res = new int[A.length];
//动态规划 前后两次 便于理解
dp1[0]=1;
dp1[1]=A[0];
dp2[A.length-1]=1;
dp2[A.length-2]=A[A.length-1];
for(int i=2;i<A.length;i++){
dp1[i]=dp1[i-1]*A[i-1];
}
for(int i=A.length-3;i>=0;i--){
dp2[i]=dp2[i+1]*A[i+1];
}
for(int i=0;i<A.length;i++){
res[i]=dp1[i]*dp2[i];
}
return res;
}
} 
import java.util.ArrayList;
public class Solution {
// 简单暴力
public int[] multiply(int[] A) {
int[] res = new int[A.length];
for(int i =0; i < A.length; i++){
int sum = 1;
for(int j = 0; j < A.length; j++){
if(j==i)
continue;
sum*=A[j];
}
res[i] = sum;
}
return res;
}
} 
public class Solution {
// 简单粗暴 使用前缀和数组
public int[] multiply(int[] A) {
if (A.length == 1) return A;
int[] help = new int[A.length];
int val = 1;
for (int i = 0; i < A.length; i++) {
help[i] = val;
val *= A[i];
}
val = 1;
for (int i = A.length-1; i >=0; i--) {
help[i] *= val;
val *= A[i];
}
return help;
}
} 
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
// 解法2：官方解法
// 分2次for循环，先计算下三角，再计算上三角
int ret[] = new int[A.length];
// 下三角：正序乘
ret[0]=1;
for(int i=1;i<A.length;i++){
ret[i] = ret[i-1] * A[i-1];
}
// 上三角：倒序乘
int product = 1;
for(int i=A.length-2;i>=0;i--){
product *= A[i+1];
ret[i] *= product;
}
return ret;
}
} 
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
if (A.length == 1)
return new int[0];
int[] B = new int[A.length];
//创建数组
for (int i = 0; i < B.length; i++)
B[i] = 1;
//先搞定i左边部分乘积
for (int i = 1; i < B.length; i++)
B[i] = B[i-1] * A[i-1];
int mult = 1;
//再搞定i右边部分乘积
for (int i = B.length-2; i >= 0; i--) {
mult *= A[i+1];
B[i] *= mult;
}
return B;
}
} 
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int lengthA = A.length;
int[] B = new int[lengthA];
for (int i = 0; i < lengthA; i++){
B[i] = 1;
}
for (int i = 1; i < lengthA; i++){
B[i] = B[i-1]*A[i-1];
}
int temp = 1;
for (int j = lengthA - 2; j >= 0; j--){
temp = temp*A[j+1];
B[j] = B[j]*temp;
}
return B;
}
} 
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] ret = new int[A.length];
if(A.length ==0){
return null;
}
int sum = 1;
int count =0;
int flag = -1;
boolean flag1 = false;
for (int i = 0; i < ret.length; i++) {
if(A[i] ==0){
count++;
}
if(count ==1 & !flag1){
flag = i;
flag1 = true;
}
sum*=A[i];
if(count==2){
return ret;
}
}
if(count ==1){
for (int i = 0; i < ret.length; i++) {
if(i!= flag){
ret[i] = 0;
}else{
int max = 1;
for (int i1 = 0; i1 < A.length; i1++) {
if(A[i1] != 0){
max*=A[i1];
}
}
ret[flag] = max;
}
}
return ret;
}
for (int i = 0; i < ret.length; i++) {
ret[i] = sum/A[i];
}
return ret;
}
} 双重循环，外循环从小到大，内循环从大到小。如果两个循环下标相同则跳过即可。
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int res[] = new int[A.length];
for(int i=A.length-1;i>=0;i--){
int sum=1;
for(int j=0;j<A.length;++j){
if(i!=j)sum*=A[j];
}
res[i]=sum;
}
return res;
}
}
/*
构建乘积数组
把结果B[]写为A[]的矩阵，
B[i]的为每行A[i]的乘积，中间凑1。
用B[i]和A[i]的累乘关系，递推。
时间O(n)。
递推：B[i]=B[i-1]*A[i-1]
先保存左下角的结果，右上角的结果可以再声明a=1,b=1来递推
然后再乘到结果里
*/
public int[] multiply(int[] A) {
int n = A.length;
int[] B = new int[n];
B[0] = 1;
//下三角，用A与B的关系递推
//B[i]=B[i-1]*A[i-1]
for(int i = 1;i < n;i++){
B[i] = B[i-1] * A[i-1];
}
//上三角，用a和b来递推
int a = 1,b = 1;
for(int i = n-1;i > 0;i--){
b = a * A[i];
B[i-1] *= b;
a = b;
}
return B;
} 
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
B[0] = 1;
for (int n=1;n<A.length;n++){
B[0] *= A[n];
}
B[A.length-1] = 1;
for (int n=0;n<A.length-1;n++){
B[A.length-1] *= A[n];
}
for (int n=1;n<A.length-1;n++){
B[n] = 1;
for (int i=0;i<A.length;i++){
if (n == i) continue;
B[n] *= A[i];
}
}
return B;
}
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
<分析>： 解释下代码，设有数组大小为5。 对于第一个for循环 第一步：b[0] = 1; 第二步：b[1] = b[0] * a[0] = a[0] 第三步：b[2] = b[1] * a[1] = a[0] * a[1]; 第四步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2]; 第五步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3]; 然后对于第二个for循环 第一步 temp *= a[4] = a[4]; b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4]; 第二步 temp *= a[3] = a[4] * a[3]; b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3]; 第三步 temp *= a[2] = a[4] * a[3] * a[2]; b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2]; 第四步 temp *= a[1] = a[4] * a[3] * a[2] * a[1]; b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1]; 由此可以看出从b[4]到b[0]均已经得到正确计算。 class Solution { public: vector<int> multiply(const vector<int>& A) { vector<int> vec; int sz=A.size(); if(sz==0) return vec; vec.push_back(1); for(int i=0;i<sz-1;i++) vec.push_back(vec.back()*A[i]); int tmp=1; for(int i=sz-1;i>=0;i--) { vec[i]=vec[i]*tmp; tmp=tmp*A[i]; } return vec; } };