跟着姚桑学算法-构建乘积数组

题. 构建乘积数组

给定一个数组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]。

不能使用除法。

数据范围
输入数组长度 [0,20]。

样例

输入：[1, 2, 3, 4, 5]

输出：[120, 60, 40, 30, 24]

思考题：

• 能不能只使用常数空间？（除了输出的数组之外）

【题解】--- 动态规划

方法一：动态规划

动态规划算法 的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。

同时，要牢记动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。

这道题可以用两个数组left和right，left[i]=A[0]*A[1]*…*A[i-1], left[i]=A[i-1]*left[i-1]; right[i] = A[i+1]*A[i+2]*…*A[n-1]，则right[i]=A[i+1]*right[i+1]。

最后结果B[i]=left[i]*right[i]。

方法二：

还可以对于A中第i位，设置两个指针j1 = i - 1，j2 = i + 1. 让两个指针同时往两侧走，直到两侧都到达边界为止，将乘积压入B.

复杂度分析：

时间复杂度由于需要遍历数组，复杂度为O(n)。

C++代码实现：

class Solution{
    public:
        int add(int num1,int num2){
            while(num2){
                int x=num1^num2;
                int y=(num1&num2)<<1;
                num1=x;
                num2=y;
            }
            return num1;
        }
}

// 方法二
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        for(int i = 0; i < A.size();i++)
        {  int j1 = i - 1, j2 = i + 1;
           int res = 1;
           while(j1 >= 0 || j2 < A.size())
           {
               if(j1 >= 0) res = res*A[j1];
               if(j2 < A.size()) res = res*A[j2];
               j1--;
               j2++;
           }
           B.push_back(res); 
        }
        return B;
    }
};