[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 文件中…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...