北京市住房和建设委员会门户网站/百度爱采购平台登录
剑指 Offer 66. 构建乘积数组
难度:middle\color{orange}{middle}middle
题目描述
给定一个数组 A[0,1,…,n−1]A[0,1,…,n-1]A[0,1,…,n−1],请构建一个数组 B[0,1,…,n−1]B[0,1,…,n-1]B[0,1,…,n−1],其中 B[i]B[i]B[i] 的值是数组 AAA 中除了下标 iii 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i−1]×A[i+1]×…×A[n−1]B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]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]
提示:
- 所有元素乘积之和不会溢出 32 位整数
- a.length<=100000a.length <= 100000a.length<=100000
算法
(前缀和)
本题的难点在于 不能使用除法 ,即需要 只用乘法 生成数组 B
。根据题目对 B[i]
的定义,可列表格,如下图所示。
根据表格的主对角线(全为 1
),可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积,即可 不使用除法 就获得结果。
我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案,而是利用索引左侧所有数字的乘积和右侧所有数字的乘积(即前缀与后缀)相乘得到答案。
对于给定索引 i
,我们将使用它左边所有数字的乘积乘以右边所有数字的乘积。下面让我们更加具体的描述这个算法。
复杂度分析
-
时间复杂度:O(n)O(n)O(n),其中 nnn 是数组的长度。
-
空间复杂度 : O(n)O(n)O(n),其中 nnn 是数组的长度。
C++ 代码
class Solution {
public:vector<int> constructArr(vector<int>& a) {if (a.empty()) return vector<int>();int n = a.size();vector<int> b(n, 0);// 左边for (int i = 0, p = 1; i < n; i ++) {b[i] = p;p *= a[i];}//右边for (int i = n - 1, p = 1; ~i; i --) {b[i] *= p;p *= a[i];}return b;}
};
相关文章:

剑指 Offer 66. 构建乘积数组
剑指 Offer 66. 构建乘积数组 难度:middle\color{orange}{middle}middle 题目描述 给定一个数组 A[0,1,…,n−1]A[0,1,…,n-1]A[0,1,…,n−1],请构建一个数组 B[0,1,…,n−1]B[0,1,…,n-1]B[0,1,…,n−1],其中 B[i]B[i]B[i] 的值是数组 AAA…...

1.1 误差的来源
不难发现,考察用计算机解决科学计算问题时所经历的几个环节(如图1-1所示),其中每一步都可能产生误差,首先,数学模型是通过对实际问题进行抽象与简化得到的,它与实际问题之间有误差.数学模型与实…...

python进程间通信
进程间通信表示进程之间的数据交换。 为了开发并行应用程序,需要在进程间交换数据。 下图显示了多个子过程之间同步的各种通信机制 - 各种通信机制 队列 队列可以用于多进程程序。 多处理模块的Queue类与Queue.Queue类相似。 因此,可以使用相同的API…...

麒麟Linux操作系统磁盘策略永久调整为deadline
1.前言在安装数据库,比如达梦数据库时,为获取磁盘最佳性能,一般要将数据磁盘设置为deadline。2. 修改磁盘调度算法2.1临时修改假设磁盘为sda,echo deadline > /sys/block/sda/queue/scheduler2.2通用机永久修改grubby --update-kernelALL …...

yum安装Docker(CentOS7.9)
目录 一、安装环境 编写yum源(根据系统版本) 二、安装docker-ce 默认安装docker-ce是最新版本 ps:安装不成功则需要安装container-selinux,下载网络yum源,再安装docker-ce即可 #查看dcoker-ce所产生的文件路径 三、启动docker 四、配置镜像加速器…...

c++错误 free(): double free detected
记一次bug调试。。。。 我定义了一个类,测试的时候,调用它的方法出现了free(): double free detected ,但是调用其他方法是正常的。这个错误,字面意思就是检测到了双重释放。是指对于同一块内存,释放了两次。 我的类…...

12升400V 升压DC-DC高压脱毛仪解决方案SC3671
ipl(intense pulsed light,强脉冲光)脱毛,也叫光子脱毛,是市场上的一种新型脱毛技术和美容方法,其利用强脉冲光特殊的波长和光热效应实现破坏毛囊并达到永久脱毛的效果,具有速度快,效果好,安全性…...

h264格式分析
h264格式分析一.简介二.h264编码原理1.帧间压缩2.帧内压缩三.编码结构1.IDR帧2.解码顺序四.NALU1.nalu头信息2.annexb模式一.简介 h264是一种视频编码标准,又叫Advanced Video Codec,即AVC 二.h264编码原理 1.帧间压缩 通过I、B、P帧实现帧间压缩 I…...

【数据分析师求职面试指南】实战技能部分
文章目录必备技能数据人员如何创造价值完整的指标体系构建数据监控集报表设计设计一份优质的数据分析报告基于互联网大数据的应用A B 测试用户画像完整的数据挖掘项目流程1. 分析问题,明确目标2.模型可行性分析3.选取模型4.选择变量5.特征工程6.建立模型&效果…...

树与二叉树(二叉树的表示,性质,遍历,还原)
基本术语:A(或B)是I的祖先,I是A(或B)的子孙;D是I的双亲,I是D的孩子;节点的孩子个数称为节点的度;树中节点的最大度数称为树的度;度大于0的节点称为…...

mysql 源码学习理解记录--lock_rec_move
记录源码学习笔记,如有错误,还请帮忙指正。 Lock_rec_move 函数使用场景之用于update Update 匹配条件时会用lock_rec_lock先加锁。然后再进行ha_update_row 操作。 在修改时,当修改的字段前后长度不一致时,会导致不能原地修改…...

markdown(.md)常用语法
markdown(.md)常用语法markdown常用语法常用目录标题分割线格式空格换行无序列表有序列表列表嵌套文字引用行内代码代码块字体转义斜体加粗删除线下划线功能链接todo listtypora插入图片并保存在本地包含了一些常用的MD语法和操作,语法不是很…...

千言数据集赛题介绍
赛题题目 通用信息抽取任务评测 将多种不同的信息抽取任务用统一的通用框架进行描述,着重考察相关技术方面在面对新的、未知的信息抽取任务与范式时的适应和迁移能力。 赛题介绍 信息抽取旨在将非结构化文本中的信息进行结构化,是自然语言处理的基础…...

信息技术最全总结(备考教资)
信息技术 备考教资信息技术知识点总结,欢迎收藏!需要xmind和备考书籍的可以评论区留言。 第一部分-学科专业知识 第一章-信息技术基础知识 信息与信息技术概述 信息概述 信息的定义 信息本身不是实体信息是通过文字、数字、图像、图形、声音、视频等方…...

opencv识别车道线(霍夫线变换)
目录1、前言2、霍夫线变换2.1、霍夫线变换是什么?2.2、在opencv中的基本用法2.2.1、HoughLinesP函数定义2.2.2、用法3、识别车道3.1、优化3.1.1、降噪3.1.2、过滤方向3.1.3、截选区域3.1.4、测试其它图片图片1图片2图片31、前言 最近学习opencv学到了霍夫线变换&am…...

MySQL的同步数据Replication功能
MySQL提供了Replication功能,可以实现将一个数据库的数据同步到多台其他数据库。前者通常称之为主库(master),后者则被称从库(slave)。MySQL复制过程采用异步方式,但延时非常小,秒级…...

2023年全国最新高校辅导员精选真题及答案17
百分百题库提供高校辅导员考试试题、辅导员考试预测题、高校辅导员考试真题、辅导员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 21.完善大学生的自我意识,我们可以采取的措施是()。 …...

中文代码92
PK 嘚釦 docProps/PK 嘚釦諿hl | docProps/app.xml漅Mo?糤?皘幅H??Q州濾mじ沜咅K宩Z5~q矹阶浇?灭貄}鰜>hk?i灐Q墩娲蝊毲b檊!J邮?\鏶 鵉苻牢[?j Y?a漺1簕B傟p悺L睮恃鶤?龎劂Q|瓣} A??苷0???5m?髤咄佶?\/#姧1N_??熹 冟.琽僠糧固Pw襅…...

