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

[python 刷题] 238 Product of Array Except Self

[python 刷题] 238 Product of Array Except Self

题目:

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

这里题目中 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer 就很明显提示说用 prefix sum 了

另外还有就是题目要求的 O ( n ) O(n) O(n) 的时间复杂度,以及不能用除法

题目要求是获取除了自己以外的所有乘积,以题目中的案例 [1,2,3,4],它的乘积可以理解成这样的计算方式:

数组1234
prefix11126
postfix2412411
productprefix[i] * postfix[i] = 24prefix[i] * postfix[i] = 12prefix[i] * postfix[i] = 8prefix[i] * postfix[i] = 6

其中 prefix 是所有的前置乘积,postfix 是所有的后置乘积

解法如下:

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:prefix = [1] * (len(nums) + 2)postfix = [1] * (len(nums) + 2)for i in range(2, len(prefix)):prefix[i] = prefix[i - 1] * nums[i - 2]for i in range(len(prefix) - 3, 0, -1):postfix[i] = postfix[i + 1] * nums[i]res = [1] * len(nums)for i in range(0, len(nums)):print(prefix[i + 1])res[i] = prefix[i + 1] * postfix[i + 1]return res

但是在实际写的时候发现 map index 的处理稍微麻烦了一些,所以又找了一下其他的写法,发现了一个优化的写法:

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:res = [1] * (len(nums))for i in range(1, len(nums)):res[i] = res[i-1] * nums[i-1]postfix = 1for i in range(len(nums) - 1, -1, -1):res[i] *= postfixpostfix *= nums[i]return res

这个写法将原本的 3 pass 缩减成了 2 pass,即只有两个循环,主要是因为没有保存 postfix 这个数组,而是一边迭代一边计算 postfix

同时,prefix 的值直接存在了返回值中,跳掉了表格中下标为 0 的占位符

虽然时间和空间的大O还是一样的,不过速度和性能上确实好了不少

相关文章:

[python 刷题] 238 Product of Array Except Self

[python 刷题] 238 Product of Array Except Self 题目: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guar…...

