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

【leetcode面试经典150题】13.除自身以外数组的乘积(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)

【题目描述】

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法,且在 O(n) 时间复杂度内完成此题。

【示例一】

输入: nums = [1,2,3,4]输出: [24,12,8,6]

【示例二】

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

【提示及数据范围】

  • 2 <= nums.length <= 10的5次方
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

【代码】

// 方法一:左右乘积列表// 1.初始化两个空数组 L 和 R。对于给定索引 i,
// L[i] 代表的是 i 左侧所有数字的乘积,R[i] 代表的是 i 右侧所有数字的乘积。// 2.我们需要用两个循环来填充 L 和 R 数组的值。
// 对于数组 L,L[0] 应该是 1,因为第一个元素的左边没有元素。
// 对于其他元素:L[i] = L[i-1] * nums[i-1]。// 3.同理,对于数组 R,R[length-1] 应为 1。
// length 指的是输入数组的大小。其他元素:R[i] = R[i+1] * nums[i+1]。// 4.当 R 和 L 数组填充完成,我们只需要在输入数组上迭代,且索引 i 处的值为:L[i] * R[i]。class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int length = nums.size();// L 和 R 分别表示左右两侧的乘积列表vector<int> L(length, 0), R(length, 0);vector<int> answer(length);// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1L[0] = 1;for (int i = 1; i < length; i++) {L[i] = nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 'length-1' 的元素,因为右侧没有元素,所以 R[length-1] = 1R[length - 1] = 1;for (int i = length - 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}// 对于索引 i,除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i = 0; i < length; i++) {answer[i] = L[i] * R[i];}return answer;}
};// 方法2:空间复杂度 O(1) 的方法// 1.初始化 answer 数组,对于给定索引 i,answer[i] 代表的是 i 左侧所有数字的乘积。
// 2.构造方式与之前相同,只是我们试图节省空间,先把 answer 作为方法一的 L 数组。
// 3.这种方法的唯一变化就是我们没有构造 R 数组。而是用一个遍历来跟踪右边元素的乘积。
// 并更新数组 answer[i]=answer[i]∗R。
// 然后 R 更新为 R=R∗nums[i],其中变量 R 表示的就是索引右侧数字的乘积。class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int length = nums.size();vector<int> answer(length);// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素,所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 对于索引 i,左边的乘积为 answer[i],右边的乘积为 Ranswer[i] = answer[i] * R;// R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上R *= nums[i];}return answer;}
};

相关文章:

