二级网站怎么建设/在哪个网站可以免费做广告

剑指 Offer 66. 构建乘积数组 - 力扣（LeetCode）

应该是不可以暴力两层循环的吧。。

不能用除法。

观察一下，结果数组每个位置的值等于它的两边的所有元素的乘积，那么使用两次遍历：

第一次从左到右，这样每一个位置都会变为该位置之前的所有元素的乘积；

第二次从右到左，这样将上一步的乘积再累乘每个位置右边的元素的乘积就可以了。

class Solution {
public:vector<int> constructArr(vector<int>& a) {if(a.empty())   return vector<int>();vector<int> res(a.size(), 0);int val = 1;//一定要初始化为1for(int i = 0; i < a.size(); ++i){res[i] = val;val *= a[i];}val = 1;for(int i = a.size()-1; i >= 0; --i){res[i] *= val;val *= a[i];}return res;}
};

这位大佬的ppt就很灵性;面试题66. 构建乘积数组（表格分区，清晰图解） - 构建乘积数组 - 力扣（LeetCode）

优化一下：

class Solution {
public:vector<int> constructArr(vector<int>& a) {if(a.empty())   return vector<int>();vector<int> res(a.size(), 1);for(int i = 1; i < a.size(); ++i){res[i] = res[i-1]*a[i-1];}int val = 1;for(int i = a.size()-2; i >= 0; --i){val *= a[i+1];res[i] *= val;}return res;}
};