刷爆力扣之构建乘积数组

刷爆力扣之构建乘积数组

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈
今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

剑指 Offer 66. 构建乘积数组

给定一个数组 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,3,4,5]
输出: [120,60,40,30,24]
1
2

提示：

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

二 🏠破题思路

2.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]

看到这句的时候，各位看官大大应该和博主一样已经笑开了 🌸🌸🌸 吧

但是这道题的核心点是 不能使用除法 😖😖😖

提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃

2.2 🚀 思路整理

如 2.1 所述，该题难点在于不能使用除法，即 只用乘法 生成数组 B

根据题目对 B[i] 的定义，可列表格，如下图所示

根据表格的主对角线（全为 1 ），可将表格分为 上三角 和 下三角 两部分；分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果

三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

std::vector constructArr(std::vector& a) {
	int len = a.size(); //输入数组长度
	std::vector b(len, 1); //初始化输出数组 b
	int left = 1, right = 1; //初始化左右双指针
	for (int i = 0; i < len; ++i) { //遍历输入数组
		b[i] *= left; //left = 索引i位置左边所有数乘积, *= 赋值给 b[i]
		left *= a[i]; //索引i位置左边所有数乘积 * a[i]

		b[len - 1 - i] *= right; //right = 索引len-1-i位置右边所有数乘积, *= 赋值给 b[len-1-i]
		right *= a[len - 1 - i]; //索引len-1-i位置右边所有数乘积* a[len - 1 - i]
	}
	return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

b[i] *= left; //left = 索引i位置左边所有数乘积, *= 赋值给 b[i]
left *= a[i]; //索引i位置左边所有数乘积 * a[i]
1
2

left 是索引 i 位置左边所有数乘积，*= 就是在把索引 i 位置左边所有数乘积赋值给 b[i]

left *= a[i] 为了一下循环（++i）提前计算 i 位置左边所有数乘积

那么这个过程就对应了，2.2 图示中的正三角过程（右部分的倒三角逻辑同理） 🌹🌹🌹

当然也可以使用两次循环，将正倒三角各元素乘积分开计算，在逻辑上或许会更好理解。但却多了一次遍历的开销，这里使用了双指针的操作（凡是等效逻辑正逆向遍历两次，均可使其简化为一次完成） 😜😜😜

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息并没有问题，在第二阶段 🚀 思路整理中有考虑尝试使用双指针，但是未联想到 上三角 和 下三角（破题关键点）😭😭😭

所以博主的这道题是在阅读完官方解析后，解出来并加以记录的

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