剑指offer五十一之构建乘积数组
2024-08-26 20:20:00
一、题目
给定一个数组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]=1*A[1]*...*A[n-3]*A[n-2]*A[n-1], B[1]=A[0]*1*...*A[n-3]*A[i-2]*...*A[n-1]。
二、思路
B[i]的值可以看作下图的矩阵中每行的乘积。下三角用连乘可以很容求得,上三角,从下向上也是连乘。此我们的思路就很清晰了,先算下三角中的连乘,即我们先算出B[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。
三、代码
链接:https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46
来源:牛客网 public class Solution {
public int[] multiply(int[] A) {
int length = A.length;
int[] B = new int[length];
if(length != 0 ){
B[0] = 1;
//计算下三角连乘
for(int i = 1; i < length; i++){
B[i] = B[i-1] * A[i-1];
}
int temp = 1;
//计算上三角
for(int j = length-2; j >= 0; j--){
temp *= A[j+1];
B[j] *= temp;
}
}
return B;
}
}
---------------------------------------------
参考链接:
https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46
最新文章
- SLP测试记录
- http - referer
- Java客户端通过Http发送POST请求上传文件到web服务器
- 第十五节,基本数据类型,元组tuple
- 关于下拉框列表不可选择相同值的设置一:当前DOM不可选
- [BZOJ2684][CEOI2004]锯木厂选址
- 多线程系列(四):Task
- Spark MLlib
- faster-rcnn原理讲解
- springboot打成war包找不到文件
- IBase<;T>;
- Houdini技术体系 基础管线(二) :Heightfiled与UE4的无缝导入以及对World Composition的支持
- git clone Failed to connect to 127.0.0.1 port 43213: Connection refused
- log4j2 使用详解
- Java(C#)基础差异-数组
- 解决Mac上adb: command not found问题
- Python Django 前后端数据交互 之 HttpRequest、HttpResponse、render、redirect
- nmap扫描时的2个小经验
- MySQL 数据库的主从配置
- SQL SERVER学习1——数据库概念
热门文章
- 2018.06.30 BZOJ1026: [SCOI2009]windy数(数位dp)
- 2018.08.27 rollcall(非旋treap)
- Git客户端命令总结
- webUploader上传视频,包括上传进度、上传状态、暂停和取消等
- 4) Maven 安装
- c# 点击按选择图片然后展示在richTextBox中
- (求树的直径)Warm up -- HDU -- 4612
- [译]window.onerror事件
- Hbase和Hive的异同
- mssql内存表