【算法|前缀和系列No.4】leetcode238. 除自身以外数组的乘积

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【leetcode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
在这里插入图片描述

点击直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣题目解析
  • 3️⃣解题代码

1️⃣题目描述

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

注意:

  • 2 <= nums.length <= 1 0 5 10^{5} 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

2️⃣题目解析

状态表示:

  • l[i]:表示i下标左边所有元素乘积之积(即[0,i - 1]之间所有元素的乘积)。
  • r[i]:表示i下标右边所有元素乘积之积(即[i + 1,n - 1]之间所有元素的乘积)。

前缀积和后缀积表达式:

  • 前缀积方程:l[i] = l[i - 1] * nums[i - 1]
  • 后缀积方程:r[i[ = r[i + 1] * nums[i + 1]

3️⃣解题代码

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> l(n),r(n);l[0] = 1,r[n - 1] = 1;for(int i = 1;i < n;i++) l[i] = l[i - 1] * nums[i - 1];for(int i = n - 2;i >= 0;i--) r[i] = r[i + 1] * nums[i + 1];vector<int> answer(n);for(int i = 0;i < n;i++) answer[i] = l[i] * r[i];return answer;}
};

最后就通过啦!!!

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何实现前端数据持久化(LocalStorage、IndexedDB等)?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

MySQL InnoDB引擎深入学习的一天(InnoDB架构 + 事务底层原理 + MVCC)

目录 逻辑存储引擎 架构 概述 内存架构 Buffer Pool Change Buffe Adaptive Hash Index Log Buffer 磁盘结构 System Tablespace File-Per-Table Tablespaces General Tablespaces Undo Tablespaces Temporary Tablespaces Doublewrite Buffer Files Redo Log 后台线程 事务原…

Hadoop 配置 Kerberos 认证

1、安装 Kerberos 服务器和客户端 1.1 规划 服务端&#xff1a; bigdata3 客户端&#xff08;Hadoop集群&#xff09;&#xff1a; bigdata0 bigdata1 bigdata2 192.168.50.7 bigdata0.example.com bigdata0 192.168.50.8 bigdata1.example.com bigdata1 192.168.50.9 b…

4.Python-用Python,Ajax实现MySQL数据库的新增数据

题记 用python&#xff0c;ajax实现mysql数据库的新增数据。以下是一个简单的实例和操作过程。 安装flask模块 pip install flask 安装mysql.connector模块 pip install mysql-connector-python 编写app.py文件 app.py文件如下&#xff1a; 块引用可能显示不完整&#x…

第15章 SpringBoot

所有的流程逻辑原理都是针对2.3.2.RELEASE版本 15.1 谈谈你对微服务架构演进的理解 难度:★ 重点:★ 白话解析 还是串主线,在串主线的过程中发现问题,解决问题。主线的入口:随着业务的逻辑越来越复杂,架构再不断升级演进,先理解架构的演进。 这道题参考了:企业IT架构转…

kantts docker化

kan-tts docker本地化 环境安装 下载docker镜像(python3.8的) registry.cn-hangzhou.aliyuncs.com/modelscope-repo/modelscope:ubuntu20.04-cuda11.8.0-py38-torch2.0.1-tf2.13.0-1.9.2 安装基础模型 pip install modelscope 安装语音模型 pip install "modelscope…

系列八、Redis的事务

一、是什么 可以一次执行多个命令&#xff0c;本质是一组命令的集合。一个事务中的所有命令都会序列化&#xff0c;按顺序地串行化执行而不会被其他命令插入&#xff0c;不允许加塞。 二、能干嘛 一个队列中&#xff0c;一次性、顺序性、排他性的执行一些列命令。 三、怎么玩…

git本地仓库及远端仓库推送【linux】

git本地仓库及远端仓库推送【linux】 一.git上创建仓库二.linux中git三板斧i.检查是否安装gitii.克隆仓库到本地iii.提交到本地仓库iiii.上传到远端仓库 三.其他内容补充git loggit status.gitignore 一.git上创建仓库 已经创建好的可以直接跳到第二步进入到创建仓库界面&…

SpringBoot + 自定义注解 + AOP 高级玩法打造通用开关

前言 最近在工作中迁移代码的时候发现了以前自己写的一个通用开关实现&#xff0c;发现挺不错&#xff0c;特地拿出来分享给大家。 为了有良好的演示效果&#xff0c;我特地重新建了一个项目&#xff0c;把核心代码提炼出来加上了更多注释说明&#xff0c;希望xdm喜欢。 案例 …

