前缀和——238. 除自身以外数组的乘积

文章目录
- 🍷1. 题目
- 🍸2. 算法原理
- 🍥解法一:暴力求解
- 🍥解法二:前缀和(积)
- 🍹3. 代码实现
🍷1. 题目
题目链接:238. 除自身以外数组的乘积 - 力扣(LeetCode)
给你一个整数数组 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 <= 105-30 <= nums[i] <= 30- 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶: 你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)
🍸2. 算法原理
本题的意思是,要求出除了当前下标位置,其他位置的乘积

🍥解法一:暴力求解
暴力求解就是遍历整个数组,然后再遍历一次除了当前位置的其他位置元素乘积,整个的时间复杂度为O(n2)
🍥解法二:前缀和(积)
这里求除了当前位置的整个数组的乘积,可以理解为求前面一部的前缀积+后面一部分的后缀积

预处理:
f表示前缀积,f[i]表示[0,i-1]区间内所有元素的乘积f[i] = f[i-1] * nums[i-1]g表示后缀积,g[i]表示[i+1,n-1]区间内所有元素的乘积g[i] = g[i+1] * nums[i+1]
这里因为
f[i]的区间是[0,i-1],所以这里的i,实际上是i-1
使用预处理之后的数组:
有了预处理的数组,我们只需让f[i]*g[i]即可求出当前位置的值
细节问题:
这里因为要求的是乘积,所以
f[0]这里要提前处理一下,f[0] = 1;同理g[n-1] = 1。
f是从前往后,g是从后往前
这个时间复杂度为O(n)+O(n)+O(n),可理解为O(n)
这里进阶是空间复杂度为O(1)求解,采用的也是前缀积和后缀积,用
ret先装前缀积,然后从后往前乘以后缀积。
我们前面采用2个数组装前缀积和后缀积,可以理解得更清晰一些。
🍹3. 代码实现
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums){int n = nums.size();vector<int> f(n) , g(n);//预处理前缀积f[0] = 1;g[n-1] = 1;for(int i=1;i<n;i++)f[i] = f[i-1] * nums[i-1];//预处理后缀积for(int i=n-2;i>=0;i--)g[i] = g[i+1] * nums[i+1];vector<int> ret(n);for(int i=0;i<n;i++)ret[i]=f[i]*g[i];return ret;}
};
优化空间复杂度:
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums){int n = nums.size();vector<int> ret(n,1);int left = 1;for(int i=1;i<n;i++){left *= nums[i-1];ret[i] = left;}int right = 1;for(int i=n-2;i>=0;i--){right*=nums[i+1];ret[i]*=right;}return ret;}
};
相关文章:
前缀和——238. 除自身以外数组的乘积
文章目录 🍷1. 题目🍸2. 算法原理🍥解法一:暴力求解🍥解法二:前缀和(积) 🍹3. 代码实现 🍷1. 题目 题目链接:238. 除自身以外数组的乘积 - 力扣&a…...
MySql数据库常用指令(二)
MySql数据库常用指令(二) 一、WHERE 子句二、UPDATE 更新三、DELETE 语句四、LIKE 子句五、UNION 操作符 注:文中TEST为测试所用数据库,根据实际应用修改 一、WHERE 子句 SELECT 语句使用 WHERE 子句从数据表中读取数据…...
zookeeper 单机伪集群搭建简单记录
1、官方下载加压后,根目录下新建data和log目录,然后分别拷贝两份,分别放到D盘,E盘,F盘 2、data目录下面新建myid文件,文件内容分别为1,2,3.注意文件没有后缀,不能是txt文…...
【Linux】匿名管道与命名管道,进程池的简易实现
文章目录 前言一、匿名管道1.管道原理2.管道的四种情况3.管道的特点 二、命名管道1. 特点2.创建命名管道1.在命令行上2.在程序中 3.一个程序执行打开管道并不会真正打卡 三、进程池简易实现1.makefile2.Task.hpp3.ProcessPool.cpp 前言 一、匿名管道 #include <unistd.h&g…...
HTML5+ API 爬坑记录
背景: 有个比较早些使用5开发的项目, 最近两天反馈了一些问题, 解决过程在此记录; 坑1: plus.gallery.pick 选择图片没有进入回调 HTML5 API Reference 在 联想小新 平板电脑上选择相册图片进行上传时, 打开相册瞬间 应用会自动重启, 相册倒是有打开, 不过应用重启了, 导…...
idea git将某个分支内的commit合并到其他分支
idea git将某个分支内的commit合并到其他分支 1.打开旧分支的代码提交记录 在IDEA中切换到新分支的代码,点击Git打开代码管理面板,在顶部点击Log:标签页(这个标签页内将来可以选择不同分支的个人/所有人的代码commit记录)&#x…...
Google hacking语法
Google hacking语法 文章目录 Google hacking语法site:inurl:intitle:filetypecacheintext注意 site: 搜索子域 跟域名site:www.baidu.com 定位 跟语言 site: jp inurl: 用于在特定url链接中搜索网站信息 inurl:login intitle: 使用intitle:指令返回页面标题中包含关键…...
Redis集群(新)
1.什么是集群 Redis集群实现了对Redis的水平扩容,可实现并发写操作,启动n个redis节点,将数据分别存储在不同的节点中,每块节点负责不同区域的插槽,所以Redis集群通过分区来提供一定程度的可用性。 Redis集群现采用的是…...
[JVM] 常用调优参数
随着Java应用程序的不断发展和优化,JVM调优已经变得越来越重要。在这篇文章中,我们将探讨一些常用的JVM调优参数,了解如何更好地优化Java应用程序的性能。 文章目录 1. -Xmx2. -Xms3. -XX:PermSize和-XX:MaxPermSize4. -XX:NewRatio5. -XX:Ma…...
【nlp】3.5 Transformer论文复现:3.解码器部分(解码器层)和4.输出部分(线性层、softmax层)
Transformer论文复现:3.解码器部分(解码器层)和4.输出部分(线性层、softmax层) 3.1 解码器介绍3.2 解码器层3.2.1 解码器层的作用3.2.2 解码器层的代码实现3.2.3 解码器层总结3.3 解码器3.3.1 解码器的作用3.3.2 解码器的代码实现3.3.3 解码器总结4.1 输出部分介绍4.2 线性…...
宝塔 Linux 面板安装一个高大上的论坛程序 —— Flarum
这个是很早搭建的版本,基于宝塔面板,比较复杂,如果想要简单的搭建方法,可以参看咕咕新写的这篇: 【好玩的 Docker 项目】10 分钟搭建一个高大上的论坛程序 购买腾讯云轻量应用服务器 待补充 登录服务器 待补充 BBR 加速脚本 BBR 加速脚本: BASH cd /usr/src &…...
数字化转型如何赋能企业实现数字化增值?
随着科技的不断发展,数字化转型已经成为了企业营销的重要趋势。数字化转型不仅可以提高企业的运营效率,还可以更好地满足消费者的需求,提升企业的市场竞争力。 一、数字化转型可以提高企业营销的精准性 在传统的企业营销中,营销人…...
深度学习之九(Transformers)
Transformers 是一种用于处理序列数据的深度学习模型,特别擅长于自然语言处理(NLP)任务。Transformer 是一种基于自注意力机制(Self-Attention Mechanism)的架构,于2017年由 Vaswani 等人在 “Attention is All You Need” 论文中提出,它在机器翻译任务中取得了显著的性…...
pgz easyexcel如何给excel文件添加自定义属性
免费API方式 直接上传URL,自定义修改Excel 视频演示【内含接口地址】 https://www.ixigua.com/7304510132812153385 前情提示 | 功能说明 多选仅支持微软office、office365系列Excel。因为WPS宏功能需要企业版且付费生成xlsx、xlsm等文件,office和WPS均可以打开,均可以单…...
【unity实战】实现一个放置3d物品建造装修系统(附项目源码)
文章目录 最终效果前言绘制开始场景素材开始放置旋转物体扩展优化1. 绘制地图边界,确保放置物品在指定区域内工作2. 让模型所占面积大小更加准确3. 隐藏白色瓦片指示区域 最终效果其他源码参考完结 最终效果 前言 其实3d物品建造装修系统之前就已经做过了ÿ…...
计算机网络之应用层
一、概述 引入目的: 为了方便用户去使用; 该如何方便用户使用网络呢,即怎样帮助用户使用网络? 1.用户需要知道网络资源所在的位置 2.网络上资源一定是在资源子网的主机上 3.资源子网上的主机,在通信子网中用IP地…...
Let’s xrOS 一款让你优先体验社区创作者的 visionOS App工具
Let’s xrOS Apple Vision Pro 发布预示着空间计算时代的到来,让科技爱好者和开发者开始思考如何在新的交互、系统和硬件上打造独特的三维应用。 自 WWDC 2023 的发布会后,社交媒体上涌现了许多精美的 visionOS App 的效果图和演示视频,然而…...
武汉教育E卡通学生证照片尺寸要求及证件照集中采集方法
”武汉教育E卡通“电子学生证旨在数字化中小学生身份,提供通用的教育卡,实现身份认证的电子化、权威化和集成化。校内一卡通系统包括刷卡考勤、电子班牌、图书借阅等,全面记录学生在校业务。同时,采集社会通行、实践活动等数据&am…...
C++《i+1》系列文章汇总
欢迎来到 PaQiuQiu 的空间 本文为【C《i1》专栏目录】,方便大家更好的阅读! 🚀~写在前面~ 当今计算机科学领域中最受欢迎和广泛使用的编程语言之一就是C。C是一种高级编程语言,具有强大的功能和广泛的应用领域,包括系统级编程、游…...
GEE:通过将 Landsat 5、7、8、9 的 C02 数据集合并起来,构建 NDVI 长时间序列
作者:CSDN @ _养乐多_ 本文记录了在 Google Earth Engine(GEE)平台上,将 Landsat-5、Landsat-7、Landsat-8 和 Landsat-9 的数据合成为一个影像集合,并生成 NDVI(归一化植被指数)的时间序列的代码。 代码封装成了函数,方便调用,结果如下图所示, 在实际应用中,可能…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...

