【LeetCode】剑指 Offer 66. 构建乘积数组 p312 -- Java Version

题目链接:https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/

1. 题目介绍(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]。不能使用除法。

【测试用例】:
>
【条件约束】:
在这里插入图片描述

2. 题解

2.1 乘积矩阵 – O(n) ⭐

时间复杂度O(n),空间复杂度O(1)
在这里插入图片描述

解题思路】:
除法: 如果没有不能使用除法的限制,我们则可以使用公式 (A[0] * A[1] * ... * A[n-1] ) / A[i] 来求得 B[i];在使用除法时,只需要注意 A[i] 等于 0 的情况即可。
……
乘积数组:我们可以将 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] 分成两部分,一部分定义为 C[i] = A[0]×A[1]×...×A[i-1] = C[i-1] ×A[i-1];另一部分定义为 D[i] = A[i+1]×…×A[n-1] = D[i+1] × A[i+1]。那么我们就得到了 B[i]= C[i] ×D[i]
……
实现策略】:

  1. 首选获取输入数组的长度 len1,进行无效输入的判断;
  2. 定义数组 B, 用来存储返回结果;
  3. 第一次循环,让 B[i] 累乘为 C[i];
  4. 第二次循环,让 B[i] 累乘为 C[i] * D[i]
  5. 最后返回结果。
