[python 刷题] 238 Product of Array Except Self
[python 刷题] 238 Product of Array Except Self
题目:
Given an integer array
nums
, return an arrayanswer
such thatanswer[i]
is equal to the product of all the elements ofnums
exceptnums[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]
,它的乘积可以理解成这样的计算方式:
数组 | 1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|---|
prefix | 1 | 1 | 1 | 2 | 6 | |
postfix | 24 | 12 | 4 | 1 | 1 | |
product | prefix[i] * postfix[i] = 24 | prefix[i] * postfix[i] = 12 | prefix[i] * postfix[i] = 8 | prefix[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:枚举类的使用 当需要定义一组常量时,建议使用枚举类(前提:类的对象只有有限个,确定的) eg: 星期:Mondey、.....、Sunday 性别:Man、.....、Woman 线程状态ÿ…...
ChatGPT:字符串操作问题——提取包含括号的字符串中的题干内容
ChatGPT:字符串操作问题——提取包含括号的字符串中的题干内容 String title p.text().split(“(”)[0];为什么会报错 ChatGPT: 在这段代码中,您正在使用Java处理一个字符串(假设是HTML或文本),尝试将其分…...

jvm中对象创建、内存布局以及访问定位
对象创建 Java语言层面,创建对象通常(例外:复制、反序列化)仅仅是一个new关键字即可,而在虚拟机中,对象(限于普通Java对象,不包括数组和Class对象等)的创建又是怎样一个过…...

C基础-操作符详解
操作符分类: 算数操作符: - * / % //算数操作符 // int main() // { // // /除法 1.整数除法(除号两端都是整数) 2浮点数除法,除号的两端只要有一个小数就执行小数除法 // // 除法中,除数为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,就是起到调试桥的作用。通过adb我们可以在Eclipse/Android Studio中方便通过DDMS来调试Android程序,说白了就是debug工具。adb是android sdk里的一个工具, 用这个工具可以直接操作管理android模拟器或者真实的and…...

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

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

Ansys Zemax | 如何建立二向分色分光镜
分光镜(Beam splitter)可被运用在许多不同的场合。一般而言,入射光抵达二向分色分光镜(dichroic beam splitter)时,会根据波长的差异产生穿透或反射的现象。这篇文章将说明如何在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. 产生争执这么怎么办(处理人际关系)…...

bing许少辉乡村振兴战略下传统村落文化旅游设计images
bing许少辉乡村振兴战略下传统村落文化旅游设计images...
第三十一章 Classes - 继承规则
第三十一章 Classes - 继承规则 继承规则 与其他基于类的语言一样,可以通过继承组合多个类定义。 类定义可以扩展(或继承)多个其他类。这些类又可以扩展其他类。 请注意,类不能继承 Python 中定义的类(即 .py 文件中…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...

Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...

高抗扰度汽车光耦合器的特性
晶台光电推出的125℃光耦合器系列产品(包括KL357NU、KL3H7U和KL817U),专为高温环境下的汽车应用设计,具备以下核心优势和技术特点: 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计,确保在…...