Python SEO采集海量文本标题,用倒排索引找出“类似的标题“代码实现
Python SEO采集海量文本标题,用倒排索引找出“类似的标题“代码实现 作者:虚坏叔叔 博客:https://xuhss.com 早餐店不会开到晚上,想吃的人早就来了!😄 一、说明 假设这个是采集到的海量文本标题: 现在要判断找到的这个标题 title = "拜登称特朗普拒绝承认选举…...

模型杂谈:快速上手元宇宙大厂 Meta “开源泄露”的大模型(LLaMA)
本篇文章聊聊如何低成本快速上手使用 Meta(Facebook)的开源模型 LLaMA。 写在前面 在积累点赞,兑现朋友提供的显卡算力之前,我们先来玩玩“小号的”大模型吧。我相信 2023 年了,应该不需要再赘述如何使用 Docker 干净…...

RedisCluster集群模式下master宕机主从切换期间Lettuce连接Redis无法使用报错Redis command timed out的问题
背景springboot使用redisTemplate访问redis cluster(三主三从),底层是Lettuce,当其中一个master挂掉后,slave正常升为master,程序报错 Redis commond timed out after 6 seconds。解决手动连接集群…...

Xuetr杀毒工具使用实验(28)
实验目的 (1)学习Xuetr的基本功能; (2)掌握Xuetr的基本使用方法。预备知识 windows操作系统的基本知识如:进程、网络、服务和文件等的了解。 XueTr是近年推出的一款广受好评的ARK工具。ARK工具全称为Anti R…...

