.238.除自身以外数组的乘法

news/2024/6/20 21:32:26/文章来源:https://blog.csdn.net/weixin_57865902/article/details/137334217

·题目描述

·解题思路:

————————时间换空间(for循环暴力求解)————————

1.两个for循环不断乘积

2.稍作优化——先判断是否有0存在,若是在乘积的余下数组中有0直接判断为0 (但是只是最优时间复杂度减少,没什么大作用)

代码:


class Solution(object):def productExceptSelf(self, nums):#牺牲时间换空间n = len(nums)res = [0] * nfor i in range(n):multiply = 1if 0 in nums[:i] or 0 in nums[i+1:]:multiply = 0for j in range(n):if j == i:multiply *= 1else:multiply *= nums[j]res[i] = multiplyreturn res

————————牺牲空间换时间(两个额外数组空间,记录前缀积和后缀积)——————

1.利用pre数组记录每个元素的前缀积,pre[0]= 1     (图解如下,来源力扣官网)

2.利用post数组记录后缀积,post[-1]= 1     (图解)

3.将pre和post两个数组对应元素相乘所得数据就是最后的结果,直接放到nums原始数组的对应位置上,即可

代码:

def productExceptSelf(self, nums):#牺牲空间换时间n = len(nums)pre ,post = [0] * n, [0] * npre[0] , post[n-1] = 1 , 1for i in range(n-1):pre[i + 1] = nums[i] * pre[i]for j in range(n-1 , 0 , -1):post[j - 1] = post [j] * nums[j]for i in range(n):nums[i] = pre[i] * post [i]return nums

—————————兼顾时间和空间————————

1.将两个数组pre和post压缩为一个数组result

2.先用result记录原始的前缀积,步骤同上

3.利用动态字母R,记录后缀积。因为每个元素的前缀积已经记录,后缀积不断从后往前移动并且相乘更新R的值即可

(同样的思路,也可以先用resul记录后缀积,动态字母L记录前缀积,L从前往后移动即可)

代码:

    def productExceptSelf(self, nums):##兼顾时间和空间n = len(nums)result = [0] * nresult[0] = 1for i in range(n-1):result[i+1] = nums[i] * result[i]R = 1for j in range(n-1, -1,-1):result[j] = result[j] * RR *= nums[j]return result

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034846.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

EVM Layer2 主流解决方案

深度解析主流 EVM Layer 2 解决方案:zk Rollups 和 Optimistic Rollups 随着以太坊网络的不断演进和 DeFi 生态系统的迅速增长,以太坊 Layer 2 解决方案日益受到关注。 其中,zk Rollups 和 Optimistic Rollups 作为两种备受瞩目的主流 EVM&…

Mistral 7B v0.2 基础模型开源,大模型微调实践来了

Mistral AI在3月24日突然发布并开源了 Mistral 7B v0.2模型,有如下几个特点: 和上一代Mistral v0.1版本相比,上下文窗口长度从8k提升到32k,上下文窗口(context window)是指语言模型在进行预测或生成文本时&…

C++的并发世界(三)——线程对象生命周期

0.案例代码 先看下面一个例子&#xff1a; #include <iostream> #include <thread>void ThreadMain() {std::cout << "begin sub thread:" << std::this_thread::get_id()<<std::endl;for (int i 0; i < 10; i){std::cout <&…

Mac 下安装maven教程

note&#xff1a;网上已经有很多该类型教程了&#xff0c;这边自身保留一份&#xff0c;方便后面使用&#xff1b; 一、安装地址&#xff1a;官网 二、安装步骤 $ tar -xvf apache-maven-3.3.9-bin.tar.gz //mac支持手动点击解压 $ sudo mv -f apache-maven-3.3.9 /usr…

SRS OBS利用RTMP协议实现音视频推拉流;WebRTC 屏幕直播分享工具

一、SRS OBS利用RTMP协议实现音视频推拉流 参考&#xff1a;https://ossrs.net/lts/zh-cn/docs/v5/doc/getting-started 1&#xff09;docker直接运行SRS服务&#xff1a; docker run --rm -it -p 1935:1935 -p 1985:1985 -p 8080:8080 registry.cn-hangzhou.aliyuncs.co…

STM32 直接修改寄存器来输出内部时钟的方法

1. 在特殊情况下使能 MCO 功能的方法 在对某些不容易复现的问题进行代码调时&#xff0c;需要观察内部时钟的情况&#xff0c;但往往代码之前并没有使能 MCO 功能&#xff0c;在这种情况下就可以使用寄存器直接配置来输出内部时钟到GPIO 脚位上进行观察和测试。 下面的例子就…

Mysql实战--为什么表数据删掉一半,表文件大小不变

经常会有同学来问我&#xff0c;我的数据库占用空间太大&#xff0c;我把一个最大的表删掉了一半的数据&#xff0c;怎么表文件的大小还是没变&#xff1f; 那么今天&#xff0c;我就和你聊聊数据库表的空间回收&#xff0c;看看如何解决这个问题。 这里&#xff0c;我们还是针…

