当前位置: 首页 > news >正文

前缀和——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. 算法原理

本题的意思是,要求出除了当前下标位置,其他位置的乘积

image-20231125122843183

🍥解法一:暴力求解

暴力求解就是遍历整个数组,然后再遍历一次除了当前位置的其他位置元素乘积,整个的时间复杂度为O(n2)

🍥解法二:前缀和(积)

这里求除了当前位置的整个数组的乘积,可以理解为求前面一部的前缀积+后面一部分的后缀积

image-20231125123557540

预处理:

  • 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. 除自身以外数组的乘积

文章目录 &#x1f377;1. 题目&#x1f378;2. 算法原理&#x1f365;解法一&#xff1a;暴力求解&#x1f365;解法二&#xff1a;前缀和&#xff08;积&#xff09; &#x1f379;3. 代码实现 &#x1f377;1. 题目 题目链接&#xff1a;238. 除自身以外数组的乘积 - 力扣&a…...

MySql数据库常用指令(二)

MySql数据库常用指令&#xff08;二&#xff09; 一、WHERE 子句二、UPDATE 更新三、DELETE 语句四、LIKE 子句五、UNION 操作符 注&#xff1a;文中TEST为测试所用数据库&#xff0c;根据实际应用修改 一、WHERE 子句 SELECT 语句使用 WHERE 子句从数据表中读取数据&#xf…...

zookeeper 单机伪集群搭建简单记录

1、官方下载加压后&#xff0c;根目录下新建data和log目录&#xff0c;然后分别拷贝两份&#xff0c;分别放到D盘&#xff0c;E盘&#xff0c;F盘 2、data目录下面新建myid文件&#xff0c;文件内容分别为1&#xff0c;2&#xff0c;3.注意文件没有后缀&#xff0c;不能是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中切换到新分支的代码&#xff0c;点击Git打开代码管理面板&#xff0c;在顶部点击Log:标签页&#xff08;这个标签页内将来可以选择不同分支的个人/所有人的代码commit记录&#xff09;&#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的水平扩容&#xff0c;可实现并发写操作&#xff0c;启动n个redis节点&#xff0c;将数据分别存储在不同的节点中&#xff0c;每块节点负责不同区域的插槽&#xff0c;所以Redis集群通过分区来提供一定程度的可用性。 Redis集群现采用的是…...

[JVM] 常用调优参数

随着Java应用程序的不断发展和优化&#xff0c;JVM调优已经变得越来越重要。在这篇文章中&#xff0c;我们将探讨一些常用的JVM调优参数&#xff0c;了解如何更好地优化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 &…...

数字化转型如何赋能企业实现数字化增值?

随着科技的不断发展&#xff0c;数字化转型已经成为了企业营销的重要趋势。数字化转型不仅可以提高企业的运营效率&#xff0c;还可以更好地满足消费者的需求&#xff0c;提升企业的市场竞争力。 一、数字化转型可以提高企业营销的精准性 在传统的企业营销中&#xff0c;营销人…...

