66_构建乘积数组

给定一个数组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]。不能使用除法。
///////////////////////////////////////////////////////////////
class Solution 
{
public:
    vector<int> multiply(const vector<int>& A) 
    {
        int size=A.size();
        vector<int> vec(size);
        vec[0]=1;
        for(int i=1;i<size;++i)
            vec[i]=vec[i-1]*A[i-1];
        
        int temp=1;
        for(int i=size-2;i>=0;--i)
        {
            temp*=A[i+1];
            vec[i]*=temp;
        }
        return vec;
    }
};

///////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////牛客网参考解析1
<分析>：
解释下代码，设有数组大小为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;
    }
};

///////////////////////////////////////////////////////////////牛客网参考解析2
//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;
    }
};