SQL注入漏洞

0x01 漏洞介绍 泛微e-office系统是标准、易用、快速部署上线的专业协同OA软件&#xff0c;国内协同OA办公领域领导品牌&#xff0c;致力于为企业用户提供专业OA办公系统、移动OA应用等协同OA整体解决方案。泛微e-office深谙改革之道以迎变革之机&#xff0c;沉心产品研发数十载…

电子笔记真的好用吗?手机上适合记录学习笔记的工具

提及笔记&#xff0c;不少人都会和学习挂钩&#xff0c;的确学习过程中我们经常会遇到很多难题&#xff0c;而经常记录笔记可以有效地帮助大家记住很多知识&#xff0c;而且时常拿出笔记查看一下&#xff0c;可方便巩固过去学习的知识。 手机作为大家日常随身携带的工具&#…

Matlab进阶绘图第31期—桑基图(Sankey Chart)

桑基图&#xff08;Sankey Chart&#xff09;本质为一种流程图&#xff0c;可以很好地展示数据的层次结构以及流量变化。 桑基图主要由节点块与流动路径线组成。 其中&#xff0c;节点块用于表示类别&#xff1b;流动路径线除了可以直观地表示流动的方向&#xff0c;其宽度还…

【EI会议征稿】第九届能源资源与环境工程研究进展国际学术会议(ICAESEE 2023)

第九届能源资源与环境工程研究进展国际学术会议&#xff08;ICAESEE 2023&#xff09; 2023 9th International Conference on Advances in Energy Resources and Environment Engineering 第九届能源资源与环境工程研究进展国际学术会议&#xff08;ICAESEE 2023&#xff09;…

补体C3/C4(C3/C4)介绍

补体是一种血清蛋白质&#xff0c;存在于人和脊椎动物血清及组织液中&#xff0c;不耐热&#xff0c;活化后具有酶活性、可介导免疫应答和炎症反应。可被抗原-抗体复合物或微生物所激活&#xff0c;导致病原微生物裂解或被吞噬。可通过三条既独立又交叉的途径被激活&#xff0c…

【MATLAB源码-第48期】基于matlab的16QAM信号盲解调仿真。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 16QAM (16个象限幅度调制) 是一种广泛使用的数字调制技术。在无线和有线通信系统中&#xff0c;为了在固定的带宽内发送更多的信息&#xff0c;高阶调制如16QAM被使用。下面是16QAM盲解调的基本步骤、优缺点及应用场景。 16Q…

从零开始学习调用百度地图网页API:一、注册百度地图账号

目录 注册账号申请AK 注册账号 https://lbsyun.baidu.com/index.php?titlejspopular3.0/guide/getkey JavaScript API只支持浏览器类型的ak 申请AK 注&#xff1a;使用示例时&#xff0c;需要在百度地图示例加上https:&#xff0c;替换ak。

蓝桥杯——递增序列和货物摆放

文章目录 前言一、递增序列二、货物摆放总结 前言 多多练习 一、递增序列 解题思路&#xff1a; 代码实现&#xff1a; 当然我的这个代码也不是很正确 发这道题就是向大家集思广益&#xff0c;我的就只作为一个参考啦~ #include <stdio.h> #include <stdlib.h>…

提升医疗服务质量:将互联网医院源码应用于实践

随着科技的快速发展&#xff0c;医疗行业也亟需寻求创新的解决方案来提升服务质量。在这个数字化时代&#xff0c;互联网医院源码成为了引人注目的选择&#xff0c;为医疗机构和患者之间的沟通和协作提供了前所未有的便利。作为该领域的专家&#xff0c;我将介绍互联网医院源码…

Linux:Termius连接本地虚拟机与虚拟机快照

Termius连接本地虚拟机与虚拟机快照 1. Termius连接本地虚拟机2. 虚拟机快照与还原2.1 设置快照以及恢复 附录 1. Termius连接本地虚拟机 ifconfig -a 查看配置 连接成功 2. 虚拟机快照与还原 在学习阶段我们无法避免的可能损坏Linux操作系统。 如果损坏的话&#xff0c;重新…

【(数据结构)- 顺序表的实现】

顺序表的实现 一.数据结构的相关概念1、什么是数据结构2、为什么需要数据结构&#xff1f; 二.顺序表1.顺序表的概念及结构1.1 线性表 2、顺序表分类3、动态顺序表的实现&#xff08;1&#xff09;头文件 —— &#xff08;顺序结构的创建和相关操作函数的定义&#xff09;(2) …