【剑指offer】不使用除法,构建乘积数组,C++实现
# 题目
# 思路
设C[i] = A[0] * A[1] * … * A[i-1],D[i] = A[i+1] * … * A[n-1],则C[i]按照从上到下的顺序计算,即C[i] = C[i-1] * A[i-1]。D[i]按照从下而上的顺序计算,即D[i] = D[i+1] * A[i+1] 。由C[i] 和 D[i]可以退出计算B[i]的公式,即B[i] = C[i] * D[i] = C[i-1] * A[i-1] * D[i+1] * A[i+1] 。
# 代码
#include <iostream> #include <vector> using namespace std; // 构建乘积数组 class Solution { public: vector<int> multiply(const vector<int>& A) { // 存储结果 int n=A.size(); vector<int> b(n); // 计算结果 int ret; ret = 1;// 存储C[i] for(int i=0;i<n;ret*=A[i++]){ b[i]=ret; } ret = 1;// 存储D[i] for(int i=n-1;i>=0;ret*=A[i--]){ b[i]*=ret; } return b; } }; int main() { const vector<int> a = {1,2,3,4,5}; Solution solution; solution.multiply(a); return 0; }
相关推荐
IT之家 2020-03-11
graseed 2020-10-28
zbkyumlei 2020-10-12
SXIAOYI 2020-09-16
jinhao 2020-09-07
impress 2020-08-26
liuqipao 2020-07-07
淡风wisdon大大 2020-06-06
yoohsummer 2020-06-01
chenjia00 2020-05-29
baike 2020-05-19
扭来不叫牛奶 2020-05-08
hxmilyy 2020-05-11
黎豆子 2020-05-07
xiongweiwei00 2020-04-29
Cypress 2020-04-25
冰蝶 2020-04-20