锻练编程思维——每日一题：《剑指offer》构建乘积数组

喜欢ヅ旅行 2023-02-12 08:27 36阅读 0赞

### 目录 ###

*   *  审题
     *  思路拆解：

## 审题 ##

> 题目描述  
> 给定一个数组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]。`不能使用除法。（注意：规定B\[0\] = A\[1\] \* A\[2\] \* … \* A\[n-1\]，B\[n-1\] = A\[0\] \* A\[1\] \* … \* A\[n-2\];）

*  提炼信息：  
    ①给定一个数组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]。`  
    ③不能使用除法。（咱目前也不知道怎么用除法来写这道题）  
    ④`注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];`
 *  思路：  
    分治法——  
    **正序计算（正着算B\[0~n-1\]）**`A[0]*A[1]*...*A[i-1]`这一堆乘积然后赋值给B\[i\]，  
    **逆序计算（倒着算B\[n-1~0\]）**`A[i+1]*...*A[n-1]`这一对乘积然后用B\[i\]\*=这些乘积  
    先算正着算的那堆乘积，再算逆着算的那堆乘积。  
    **这是大体思路。**

## 思路拆解： ##

先分析正序计算（正着算B\[0~n-1\]）`B[i]=A[0]*A[1]*...*A[i-1]`这一堆乘积然后赋值给B\[i\]这一分治出的目标。

*  我们先在纸上推算得出B\[0\],B\[1\],B\[2\],…,B\[n-1\]应该等于什么  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]
 *  考虑到规定B\[0\]= `A[1] * A[2] * ... * A[n-1]`，而正序计算的一堆乘积满足不了B\[0\]应得的值，**所以我们不妨让B\[0\]=1**
 *  通过以上规律，你想一下是不是需要找一个**变量存储并迭代A数组部分元素的乘积**，这个变量在存储迭代A数组元素的同时还要把它迭代一次又一次的A数组元素乘积赋值给B数组元素。
 *  由于有迭代，而且要先算出B数组每个元素的一部分值（对应的`A[0]*A[1]*...*A[i-1]`），我们不难想到要用for循环来完成这件事，于是得到一块**核心代码**：

for(int i=0;i<n-1;i++)
    {
        
    	//n是A数组的长度，同样也作为B数组的长度（下面会提及怎么获取两个数组的长度）
    	B[i]=temp;//这里temp作为一个变量存储并迭代A数组部分元素的乘积，
    	//在存储迭代A数组部分元素的同时
    	//还要把它迭代一次又一次的A数组部分元素的乘积赋值给B数组元素。
    	//temp在这个for循环前要赋值1以让全部B数组元素的部分乘积值正确，
    	//同时为下面将分析出的for循环并得出B[0]的最终乘积值做个铺垫。
    	temp*=A[i];//存储并迭代A数组部分元素的乘积
    }

*  你或许会好奇这个temp应该在定义的时候初始化吗？初始化为多少？为什么不在for里头定义temp？  
    先往下看，不要急，后面的解释你会懂的。

再分析逆序计算（倒着算B\[n-1~0\]）`A[i+1]*...*A[n-1]`这一对乘积然后用B\[i\]\*=这些乘积 这一分治出的目标

*  纸上推算由B\[i\]\*=`A[i+1]*...*A[n-1]`得出的**每一个B数组元素的最终乘积**。因为我们分析的逆序计算，所以最好先推B\[n-1\]的最终乘积，然后B\[n-2\]这样以此类推  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]
 *  我们推出来每一个B\[i\]应该得的最终乘积后，提取出每一个后乘到每个B\[i\]的A数组部分元素乘积
 *  可得知**需要一个变量存储并迭代A数组部分元素的乘积**，这个变量在存储迭代A数组部分元素的同时还要把它迭代一次又一次的A数组部分元素乘积赋值给B数组元素。
 *  上面分析正序计算用到的那个temp变量可以再次被使用下来，并且不难想到再用一次for循环，于是得到一块**核心代码**：

for(i=n-1;i>=0;i--)
    {
        
    	B[i]*=temp;//temp在这个for循环前要再次赋值1以让全部B数组元素的最终乘积值正确，也让规定的B[n-1]和B[0]最终乘积值正确。
    	temp*=A[i];
    	//通过纸上推出的从B[n-1]~B[0]全部B数组元素的最终乘积值，
    	//我们就会想到这么写代码
    }

OK，核心代码全部给出，目前我们需要添枝加叶。

*  n首先要定义并且被赋值为A.size()（A数组的长度）
 *  B数组没有被给出，需要自己定义一个和A数组长度相等的B数组（名称为B的vector容器）
 *  temp定义并初始化为1，在第一次for循环后第二次for循环前再被赋值为1
 *  return B写上  
    得出最终代码

class Solution {
        
    public:
        vector<int> multiply(const vector<int>& A) {
        
            int n=A.size(),temp;
            vector<int>B(n);//定义vector容器的语法
            temp=1;//理论上temp愿意是多少就是多少，这里为了让B[1]以后的元素都是正确的乘积值
            
            for(int i=0;i<n;i++)
            {
        
                B[i]=temp;
                temp*=A[i];
            }
            temp=1;//以及为了让B[0]、B[n-1]得出其规定的结果
            for(int i=n-1;i>=0;i--)
            {
        
                B[i]*=temp;
                temp*=A[i];
            }
            return B;
        }
    };

如果忘了vector的语法请看这篇博客——[Essential C++学习记录&笔记整理5（如何运用Array和Vector）][Essential C_5_Array_Vector]

好了，这篇题解就讲述完毕，希望大家能听明白，若有错误，欢迎指正！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200525164116617.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052516412979.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[Essential C_5_Array_Vector]: https://blog.csdn.net/weixin_45910408/article/details/105317681