给定一个数组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];）
class Solution { public: // B就像是对角线上为1，其他数据为Ai的矩阵的横向乘积 // 可以看作是两个三角矩阵，Bi分为两部分 Ci 和 Cj Ci 为 0 -> i-1 Cj 为 i+1->n vector<int> multiply(const vector<int>& A) { vector<int> ci; vector<int> cj; vector<int> B; ci.push_back(1); cj.push_back(1); int size = A.size(); for(int i = 1; i < size - 1; i++){ int c = ci[i-1] * A[i]; ci.push_back(c); } for(int i = size - 1; i > 0; i--){ int c = cj[size - i - 1] * A[i]; cj.push_back(c); } B.push_back(cj[size - 1]); for(int i = 0; i < size - 1; i++){ ci[i] = ci[i] * cj[size - i - 1 - 1]; B.push_back(ci[i]); } return B; } };
