使用 oh-my-zsh

题目描述

给定一个数组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]。不能使用除法。

思路1 减少溢出风险

• 顺序逐个求累积，最后一个不要乘，这样每一个累积都少一个数
• 倒序逐个求累积，逐个乘以逆序累积，少一位

思路1

• 顺序逐个求累积，每个都乘，求总乘积
• 逐个除去当前的元素，剩下的每个元素就是B数组的元素

原始： 2   3   4   5   6
顺序： 1   2   6   24  120
逆序： 360 120 30  6   1
B:    360 240 180 144 120
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> vec;
        int sz=A.size();
        // 异常处理
        if(sz==0)
             return vec;
        vec.push_back(1);
        
        // 顺序累计求乘积，少一个元素
        for(int i=0;i<sz-1;i++)
             vec.push_back(vec.back()*A[i]);
        
        // 倒序累计求乘积
        int tmp=1;
        for(int i=sz-1;i>=0;i--)
        {
              vec[i]=vec[i]*tmp;//少一个元素
              tmp=tmp*A[i];
        }
        return vec;
    }
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com