【leetcode面试经典150题】13.除自身以外数组的乘积(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…...

网络编程核心概念解析:IP地址、端口号与网络字节序深度探讨

⭐小白苦学IT的博客主页 ⭐初学者必看&#xff1a;Linux操作系统入门 ⭐代码仓库&#xff1a;Linux代码仓库 ❤关注我一起讨论和学习Linux系统 本节重点 认识IP地址, 端口号, 网络字节序等网络编程中的基本概念; 1.前言 网络编程&#xff0c;作为现代信息社会中的一项核心技术&…...

突破编程_C++_网络编程(TCPIP 四层模型(网络层(1))

1 网络层概述 TCP/IP 四层模型中的网络层是模型中的核心组成部分&#xff0c;它主要负责处理数据包的路由和转发&#xff0c;确保数据能够在源主机和目标主机之间准确地传输。 一、主要功能 网络层的主要功能是实现数据包的选路和转发。当数据从应用层传输到传输层后&#x…...

Java | Leetcode Java题解之第9题回文数

题目&#xff1a; 题解&#xff1a; class Solution {public boolean isPalindrome(int x) {// 特殊情况&#xff1a;// 如上所述&#xff0c;当 x < 0 时&#xff0c;x 不是回文数。// 同样地&#xff0c;如果数字的最后一位是 0&#xff0c;为了使该数字为回文&#xff0…...

极简云验证 download.php 文件读取漏洞复现

0x01 产品简介 极简云验证是一款开源的网络验证系统&#xff0c;支持多应用卡密生成&#xff1a;卡密生成 单码卡密 次数卡密 会员卡密 积分卡密、卡密管理 卡密长度 卡密封禁 批量生成 批量导出 自定义卡密前缀等&#xff1b;支持多应用多用户管理&#xff1a;应用备注 应用版…...

红黑树路径长度分析:证明与实现

红黑树路径长度分析&#xff1a;证明与实现 一、红黑树的基本性质二、证明&#xff1a;最长路径至多是最短路径的2倍2.1 证明思路2.2 证明过程 三、伪代码实现四、 C语言代码实现5、 结论 红黑树作为一种高效的自平衡二叉搜索树&#xff0c;在计算机科学领域中被广泛应用于各种…...

esp32 gpio初识(一)

目录 功能介绍 实操 功能介绍 引脚又叫管脚&#xff0c;英文叫 Pin, 就是从集成电路&#xff08;芯片以及一些电子元件&#xff09;内部电路引出与外围电路的接线的接口。 在我们的 ESP32 开发板上, 我们可以把这些称为引脚, 这些引脚其实是从 ESP32 芯片内部引出来的, 我们…...

python 自制黄金矿工游戏(设计思路+源码)

1.视频效果演示 python自制黄金矿工&#xff0c;细节拉满沉浸式体验&#xff0c;看了你也会 2.开发准备的工具 python3.8, pygame库(python3.5以上的版本应该都可以) 图片处理工具&#xff0c;美图秀秀 截图工具&#xff0c;电脑自带的 自动抠图网页&#xff1a;https://ko…...

Splunk Attack Range:一款针对Splunk安全的模拟测试环境创建工具

关于Splunk Attack Range Splunk Attack Range是一款针对Splunk安全的模拟测试环境创建工具&#xff0c;该工具完全开源&#xff0c;目前由Splunk威胁研究团队负责维护。 该工具能够帮助广大研究人员构建模拟攻击测试所用的本地或云端环境&#xff0c;并将数据转发至Splunk实例…...

OpenCV入门例程:裁剪图片、模糊检测、黑屏检测

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 本例程运行环境为CentOS7&…...

opencv-python库 cv2边界填充resize图片

文章目录 边界填充改变图片大小 边界填充 在OpenCV中&#xff0c;边界填充&#xff08;Border Padding&#xff09;是指在图像周围添加额外的像素&#xff0c;以扩展图像的尺寸或满足某些算法&#xff08;如卷积&#xff09;的要求。OpenCV提供了cv2.copyMakeBorder()函数来进…...

Java代码基础算法练习-负数个数统计-2024.04.04

任务描述&#xff1a; 从键盘输入任意10个整型数&#xff08;数值范围-100000~100000&#xff09;&#xff0c;统计其中的负数个数 任务要求&#xff1a; 代码示例&#xff1a; package April_2024;import java.util.Scanner;// 从键盘输入任意10个整型数&#xff08;数值范围…...

【算法刷题day17】Leetcode:110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和

110.平衡二叉树 文档链接&#xff1a;[代码随想录] 题目链接&#xff1a;:110.平衡二叉树 题目&#xff1a; 给定一个二叉树&#xff0c;判断它是否是 平衡二叉树 注意&#xff1a; 判断两棵子树高度差是否大于1 class Solution { public:int result;bool isBalanced(TreeNode…...

C++ | Leetcode C++题解之第10题正则表达式匹配

题目&#xff1a; 题解&#xff1a; class Solution { public:bool isMatch(string s, string p) {int m s.size();int n p.size();auto matches [&](int i, int j) {if (i 0) {return false;}if (p[j - 1] .) {return true;}return s[i - 1] p[j - 1];};vector<…...

职场迷航?MBTI测试为你指明方向,找到最匹配的职业!

MBTI简介 MBTI的全名是Myers-Briggs Type Indicator。它是一种迫选型、自我报告式的性格评估工具&#xff0c;用以衡量和描述人们在获取信息、作出决策、对待生活等方面的心理活动规律和性格类型。 类型指标 美国的凯恩琳布里格斯和她的女儿伊莎贝尔布里格斯迈尔斯研制了迈尔…...

hive 慢sql 查询

hive 慢sql 查询 查找 hive 执行日志存储路径&#xff08;一般是 hive-audit.log &#xff09; 比如&#xff1a;/var/log/Bigdata/audit/hive/hiveserver/hive-audit.log 解析日志 获取 执行时间 执行 OperationId 执行人 UserNameroot 执行sql 数据分隔符为 \001 并写入 hiv…...

Vue - 2( 10000 字 Vue 入门级教程)

一&#xff1a;Vue 1.1 绑定样式 1.1.1 绑定 class 样式 <!DOCTYPE html> <html><head><meta charset"UTF-8" /><title>绑定样式</title><style>......</style><script type"text/javascript" src&…...

Cisco交换机安全配置

Cisco交换机安全配置 前提 我们以下命令一般都要先进入Config模式 S1> enable S1# conf t S1(config)#端口安全保护 禁用未使用的端口 以关闭fa0/1到fa0/24的端口为例 S1(config)# interface range fa0/1-24 S1(config-if-range)# shutdown缓解MAC地址表攻击 防止CAM…...

LLM大模型可视化-以nano-gpt为例

内容整理自&#xff1a;LLM 可视化 --- LLM Visualization (bbycroft.net)https://bbycroft.net/llm Introduction 介绍 Welcome to the walkthrough of the GPT large language model! Here well explore the model nano-gpt, with a mere 85,000 parameters. 欢迎来到 GPT 大…...

【layui-table】转静态表格时固定表格列处理行高和单元格颜色

处理思路&#xff1a;覆盖layui部分表格样式 行高处理&#xff1a;获取当前行数据单元格的最高高度&#xff0c;将当前行所有数据单元格高度设置为该最高高度 单元格颜色处理&#xff1a;将原生表格转换为layui表格后&#xff0c;因为原生表格的表格结构和生成的layui表格结构…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...