class Solution {
    // Solution1:B[i] = C[i] * D[i];
    // C[i] = A[0] * ... * A[i-1];
    // D[i] = A[i+1] * ... * A[n-1];
    public int[] constructArr(int[] a) {
        int len1 = a.length;  // 获取数组A的长度
        if (len1 <= 0) return new int[0];  // 无效输入判断
        int[] b = new int[len1];  // 定义数组B,用来存储返回结果

        b[0] = 1;
        for (int i = 1; i < len1; i++) {  // 累乘让 B[i] = C[i]
            b[i] = b[i-1] * a[i-1];
        }

        int temp = 1;
        for (int j = len1-2; j >= 0; j--) {  // 累乘 让 C[i] * D[i]
            temp *= a[j+1];
            b[j] *= temp;
        }

        return b;
    }
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/13629.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

System V 共享内存

System V 共享内存 共享内存是什么如何使用共享内存ftokshmgetshmatshmdtshmctl 共享内存的原理共享内存实现两个进程间通信共享内存的特点共享内存与管道配合使用两个进程间通信多个进程间通信 共享内存是什么 &#x1f680;共享内存是最快的IPC形式。一旦这样的内存映射到共…

网络工程师的水平检测1

水平测试 文章目录 水平测试填空题&#xff08;11分&#xff09;判断题&#xff08;9分&#xff09;选择题&#xff08;8分&#xff09;简答题&#xff08;26分&#xff09;子网划分&#xff08;24分&#xff09;实验拓扑&#xff08;19分&#xff09;填空题&#xff08;5分&am…

【MySQL】数据库完整性和安全性

目录 一、完整性 1.概念 2.sql语言支持的两种约束 2.1静态约束 撤销追加约束 断言 2.3动态约束 触发器 二、安全性 用DBMS对数据库实现的两个特性 一、完整性 1.概念 指dbms保证的db的一种特性&#xff0c;在任何情况下的正确性、有效性、一致性 原理图 广义完整性&…

园区路线地图指引图怎么画?园区地图三维图怎么画?

目前在园区信息化应用形式中&#xff0c;广泛缺乏专业电子地图的使用&#xff0c;因此&#xff0c;使这种高效的信息化工具的应用受到了很大限制。有些仅以图片代替&#xff0c;但图片没有空间计算、检索、路径设计的能力&#xff0c;在地图应用形式中&#xff0c;使用价值很低…

Day953.以假设驱动为指引 -遗留系统现代化实战

以假设驱动为指引 Hi&#xff0c;我是阿昌&#xff0c;今天学习记录的是关于以假设驱动为指引的内容。 很多人在做遗留系统现代化的时候呢&#xff0c;总觉得它是一个十分复杂的技术问题。 本来嘛&#xff0c;无论是代码的重构、架构的拆分&#xff0c;还是 DevOps 平台的搭…

除了学历,你更需要有能力

遥想当年&#xff0c;家里培养出一个大学生&#xff0c;是多荣耀的事&#xff01;可现今却处于一个比较尴尬的状态。 为什么大学生贬值得这么厉害&#xff1f;其实大学生之所以会不值钱不外乎三大原因&#xff1a;量大、与企业需求不匹配、质量差。 高校扩招下&#xff0c;大…

Python每日一练(20230423)

目录 1. 删除链表的倒数第 N 个结点 &#x1f31f;&#x1f31f; 2. 最小覆盖子串 &#x1f31f;&#x1f31f;&#x1f31f; 3. 二叉树的层序遍历 &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏…

Java核心技术 卷1-总结-11

Java核心技术 卷1-总结-11 Java 集合框架将集合的接口与实现分离Collection接口迭代器泛型实用方法集合框架中的接口 Java 集合框架 将集合的接口与实现分离 Java集合类库将接口&#xff08;interface&#xff09;与实现&#xff08;implementation&#xff09;分离。 例如队…

小航助学答题系统编程等级考试scratch一级真题2023年3月(含题库答题软件账号)

青少年编程等级考试scratch真题答题考试系统请点击 电子学会-全国青少年编程等级考试真题Scratch一级&#xff08;2019年3月&#xff09;在线答题_程序猿下山的博客-CSDN博客_小航答题助手 1.下列说法不正确的是&#xff1f;&#xff08; &#xff09; A.可以从声音库中随机…

使用buildroot编译完整系统【IMX6ULLPRO】

目录 构建 IMX6ULL Pro 版的根文件系统 编译系统 ​编辑 镜像文件 构建 IMX6ULL Pro 版的根文件系统 配置文件说明 编译系统 下面以 100ask_imx6ull_pro_ddr512m_systemV_qt5_defconfig 配置文 件为例&#xff0c;在 ubuntu 终端上说明 Buildroot 的配置过程&#x…

抖音数字人主播app

抖音数字人主播app是指一款利用计算机生成的虚拟数字人&#xff0c;在抖音平台上进行实时音视频传输和互动的应用程序。该软件可以让用户创建自己的虚拟数字人&#xff0c;并在抖音平台上进行实时互动和交流。 抖音数字人主播app通常需要包含以下功能&#xff1a; 3D建…

前端学习之路 来自前端方向学生的总结

恭喜您&#xff01;您发现了宝藏&#xff01; 我发现很多小伙伴&#xff0c;对于前端感兴趣&#xff0c;也很想去学好&#xff0c;但是却无从下手&#xff0c;不知道如何去学习。作为一名现处于大三即将大四的学生&#xff0c;借此机会来分享分享我的前端学习之路&#xff01;…

Visual Instruction Tuning: 用LLaVA近似多模态GPT-4

©Paperweekly 原创 作者 | Chunyuan Li 使用 GPT-4 进行视觉指令学习&#xff01;Visual Instruction Tuning with GPT-4! ▲ Generated by GLIGEN (https://gligen.github.io/): A cute lava llama and glasses 我们分享了 LLaVA (Language-and-Vision Assistant)&#…

设计模式--单例模式

目录 介绍 单例模式的八种实现方式 饿汉式(静态常量) 优缺点说明: 饿汉式(静态代码块) 优缺点说明 懒汉式(线程不安全) 优缺点说明 懒汉式(线程安全 同步方法) 优缺点说明 懒汉式(线程安全 同步代码块) 优缺点说明 双重检查 优缺点说明 静态内部类 优缺点说明 …

打怪升级之FPGA组成原理(LE部分)

FPGA芯片逻辑单元的原理 不论你使用哪一款FPGA芯片&#xff0c;其核心可编程逻辑单元都是从一段内存种按顺序读取执行并执行的过程。具体来说&#xff0c;FOGA芯片内部包括可编程逻辑块(LAB)、可配置输入输出单元(IOE)、时钟管理模块、嵌入式RAM(BRAN&#xff0c;在Cyclone IV…

PNAS: 这些病毒是原生动物基因组中的偷渡者

在对复杂单细胞微生物进行大规模研究时&#xff0c;奥地利因斯布鲁克大学生态学系的Christopher Bellas博士、Marie-Sophie Plakolb和Ruben Sommaruga教授发现了一个意外情况&#xff1a;微生物的基因组中找到超过30,000种先前未知的病毒DNA。这种“隐藏”的DNA可能允许宿主细胞…

字节跳动正式开源分布式训练调度框架 Primus

动手点关注 干货不迷路 项目地址&#xff1a;https://github.com/bytedance/primus 随着机器学习的发展&#xff0c;模型及训练模型所需的数据量越来越大&#xff0c;也都趋向于通过分布式训练实现。而算法工程师通常需要对这些分布式框架涉及到的底层文件存储和调度系统有较深…

基于 多态 的职工管理系统(Staff Management System)

目录 一、管理系统需求 作用&#xff1a;管理公司内所有员工的信息 分类&#xff1a;要显示每位员工的编号、姓名、岗位与职责 具体实现的功能&#xff1a; 二、创建管理 类 三、各个接口函数 1、菜单展示功能 2、 选择功能 3、创建员工功能 ①普通员工employee ②经理…

怎么批量把heic格式转化jpg,3招快速解决

怎么批量把heic格式转化jpg&#xff1f;heic是一种新型的图像文件格式&#xff0c;是苹果独家搞出来的一个图片格式&#xff0c;它小巧玲珑&#xff0c;而且图像质量超好&#xff0c;专门给iOS11系统用户用的。这种格式比老JPEG更厉害&#xff0c;不仅图片质量好&#xff0c;而…

【网络原理】应用层协议 与 传输层协议

✨个人主页&#xff1a;bit me&#x1f447; ✨当前专栏&#xff1a;Java EE初阶&#x1f447; 目 录 &#x1f3c9;一. 应用层协议⚾️二. 传输层协议&#x1f452;1. UDP 协议&#x1f302;2. 校验和&#x1f453;3. TCP 协议 &#x1f3c9;一. 应用层协议 我们自己写的应用…