UG NX二次开发(C#)-计算直线到各个坐标系轴向的投影角度

文章目录 1、前言2、需求分析3、NXOpen方法实现3.1 创建基准坐标系3.2 然后计算直线到基准坐标系的轴向角度3.3 代码调用4、测试效果为:1、前言 最近有个粉丝问我如何计算直线到坐标系各个轴向的角度,这里用UG NX二次开发(C#)实现。当然,这里的内容是经验之谈,如果有更好的…...

C# ComboBox 和 枚举类型(Enum)相互关联

C# ComboBox 和 枚举类型(Enum)相互关联 目的 在C# Winform面板上的ComboBox选择项,由程序填写某个Enum的各个枚举项目。 在运行中读取ComboBox的选择项,返回Enum数值。 非编程方法 低阶做法可以在winform设计窗口手动填写,但是不会自动跟…...

Linux CentOS7 tree命令

tree就是树,是文件或文件名输出到控制台的一种显示形式。 tree命令作用:以树状图列出目录的内容,包括文件、子目录及子目录中的文件和目录等。 我们使用ll命令显示只能显示一个层级的普通文件和目录的名称。而使用tree则可以树的形式将指定…...

软件设计模式系列之九——桥接模式

1 模式的定义 桥接模式是一种结构型设计模式,它用于将抽象部分与其实现部分分离,以便它们可以独立地变化。这种模式涉及一个接口,它充当一个桥,使得具体类可以在不影响客户端代码的情况下改变。桥接模式将继承关系转化为组合关系…...

构造函数的调用规则

#include <iostream> #include <string> using namespace std; class person{ public:int m_age; // person(){ // cout<<"默认构造的调用"<<endl; // } // person(int age){ // m_ageage; // cout<<"有参构造的调用"<…...

第十章:枚举类与注解

10.1&#xff1a;枚举类的使用 当需要定义一组常量时&#xff0c;建议使用枚举类&#xff08;前提&#xff1a;类的对象只有有限个&#xff0c;确定的&#xff09; eg&#xff1a; 星期&#xff1a;Mondey、.....、Sunday 性别&#xff1a;Man、.....、Woman 线程状态&#xff…...

ChatGPT:字符串操作问题——提取包含括号的字符串中的题干内容

ChatGPT&#xff1a;字符串操作问题——提取包含括号的字符串中的题干内容 String title p.text().split(“(”)[0];为什么会报错 ChatGPT&#xff1a; 在这段代码中&#xff0c;您正在使用Java处理一个字符串&#xff08;假设是HTML或文本&#xff09;&#xff0c;尝试将其分…...

jvm中对象创建、内存布局以及访问定位

对象创建 Java语言层面&#xff0c;创建对象通常&#xff08;例外&#xff1a;复制、反序列化&#xff09;仅仅是一个new关键字即可&#xff0c;而在虚拟机中&#xff0c;对象&#xff08;限于普通Java对象&#xff0c;不包括数组和Class对象等&#xff09;的创建又是怎样一个过…...

C基础-操作符详解

操作符分类&#xff1a; 算数操作符&#xff1a; - * / % //算数操作符 // int main() // { // // /除法 1.整数除法(除号两端都是整数) 2浮点数除法&#xff0c;除号的两端只要有一个小数就执行小数除法 // // 除法中&#xff0c;除数为0 // int a 7 / 2; /…...

时序预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元时间序列预测

时序预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元时间序列预测 目录 时序预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元时间序列预测效果一览基本介绍模型搭建程序设计参考资料 效果一览 基本介绍 MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元时间序列预测。…...

【深度学习实验】线性模型(五):使用Pytorch实现线性模型:基于鸢尾花数据集,对模型进行评估(使用随机梯度下降优化器)

目录 一、实验介绍 二、实验环境 1. 配置虚拟环境 2. 库版本介绍 三、实验内容 0. 导入库 1. 线性模型linear_model 2. 损失函数loss_function 3. 鸢尾花数据预处理 4. 初始化权重和偏置 5. 优化器 6. 迭代 7. 测试集预测 8. 实验结果评估 9. 完整代码 一、实验介…...

ADB底层原理

介绍 adb的全称为Android Debug Bridge&#xff0c;就是起到调试桥的作用。通过adb我们可以在Eclipse/Android Studio中方便通过DDMS来调试Android程序&#xff0c;说白了就是debug工具。adb是android sdk里的一个工具, 用这个工具可以直接操作管理android模拟器或者真实的and…...

etcd之读性能主要影响因素

1、Raft模块-线性读ReadIndex-节点之间的RTT延时、磁盘IO 线性读时Follower节点首先会向Raft 模块发送ReadIndex请求&#xff0c;此时Raft模块会先向各节点发送心跳确认&#xff0c;一半以上节点确认 Leader 身份后由leader节点将已提交日志索引 (committed index) 封装成 Rea…...

【Stable Diffusion】安装 Comfyui 之 window版

序言 由于stable diffusion web ui无法做到对流程进行控制&#xff0c;只是点击个生成按钮后&#xff0c;一切都交给AI来处理。但是用于生产生活是需要精细化对各个流程都要进行控制的。 故也就有个今天的猪脚&#xff1a;Comfyui 步骤 下载comfyui项目配置大模型和vae下载…...

Ansys Zemax | 如何建立二向分色分光镜

分光镜(Beam splitter)可被运用在许多不同的场合。一般而言&#xff0c;入射光抵达二向分色分光镜(dichroic beam splitter)时&#xff0c;会根据波长的差异产生穿透或反射的现象。这篇文章将说明如何在OpticStudio的非序列模式(non-sequential mode)中建立二向分色分光镜&…...

Mybatis学习笔记8 查询返回专题

1.返回实体类 2.返回List<实体类> 3.返回Map 4.返回List<Map> 5.返回Map<String,Map> 6.resultMap结果集映射 7.返回总记录条数 新建模块 依赖 目录结构 1.返回实体类 如果返回多条,用单个实体接收会出异常 2.返回List<实体类> 即使返回一条记…...

【测试开发】基础篇 · 专业术语 · 软件测试生命周期 · bug的描述 · bug的级别 · bug的生命周期 · 处理争执

【测试开发】基础篇 文章目录 【测试开发】基础篇1. 软件测试生命周期1.1 软件生命周期1.2 软件测试生命周期 2. 描述bug3. 如何定义bug的级别3.1 为什么要对bug进行级别划分3.2 bug的一些常见级别 4. bug的生命周期5. 产生争执这么怎么办&#xff08;处理人际关系&#xff09;…...

​bing许少辉乡村振兴战略下传统村落文化旅游设计images

​bing许少辉乡村振兴战略下传统村落文化旅游设计images...

第三十一章 Classes - 继承规则

第三十一章 Classes - 继承规则 继承规则 与其他基于类的语言一样&#xff0c;可以通过继承组合多个类定义。 类定义可以扩展&#xff08;或继承&#xff09;多个其他类。这些类又可以扩展其他类。 请注意&#xff0c;类不能继承 Python 中定义的类&#xff08;即 .py 文件中…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

从0开始学习R语言--Day17--Cox回归

Cox回归 在用医疗数据作分析时&#xff0c;最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据&#xff0c;往往会有很多的协变量&#xff0c;即使我们通过计算来减少指标对结果的影响&#xff0c;我们的数据中依然会有很多的协变量&#xff0c;且…...

从数据报表到决策大脑:AI重构电商决策链条

在传统电商运营中&#xff0c;决策链条往往止步于“数据报表层”&#xff1a;BI工具整合历史数据&#xff0c;生成滞后一周甚至更久的销售分析&#xff0c;运营团队凭经验预判需求。当爆款突然断货、促销库存积压时&#xff0c;企业才惊觉标准化BI的决策时差正成为增长瓶颈。 一…...

【笔记】结合 Conda任意创建和配置不同 Python 版本的双轨隔离的 Poetry 虚拟环境

如何结合 Conda 任意创建和配置不同 Python 版本的双轨隔离的Poetry 虚拟环境&#xff1f; 在 Python 开发中&#xff0c;为不同项目配置独立且适配的虚拟环境至关重要。结合 Conda 和 Poetry 工具&#xff0c;能高效创建不同 Python 版本的 Poetry 虚拟环境&#xff0c;接下来…...

ABB馈线保护 REJ601 BD446NN1XG

配电网基本量程数字继电器 REJ601是一种专用馈线保护继电器&#xff0c;用于保护一次和二次配电网络中的公用事业和工业电力系统。该继电器在一个单元中提供了保护和监控功能的优化组合&#xff0c;具有同类产品中最佳的性能和可用性。 REJ601是一种专用馈线保护继电器&#xf…...

【NLP】 38. Agent

什么是 Agent&#xff1f; 一个 Agent 就是能够 理解、思考&#xff0c;并且进行世界交互 的模型系统&#xff0c;并不是纯粹的 prompt 返回器。 它可以&#xff1a; 读取外部数据&#xff08;文件/API&#xff09;使用记忆进行上下文维持用类Chain-of-Thought (CoT)方式进行…...