fastapi(https)+openssl+测试(双向校验)
第一步生成根证书 # Generate CA private key openssl genrsa -out ca.key 2048 # Generate CSR openssl req -new -key ca.key -out ca.csr # Generate Self Signed certificate(CA 根证书) openssl x509 -req -days 365 -in ca.csr -signkey ca.key -o…...

TiDB Server
文章目录TiDB Server架构TiDB Server作用TiDB Server的进程SQL语句的解析和编译SQL读写相关模块在线DDL相关模块GC机制与相关模块TiDB Server的缓存热点小表缓存TiDB Server架构 Protocol Layer、Parse、Compile负责sql语句的解析编译和优化,然后生成sql语句执行计划…...

S3C2440移植Linux4.19.275内核以及过程中遇到的问题
目录 1 问题一:内核移植时MTD分区问题 2 问题二:uboot的MTDPARTS_DEFAULT定义的MTD分区,bootargs中的文件系统分区,内核的mtd_partition smdk_default_nand_part定义的分区,三者要对应起来 3 问题三:ubo…...

解忧杂货铺(二):UML时序图
目录 1、概述 2、UML时序图 2.1、什么是时序图 2.2、时序图的元素 2.2.1 角色(Actor) 2.2.2 对象(Object) 2.2.3 生命线(LifeLine) 2.2.4 控制焦点(Activation) 2.2.5 消息(Message) 2.2.6 自关联消息 2.2.7 组合片段 1、概述 在看AUTOSAR规范的时候发现时序图里面的…...

微信小程序的代码由哪些结构组成?
小程序官方建议把所有小程序的页面,都存放在pages 目录中,以单独的文件夹存在,如图所示: 其中,每个页面由4 个基本文件组成,它们分别是:js文件(页面的脚本文件,存放页面的数据、事件…...

Cloud Kernel SIG月度动态:发布 ANCK 新版本及 Plugsched v1.2.0
Cloud Kernel SIG(Special Interest Group):支撑龙蜥内核版本的研发、发布和服务,提供生产可用的高性价比内核产品。 01 2 月 SIG 整体进展 发布 ANCK 4.19.91-27.1 版本。 发布 ANCK 5.10.134-13.1 版本。 调度器热升级相关事…...

Jedis 使用详解(官方原版)
一、配置 Maven 依赖项Jedis也通过Sonatype作为Maven Dependency 分发。要配置它,只需将以下 XML 代码段添加到您的 pom.xml 文件中。<dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId><version>2.…...

关于Pytorch中的张量学习
关于Pytorch中的张量学习 张量的概念和创建 张量的概念 Tensor是pytorch中非常重要且常见的数据结构,相较于numpy数组,Tensor能加载到GPU中,从而有效地利用GPU进行加速计算。但是普通的Tensor对于构建神经网络还远远不够,我们需…...