当前位置:网站首页>【剑指 Offer】66. 构建乘积数组
【剑指 Offer】66. 构建乘积数组
2022-07-05 16:22:00 【LuZhouShiLi】
剑指 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]。不能使用除法。
思路
https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
- 初始化一个数组和原数组一样,b[0] = 1,声明一个辅助变量tmp = 1
- 计算b[i]的下三角各个元素的乘积,直接乘入b[i]
- 计算b[i]的上三角各元素的乘积,记为tmp,并乘入b[i]
- 返回b
代码
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int length = a.size();
if(length == 0)
{
return {
};
}
vector<int> b(length,1); // 声明一个长度为length的向量 初始值都是1
b[0] = 1;
int tmp = 1;
// 自上而下计算下三角矩阵
//
for(int i = 1; i < length; i++)
{
b[i] = b[i - 1] * a[i - 1];
}
for(int i = length -2; i >= 0; i--)
{
tmp *= a[i + 1];// 必须声明一个临时变量进行存储 不可以是 b[i] *= a[i+1]
b[i] *= tmp;
}
return b;
}
};
边栏推荐
- Raspberry pie 4B installation pytorch1.11
- Jarvis OJ shell流量分析
- JSON转MAP前后数据校验 -- 自定义UDF
- Cs231n notes (bottom) - applicable to 0 Foundation
- 中间表是如何被消灭的?
- PSPNet | 语义分割及场景分析
- 文件操作--I/O
- "21 days proficient in typescript-3" - install and build a typescript development environment md
- Keras crash Guide
- StarkWare:欲构建ZK“宇宙”
猜你喜欢
If you can't afford a real cat, you can use code to suck cats -unity particles to draw cats
數據訪問 - EntityFramework集成
【刷题篇】鹅厂文化衫问题
文件操作--I/O
Accès aux données - intégration du cadre d'entité
二叉树相关OJ题
Jarvis OJ Telnet Protocol
2020-2022两周年创作纪念日
Solve cmakelist find_ Package cannot find Qt5, ECM cannot be found
Binary tree related OJ problems
随机推荐
Jarvis OJ shell流量分析
美国芯片傲不起来了,中国芯片成功在新兴领域夺得第一名
Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
极坐标扇图使用场景与功能详解
Domestic API management artifact used by the company
[es6] add if judgment or ternary operator judgment in the template string
【729. 我的日程安排錶 I】
Global Data Center released DC brain system, enabling intelligent operation and management through science and technology
WSL2.0安装
Flet教程之 11 Row组件在水平数组中显示其子项的控件 基础入门(教程含源码)
Win11 prompt: what if the software cannot be downloaded safely? Win11 cannot download software safely
Flet tutorial 12 stack overlapping to build a basic introduction to graphic and text mixing (tutorial includes source code)
搜索 正排索引 和 倒排索引 区别
Raspberry pie 4B installation pytorch1.11
JSON转MAP前后数据校验 -- 自定义UDF
DenseNet
帮忙看看是什么问题可以吗?[ERROR] Could not execute SQL stateme
Today's sleep quality record 79 points
[深度学习][原创]让yolov6-0.1.0支持yolov5的txt读取数据集模式
Summary of PHP pseudo protocol of cisp-pte