[剑指offer] 构建乘积数组

题目描述

给定一个数组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[i]的值可以看作图中矩阵第 i 行所有元素的乘积。我们可以先算下三角中的连乘,即我们先算出B[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。

参考代码

public class Solution {
    public int[] multiply(int[] A) {
        if(A.length <= 1)
            return A;
        int [] B = new int[A.length];
        B[0] = 1;
        for(int i = 1; i < A.length; i++){
            B[i] = B[i-1] * A[i-1];
        }
        int temp = 1;
        for(int j = A.length - 2; j>=0; j--){
            temp *= A[j+1];
            B[j] *= temp;
        }
        return B;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/multiply/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GopherCoder

Python 强化训练:第二篇

17150
来自专栏丁科的专栏

pytorch 学习笔记之编写 C 扩展

在之前的文章中,我们已经了解了如何自定义 Module。这篇主要讲解pytorch利用 CFFI 进行 C 语言扩展。包括两个基本的步骤(docs):编写 C ...

1K00
来自专栏一“技”之长

一个移动开发者的Mock数据之路 原

    在前端开发中,很大一部分工作都是将后台数据获取到后展示在前端界面上。如果接口是现成的,这个过程还相对容易一些,但是如果接口的开发和前端开发是同时进行的,...

7710
来自专栏mathor

LeetCode130. 被围绕的区域

 bfs题,主函数中枚举每一个起点,如果是'O'就开始bfs搜索,首先将'O'变为'X',然后将周围是'O'都入队。这里有个地方要注意,如果'O'并不是被...

10620
来自专栏云时之间

深度学习与神经网络:制作数据集,完成应用(1)

22440
来自专栏Golang语言社区

Golang语言--计算运行的时间

函数time.Since() 计算golang运行的时间是非常有用的性能衡量指标,特别是在并发基准测试中。下面将介绍如何简单地使用Go语言来计算程序运行的时间。...

36480
来自专栏应兆康的专栏

100个Numpy练习【1】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

583150
来自专栏AI研习社

将 Tensorflow 图序列化以及反序列化的巧妙方法

将类中的字段和 graph 中的 tensorflow 变量进行自动绑定,并且在不需要手动将变量从 graph 中取出的情况下进行重存,听起来有没有很炫酷?

16440
来自专栏C/C++基础

Linux命令(12)——wc命令

(3)从文件读取输入文件名。如果有多个文件名,并且希望 wc 从一个文件中读取它们,那么使用-files0-from 选项。这里将文件名称必须以NULL字符结束...

11510
来自专栏生信小驿站

R 热图绘制heatmap②

12240

扫码关注云+社区

领取腾讯云代金券