[1,2,3,4,5]
[120,60,40,30,24]
[100,50]
[50,100]
//B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
//从左到右算 B[i]=A[0]*A[1]*...*A[i-1]
//从右到左算B[i]*=A[i+1]*...*A[n-1]
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int n=A.size();
vector<int> b(n);
int ret=1;
for(int i=0;i<n;ret*=A[i++]){
b[i]=ret;
}
ret=1;
for(int i=n-1;i>=0;ret*=A[i--]){
b[i]*=ret;
}
return b;
}
};
import java.util.ArrayList;
public class Solution {
int[] multiply(int[] A) {
int len = A.length;
int forword[] = new int[len];
int backword[] = new int[len];
int B[] = new int[len];
forword[0] = 1;
backword[0] = 1;
for(int i = 1;i < len; i++){
forword[i] = A[i - 1]*forword[i-1];
backword[i] = A[len - i]*backword[i - 1];
}
for(int i = 0; i < len; i++){
B[i] = forword[i] * backword[len - i -1];
}
return B;
}
}
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
if(A==null||A.length==0)
return A;
int[] left = new int[A.length];//记录除了自己，左边的乘积
int[] right = new int[A.length];//记录除了自己，右边的乘积
right[A.length-1] = 1;
for(int i = A.length-2;i>=0;i--){
right[i] = right[i+1]*A[i+1];
}
left[0] = 1;
for(int i = 1;i<A.length;i++){
left[i] = left[i-1]*A[i-1];
}
int[] B = new int[A.length];
for(int i = 0;i<A.length;i++){
B[i] = left[i]*right[i];
}
return B;
}
}
public class Solution {
public int[] multiply(int[] A) {
int length = A.length;
int[] B = new int[length];
if(length != 0 ){
B[0] = 1;
//计算下三角连乘
for(int i = 1; i < length; i++){
B[i] = B[i-1] * A[i-1];
}
int temp = 1;
//计算上三角
for(int j = length-2; j >= 0; j--){
temp *= A[j+1];
B[j] *= temp;
}
}
return B;
}
}
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
boolean changed = false;
for(int k = 0; k < B.length; k++){
B[k] = 1;
for(int i = 0; i < A.length; i++){
int temp = 1;
if(i == k){
changed = true;
temp = A[i];
A[i] = 1;
}
B[k] *= A[i];
if(changed){
A[i] =temp;
changed = false;
}
}
}
return B;
}
} 
public class Solution {
public int[] multiply(int[] A) {
int len = A.length;
int[] lefts = new int[len];
int[] rights = new int[len];
lefts[0] = lefts[len-1] = rights[0] = rights[len-1] = 1;
int l = 1;
int r = 1;
for (int i=1; i<len; i++){
lefts[i] = A[i-1]*lefts[i-1];
}
for (int i=len-2; i>=0; i--){
rights[i] = A[i+1]*rights[i+1];
}
int[] B = new int[len];
while (len>0){
len--;
B[len] = lefts[len]*rights[len];
}
return B;
}
} 
public static int[] multiply(int[] A) {
if(A == null){
return null;
}
int len = A.length;
int[] forword = new int[len];
int[] back = new int[len];
int[] B = new int[len];
forword[0] = 1;
back[len - 1] = 1;
for(int i = 1; i < len; i++){
forword[i] = A[i - 1] * forword[i - 1];
}
for(int i = len - 2; i >= 0; i--){
back[i] = A[i + 1] * back[i + 1];
}
for(int i = 0; i < len; i++){
B[i] = forword[i] * back[i];
}
return B;
}
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int n=A.size();
int k=n;
vector<int> b;
vector<int> c;
for(int i=0;i<n;i++){
c.push_back(A[i]);
}
for(int i=0;i<n;i++){
b.push_back(1);
}
for(int i=0;i<n;i++){
c[i]=1;
k=n;
for(int j=0;j<n;j++){
b[i]*=c[j];
}
c[i]=A[i];
}
return b;
}
};
import java.util.ArrayList;
public class Solution {
// ---------------------
// B0 | 1 | A1 | A2 | A3 |
// ---------------------
// B1 | A0 | 1 | A2 | A3 |
// ---------------------
// B2 | A0 | A1 | 1 | A3 |
// ---------------------
// B3 | A0 | A1 | A2 | 1 |
// ---------------------
//以上面的4*4数组为例
//B0 = A1*A2*A3,B1 = A0*A2*A3,B2 = A0*A1*A3,B3 = A0*A1*A2
//第一轮，先算左下角的元素，即
//B0 = 1,B1 = A0,B2 = A0*A1,B3 = A0*A1*A2
//第二轮，再端右上角的元素，即
//B2 = A0*A1* A3(temp=A3),B1 = A0* A2*A3(temp=A3*A2),B0 = A1*A2*A3(temp=A3*A2*A1)
public int[] multiply(int[] A) {
int length = A.length;
int[] B = new int[length];
if(length != 0){
B[0] = 1;
for(int i=1;i<length;i++){
B[i] = B[i-1]*A[i-1];
}
int temp = 1;
for(int j=length-2;j>=0;j--){
temp *= A[j+1];
B[j] *= temp;
}
}
return B;
}
} 
class Solution
{
public:
vector<int> multiply(const vector<int>& A)
{
/* vector<int> B;//直接暴力解决，逐行遍历，然后逐个相乘
if (!A.empty())
{
int n = A.size();
for (int i = 0; i <= n - 1; i++)
{
int mult = 1;
for (int j = 0; j <= n - 1; j++)
{
if (j != i)
mult *= A[j];
}
B.push_back(mult);
}
}
return B;*/
vector<int> B;//剑指offer思路，总结规律，使用递推公式求解
if (!A.empty())
{
int n = A.size();
vector<int> C, D;
B.assign(n, 1);
C.assign(n, 1);
D.assign(n, 1);
if (n > 1)
{
C[1] = A[0];
D[n - 2] = A[n - 1];
}
for (int i = 2; i <= n - 1; i++)
C[i] = C[i - 1] * A[i - 1];
for (int i = n - 3; i >= 0; i--)
D[i] = D[i + 1] * A[i + 1];
for (int i = 0; i < n; i++)
B[i] = C[i] * D[i];
}
return B;
}
};
int sumF = 1,sumB = 1,n = A.size();
vector<int> B(n,1);
for(int i = 0;i <n;i++)
{
B[i] *= sumF;//前半部分
B[n- i -1] *= sumB;//后半部分
sumF *= A[i];//标记从前往后累乘
sumB *= A[n-i-1];//标记从后往前累乘
} # -*- coding:utf-8 -*- class Solution: def multiply(self, A): import copy # write code here B=[1]*len(A) for i in range(len(A)): C=copy.copy(A) C.pop(i) for j in range(len(C)): B[i]*=C[j] return B
/*复杂度O(n)*/
int[] multiply(int[] A) {
int length = A.length;
int[] B = new int[length];
if(length <= 0)
return B;
int[] before = new int[length];
int[] after = new int[length];
before[0] = 1;
after[0] = 1;
for(int i = 0 ; i < length; i ++){
if(i > 0)
before[i] = before[i-1]*A[i-1];
if(i < length-1)
after[i+1] = after[i]*A[length-i-1];
}
for(int i = 0; i < length; i ++){
B[i] = before[i]*after[length-i-1];
}
return B;
}
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int len=A.length;
int[] b=new int[len];
for(int i=0;i<len;i++){
b[i]=1;
for(int j=0;j<len;j++){
if(j==i) continue;
b[i]*=A[j];
}
}
return b;
}
} 
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int n = A.size();
vector<int> B(n, 1);
vector<int> C(n, 1);
vector<int> D(n, 1);
for(int i = 1; i < n; ++i){
C[i] = C[i-1]*A[i-1];
D[i] = D[i-1]*A[n-i];
}
for(int i = 0; i < n; ++i)
B[i] = C[i]*D[n-1-i];
return B;
}
}; 
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> vec;
vec.push_back(1);
for(int i=1;i<A.size();i++)
{
int temp=A[i-1]*vec[i-1];
vec.push_back(temp);
}
int temp=1;
for(int i=A.size()-2;i>=0;--i)
{
temp =temp*A[i+1];
vec[i]=vec[i]*temp;
}
return vec;
}
};
public: vector<int> multiply(const vector<int>& A) { vector<int> B; int length = A.size(); if(length==0) return B; B.push_back(1); for(int i=0;i<length-1;++i) { B.push_back(B.back()*A[i]); } int temp = 1; for(int i=length-2;i>=0;--i) { temp *= A[i+1]; B[i] *=temp; } 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; } };