题目内容
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中?B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即?B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
?
示例:
1
2
| 输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
|
提示：
1
2
| 所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
|
解法一：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<int> constructArr(vector<int>& a) {
// dp[i] = dp[i-1] * a[i-1];
// dp[i] = dp[i+1]
if(a.size()<=1)return a;
vector<int> res(a.size()),dp(a.size());
res[0] = 1;
for(int i = 1;i<a.size();i++){
res[i] = res[i-1] * a[i - 1];
}
dp[a.size()-1] =1;
for(int i = a.size()-2;i>=0;i--){
dp[i] = dp[i+1] * a[i+1];
}
for(int i =0;i<a.size();i++){
res[i] *= dp[i];
}
return res;
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
12 ms
, 在所有 C++ 提交中击败了
97.37%
的用户
内存消耗：
24.4 MB
, 在所有 C++ 提交中击败了
33.63%
的用户
通过测试用例：
44 / 44
|