前端学习<三>CSS进阶——04-如何让一个元素水平垂直居中?

前言 老板的手机收到一个红包&#xff0c;为什么红包没居中&#xff1f; 如何让一个子元素在父容器里水平垂直居中&#xff1f;不管是学生还是找工作这个问题点必考&#xff0c;在实战开发中&#xff0c;也应用得非常多。 你也许能顺手写出好几种实现方法。但大部分人的写法…

产品经理和项目经理,到底有什么区别?

在项目管理中&#xff0c;产品经理和项目经理作为项目和产品成功实施的关键角色&#xff0c;扮演着不可或缺的作用。然而&#xff0c;尽管两者都涉及到项目的规划、执行和监控&#xff0c;但他们的职责、角色和重点却存在显著的差异。 产品经理和项目经理的区别主要体现在以下…

2_1.Linux中的网络配置

#1.什么是IP ADDRESS# internet protocol ADDRESS ##网络进程地址 ipv4 internet protocol version 4 ip是由32个01组成 11111110.11111110.11111110.11111110 254.254.254.254 #2.子网掩码# 用来划分网络区域 子网掩码非0的位对应的ip上的数字表示这个ip的网络位 子网掩码0位…

Java八股文(K8S)

Java八股文のK8S K8S K8S 请解释什么是Kubernetes&#xff1f; Kubernetes是一个开源的容器编排和管理工具&#xff0c;用于自动化部署、扩展和管理容器化应用程序。 请解释Kubernetes中的Pod、Deployment和Service之间的关系。 ● Pod是Kubernetes的最小部署单元&#xff0c;…

docker 部署 nali 开源 IP 地理信息归属查询软件

前言 早前用到一个小巧开源的 IP 归属地查询软件&#xff0c;官方提供了 Dockerfile&#xff0c;使用了一段时间觉得还不错&#xff0c;非常简单便捷。 部署 docker 启动 由于该项目会在首次启动自动下载 IP 数据库,所以最好通过挂载目录的方式,将数据库目录挂在到本地,避免…

高效学习方法:冥想背诵,看一句念一句,再每个词分析位置及语法等合理性,忘记哪个词再看猜下为什么会忘,跟自己的表达哪里不一样。

原则&#xff1a;易学则易行&#xff0c;则效果最好。《易经》 你提到的这种学习方法结合了多种记忆和理解技巧&#xff0c;可以帮助提高学习效率。下面是对这种方法的一个详细解释和一些建议&#xff1a; 冥想背诵&#xff1a;通过冥想来集中注意力&#xff0c;可以帮助你在没…

学习vue3第十二节(组件的使用与类型)

1、组件的作用用途 目的&#xff1a; 提高代码的复用度&#xff0c;和便于维护&#xff0c;通过封装将复杂的功能代码拆分为更小的模块&#xff0c;方便管理&#xff0c; 当我们需要实现相同的功能时&#xff0c;我们只需要复用已经封装好的组件&#xff0c;而不需要重新编写相…

神经网络:梯度下降法更新模型参数

作者&#xff1a;CSDN _养乐多_ 在神经网络领域&#xff0c;梯度下降是一种核心的优化算法&#xff0c;本文将介绍神经网络中梯度下降法更新参数的公式&#xff0c;并通过实例演示其在模型训练中的应用。通过本博客&#xff0c;读者将能够更好地理解深度学习中的优化算法和损…

如何从文本数据中提取子列表

提取文本数据中的子列表可以通过各种方式实现&#xff0c;具体取决于文本数据的结构和提取子列表的条件。例如&#xff1a;使用字符串操作和条件判断、使用正则表达式、使用自然语言处理工具、使用自定义解析器等几种模式&#xff0c;那么对于在日常使用中会有那些问题呢 &…

EasyExcel 模板导出excel、合并单元格及单元格样式设置。 Freemarker导出word 合并单元格

xls文件&#xff1a; 后端代码&#xff1a; InputStream filePath this.getClass().getClassLoader().getResourceAsStream(templateFile);// 根据模板文件生成目标文件ExcelWriter excelWriter EasyExcel.write(orgInfo.getFilename()).excelType(ExcelTypeEnum.XLS).withTe…

python批量转化pdf图片为jpg图片

1.把pdf图片批量转为jpg&#xff1b;需要注意的是&#xff0c;需要先安装poppler这个软件&#xff0c;具体安装教程放在下面代码中了 2.代码 #poppler安装教程参考&#xff1a;https://blog.csdn.net/wy01415/article/details/110257130 #windows上poppler下载链接&#xff1a…

基于ssm端游账号销售管理系统论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对端游账号销售信息管理混乱&#xff0c;出错率高&#xff0c;信息安全…

乐观锁解决超卖问题

3.6 乐观锁解决超卖问题 修改代码方案一、 VoucherOrderServiceImpl 在扣减库存时&#xff0c;改为&#xff1a; boolean success seckillVoucherService.update().setSql("stock stock -1") //set stock stock -1.eq("voucher_id", voucherId).eq(&q…