深度学习之九(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. 绘制地图边界&#xff0c;确保放置物品在指定区域内工作2. 让模型所占面积大小更加准确3. 隐藏白色瓦片指示区域 最终效果其他源码参考完结 最终效果 前言 其实3d物品建造装修系统之前就已经做过了&#xff…...

计算机网络之应用层

一、概述 引入目的&#xff1a; 为了方便用户去使用&#xff1b; 该如何方便用户使用网络呢&#xff0c;即怎样帮助用户使用网络&#xff1f; 1.用户需要知道网络资源所在的位置 2.网络上资源一定是在资源子网的主机上 3.资源子网上的主机&#xff0c;在通信子网中用IP地…...

Let’s xrOS 一款让你优先体验社区创作者的 visionOS App工具

Let’s xrOS Apple Vision Pro 发布预示着空间计算时代的到来&#xff0c;让科技爱好者和开发者开始思考如何在新的交互、系统和硬件上打造独特的三维应用。 自 WWDC 2023 的发布会后&#xff0c;社交媒体上涌现了许多精美的 visionOS App 的效果图和演示视频&#xff0c;然而…...

武汉教育E卡通学生证照片尺寸要求及证件照集中采集方法

”武汉教育E卡通“电子学生证旨在数字化中小学生身份&#xff0c;提供通用的教育卡&#xff0c;实现身份认证的电子化、权威化和集成化。校内一卡通系统包括刷卡考勤、电子班牌、图书借阅等&#xff0c;全面记录学生在校业务。同时&#xff0c;采集社会通行、实践活动等数据&am…...

C++《i+1》系列文章汇总

欢迎来到 PaQiuQiu 的空间 本文为【C《i1》专栏目录】&#xff0c;方便大家更好的阅读! &#x1f680;~写在前面~ 当今计算机科学领域中最受欢迎和广泛使用的编程语言之一就是C。C是一种高级编程语言&#xff0c;具有强大的功能和广泛的应用领域&#xff0c;包括系统级编程、游…...

GEE:通过将 Landsat 5、7、8、9 的 C02 数据集合并起来,构建 NDVI 长时间序列

作者:CSDN @ _养乐多_ 本文记录了在 Google Earth Engine(GEE)平台上,将 Landsat-5、Landsat-7、Landsat-8 和 Landsat-9 的数据合成为一个影像集合,并生成 NDVI(归一化植被指数)的时间序列的代码。 代码封装成了函数,方便调用,结果如下图所示, 在实际应用中,可能…...

Spring Boot Admin Server 2.3.1 保姆级搭建教程:从零到一,顺便搞定安全登录

Spring Boot Admin Server 2.3.1 零基础实战&#xff1a;从环境搭建到安全防护全解析 当你面对十几个微服务实例时&#xff0c;是否经常为查看日志、监控状态而频繁切换终端&#xff1f;Spring Boot Admin 就像给你的微服务集群装上了"全景天窗"&#xff0c;一站式解…...

NVIDIA Profile Inspector深度解析:如何解锁显卡隐藏性能的7个关键技术

NVIDIA Profile Inspector深度解析&#xff1a;如何解锁显卡隐藏性能的7个关键技术 【免费下载链接】nvidiaProfileInspector 项目地址: https://gitcode.com/gh_mirrors/nv/nvidiaProfileInspector 当你面对游戏帧率波动、画面撕裂或显卡性能未充分发挥时&#xff0c;…...

深入GStreamer插件生态:从good、bad、ugly到libav,如何为你的项目选对‘轮子’

深入GStreamer插件生态&#xff1a;从good、bad、ugly到libav&#xff0c;如何为你的项目选对‘轮子’ 在多媒体开发领域&#xff0c;GStreamer以其灵活的管道架构和丰富的插件生态著称。但面对good、bad、ugly和libav四大插件集&#xff0c;开发者常陷入选择困境&#xff1a;是…...

重新定义效率革命:baidupankey技术突破与数字资源获取范式转移

重新定义效率革命&#xff1a;baidupankey技术突破与数字资源获取范式转移 【免费下载链接】baidupankey 项目地址: https://gitcode.com/gh_mirrors/ba/baidupankey 在数字资源分发的生态系统中&#xff0c;信息获取效率已成为制约知识流动的关键瓶颈。传统云存储服务…...

3步搞定视频硬字幕提取:本地化AI工具终极指南

3步搞定视频硬字幕提取&#xff1a;本地化AI工具终极指南 【免费下载链接】video-subtitle-extractor 视频硬字幕提取&#xff0c;生成srt文件。无需申请第三方API&#xff0c;本地实现文本识别。基于深度学习的视频字幕提取框架&#xff0c;包含字幕区域检测、字幕内容提取。A…...

工程施工项目安全生产履职规范

工程施工项目安全生产履职规范——第一责任人示范与全员深度参入要求为全面落实施工项目安全生产责任&#xff0c;推动各级参入人深度参与安全生产管理&#xff0c;防范各类安全事故发生&#xff0c;保障项目施工安全、有序推进&#xff0c;结合施工项目管理实际&#xff0c;制…...

思源宋体CN:7种字重免费开源字体如何快速提升你的中文设计效果

思源宋体CN&#xff1a;7种字重免费开源字体如何快速提升你的中文设计效果 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 还在为中文排版设计而烦恼吗&#xff1f;找不到既美观又免费…...

LinkSwift技术解析:八大网盘直链获取方案与架构设计深度分析

LinkSwift技术解析&#xff1a;八大网盘直链获取方案与架构设计深度分析 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 …...

# 发散创新:基于A*算法的AI寻路优化实战与多场景适配在游戏开发、机器人导航和自动驾驶等领域,**智能寻路系统**是

发散创新&#xff1a;基于A*算法的AI寻路优化实战与多场景适配 在游戏开发、机器人导航和自动驾驶等领域&#xff0c;智能寻路系统是核心模块之一。传统BFS/DFS方法虽然简单&#xff0c;但在复杂地图中效率低下&#xff1b;而A*&#xff08;A-Star&#xff09;算法凭借启发式函…...

3分钟破解QQ音乐格式封锁:qmcdump音频解密完整指南

3分钟破解QQ音乐格式封锁&#xff1a;qmcdump音频解密完整指南 【免费下载链接】qmcdump 一个简单的QQ音乐解码&#xff08;qmcflac/qmc0/qmc3 转 flac/mp3&#xff09;&#xff0c;仅为个人学习参考用。 项目地址: https://gitcode.com/gh_mirrors/qm/qmcdump 你是否遇…...