题目描述
给定一个数组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] | 1 | A[1] | A[2] | A[n - 1] |
| b[1] | A[0] | 1 | A[2] | A[n - 1] |
| ....... | A[0] | A[1] | A[2] | A[n - 1] |
| b[n - 2] | A[0] | A[1] | 1 | A[n - 1] |
| b[n - 1] | A[0] | A[1] | A[2] | 1 |
可以将B[i]分为两部分，左边乘以右边，B[i] = L[i] * R[i];
L[0] = 1,L[i] = L[i - 1] * A[i - 1];
R[n - 1] = 1,R[i] = R[i + 1] * A[i + 1];
这样一写，for循环进行计算的时候就会不写错边界和初始化条件，注意因为不能使用除法，所以L要从0开始往下计算，R要从下往上进行计算。
接下来考虑优化，只用一个vector就可以了，先将左边的遍历一遍，然后从右下角开始直接相乘计算得到结果。
class Solution { public: vector<int> multiply(const vector<int>& A) { if(A.empty()){ return {}; } vector<int> res(A.size(),1); int tmp = 1; for(int i = 1;i < A.size();++i){ tmp *= A[i - 1]; res[i] = tmp; } tmp = 1; for(int i = A.size() - 2;i >= 0;--i){ tmp *= A[i + 1]; res[i] *= tmp; } return res; } };
class Solution { public: vector<int> multiply(const vector<int>& A) { if(A.empty()){ return {}; } vector<int> res(A.size()); vector<int> l(A.size(),1),r(A.size(),1); int ls = 1,rs = 1; //l.push_back(1); for(int i = 1;i < A.size();++i){ ls *= A[i - 1]; l[i] = ls; } for(int i = A.size() - 2;i >= 0;--i){ rs *= A[i + 1]; r[i] = rs; } for(int i = 0;i < A.size();++i){ res[i] = l[i] * r[i]; } return res; } };