除自身以外数组的乘积(c语言详解)
题目:除自身外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法,且在 O(n) 时间复杂度内完成此题。
提示:
2 <= nums.lengh <= 10^5
-30 <= nums[i] <= 30
保证数组之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内 nums;
示例 1:
输入:nums=[ 1,2,3,4 ]
输出:[ 24,12,8,6 ]
示例 2:
输入:nums=[ -1,-1,0,-3,3 ]
输出:[ 0,0,9,0,0 ]
解题思路:
定义两个数组(前缀乘积数组与后缀乘积数组),前缀数组为:left [ ] ,后缀数组:right [ ] ;
left [ i ] 里存 nums [ i ] 前面的乘积和,righ[ i ] 里存 nums [ i ] 后面的乘积和,(为空时存1);
创建一个动态内存变量 int* ret=(int*)malloc(sizeof(int)*numsSize);
然后ret [ i ]=left [ i ] * right [ i ],存储后返回;
思路实现:
因为数组元素 :2 <= nums.lengh <= 10^5
所以前缀和后缀数组申请的数组大小都是10^5;
int left[100000]={0};
int right[100000]={0};
然后就是遍历求前缀乘积数组的各项值:
//前缀乘积和for(i=0;i<numsSize;i++){if(i==0){left[i]=1;}else{left[i]=left[i-1]*nums[i-1];}}
解析:
这里呢用数组 nums [ 1,2,3,4,5,6 ] 来举例;
此时,left [ 0 ] =1,然后 left [ 1 ] = left [ 0 ] * nums [ 0 ] 相当于 left [ 1 ] = nums [ 0 ] ;
left [ 2 ] = left [ 1 ] * nums [ 1 ] 相当于 left [ 2 ] = nums [ 0 ] * nums [ 1 ] ;
left [ 3 ] = left [ 2 ] * nums [ 2 ] 相当于 left [ 3 ] = nums [ 0 ] * nums [ 1 ] * nums [ 2 ] ;
。。。。。。
left [ 5 ] = left [ 4 ] * nums [ 4 ] 相当于 left [ 5 ] = nums [ 0 ] * nums [ 1 ] * nums [ 2 ] * nums [ 3 ] * nums [ 4 ] ;
想必大家也已经找到其中的规律了;
然后就是遍历求后缀乘积数组的各项值:
//后缀乘积和for(i=numsSize-1;i>=0;i--){if(i==numsSize-1){right[i]=1;}else{right[i]=right[i+1]*nums[i+1];}}
解析:
同理:nums [ 1,2,3,4,5,6 ]
left [ 5 ] =1,然后 left [ 4 ] = left [ 5 ] * nums [ 5 ] 相当于 left [ 4 ] = nums [ 5 ] ;
left [ 3 ] = left [ 4 ] * nums [ 4 ] 相当于 left [ 3 ] = nums [ 4 ] * nums [ 5 ] ;
left [ 2 ] = left [ 3 ] * nums [ 3 ] 相当于 left [ 2 ] = nums [ 3 ] * nums [ 4 ] * nums [ 5 ] ;
。。。。。。
left [ 0 ] = left [ 1 ] * nums [ 1 ] 相当于 left [ 0 ] = nums [ 1 ] * nums [ 2 ] * nums [ 3 ] * nums [ 4 ] * nums [ 5 ] ;
然后就是给返回值(* returnSize)赋值,以及创建动态内(ret),以及给其赋值再返回;
* returnSize=numsSize;int* ret=(int*)malloc(4*numsSize);//给返回指针赋值for(i=0;i<numsSize;i++){ret[i]=left[i]*right[i];}
时间复杂度为(O(N) ) ;
这就是这道题目的基本思路,下面是程序源代码:
int* productExceptSelf(int* nums, int numsSize, int* returnSize){int i=0;int left[100000]={0};int right[100000]={0};//前缀乘积和for(i=0;i<numsSize;i++){if(i==0){left[i]=1;}else{left[i]=left[i-1]*nums[i-1];}}//后缀乘积和for(i=numsSize-1;i>=0;i--){if(i==numsSize-1){right[i]=1;}else{right[i]=right[i+1]*nums[i+1];}}* returnSize=numsSize;int* ret=(int*)malloc(4*numsSize);//给返回指针赋值for(i=0;i<numsSize;i++){ret[i]=left[i]*right[i];}return ret;
}
如有不足欢迎来补充交流!
完结。。。
相关文章:
除自身以外数组的乘积(c语言详解)
题目:除自身外数组的乘积 给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除…...

ONES × 鲁邦通|打造研发一体化平台,落地组织级流程规范
近日,ONES 签约工业互联网行业领先的解决方案提供商——鲁邦通,助力鲁邦通优化组织级流程规范,落地从需求到交付的全生命周期线上化管理。 依托于 ONES 一站式研发管理平台,鲁邦通在软硬件设计开发、项目管理和精益生产等方面的数…...
【GaussDB】 SQL 篇
建表语句 表的分类 普通的建表语句 复制表内容 只复制表结构 create table 新表名(like 源表名 including all); 如果希望注释被复制的话要指定including comments 复制索引、主键约束和唯一约束,那么需要指定including indexes including constraints …...

rn和flutter出现“Running Gradle task ‘assembleDebug
在第一次运行rn和flutter时,会卡在Running Gradle task assembleDebug,可以使用阿里的镜像,如下图: maven { url https://maven.aliyun.com/repository/google/ } google() maven { url https://maven.aliyun.com/repository/jcen…...

Shell脚本基础( 四: sed编辑器)
目录 1 简介 1.1 sed编辑器的工作流程 2 sed 2.1 基本用法 2.2 sed基本格式 2.2.1 sed支持正则表达式 2.2.2 匹配正则表达式 2.2.3 奇数偶数表示 2.2.4 -d选项删除 2.2.5 -i修改文件内容 2.2.6 -a 追加 2.3 搜索替代 2.4 变量 1 简介 sed是一种流编辑器,…...

微信消息没通知iphone can‘t show notifications
小虎最近手机微信消息没通知,本来以为要卸载,但是发现原来是多客户端登录导致消息被其他平台截取,所有没有通知。 解决方法 小虎是在手机和电脑端同时登录的,所有退出电脑端后手机新消息就有提示了。可能是一个bug。...
Linux Kernel:pid与namespace
环境: Kernel Version:Linux-5.10 ARCH:ARM64 一:前言 Linux内核涉及进程和程序的所有算法都围绕task_struct数据结构建立,具体可看另一篇文章: Linux Kernel:thread_info与task_struct 同时Linux提供了资源限制(resource limit, rlimit)机制,对进程使用系统资源施…...

开源后台管理系统Geekplus Admin
本系统采用前后端分离开发模式,后端采用springboot开发技术栈,mybatis持久层框架,redis缓存,shiro认证授权框架,freemarker模版在线生成代码,websocket消息推送等,后台管理包含用户管理…...

【MATLAB基础绘图第16棒】绘制热图(Heatmap)
热图(Heatmap) 热图的主要作用是直观展示重点研究对象的差异情况,多用于经济学与工学差异性分析之中。 heatmap函数创建热图 语法 hheatmap(tbl,xvar,yvar) hheatmap(tbl,xvar,yvar,ColorVariable,cvar) hheatmap(cdata) hheatmap(xvalue…...

数据库--SQL关键字的执行顺序
数据库相关链接: 数据库--数据类型:http://t.csdn.cn/RtqMD 数据库--三大范式、多表查询、函数sql:http://t.csdn.cn/udJSG 数据库--MySQL增删改查:http://t.csdn.cn/xkiti 一、一条sql语句通常包括: select fro…...

如何优雅地处理Java多线程编程中的共享资源问题,以确保线程安全和高性能?
文章目录 🎉欢迎来到Java面试技巧专栏~如何优雅地处理Java多线程编程中的共享资源问题? ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页:IT陈寒的博客🎈该系列文章专栏:Java面试技巧文章作者技术和水平有限&…...

每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等递归)
今日份题目: 求 12...n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例1 输入: n 3 输出: 6 示例2 输入: n 9 输出: 45 提示 1 < n < 10000 题目思路 使用递归…...

服务器安装centos7踩坑
1、制作启动工具 下载iso https://developer.aliyun.com/mirror/?spma2c6h.25603864.0.0.20387abbo2RFbn http://mirrors.aliyun.com/centos/7.9.2009/isos/x86_64/?spma2c6h.25603864.0.0.1995f5ad4AhJaW下载 UltraISO https://cn.ultraiso.net/插入u盘启动 到了如图所示页面…...

Java | IDEA中 jconsole 不是内部或外部命令,也不是可运行的程序
解决办法: 1.先将Terminal的Shell path 修改为C:\WINDOWS\system32\cmd.exe 2.在检查环境变量中的ComSpec的值 3.找到自己电脑下载的jdk的bin的地址 4.将jdk的bin地址加入到系统变量path中...
将Swift Package构建为通用二进制文件 Universal Binary
将Swift软件包构建为通用二进制文件 因此,在苹果在WWDC 2020期间宣布他们将把Mac从英特尔处理器过渡到苹果硅之后,现在是时候让每个人都准备好他们的软件了。 对大多数人来说,这次过渡可能更容易一些,特别是那些已经在iOS上支持a…...

正则表达式:贪婪与非贪婪模式
正则中的三种模式,贪婪匹配、非贪婪匹配和独占模式。 在这 6 种元字符中,我们可以用 {m,n} 来表示 (*)()(?) 这 3 种元字符: 贪婪模式,简单说就是尽可能进行…...
UVa247 Calling Circles(Floyd warshall算法)
题意 给定两个人相互打电话,如果a打给b,b打给c,c打给a,则说a,b,c在同一电话圈中。给出n个人的m次通话,输出所有的电话圈 思路 用graph[u][v]1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]1表示u,v之间有直接…...

Java项目之基于ssm框架的社区生活超市管理系统(附源码)
基于ssm框架的社区生活超市管理系统设计与实现(程序源码毕业论文) 大家好,今天给大家介绍基于ssm框架的社区生活超市管理系统设计与实现,本论文只截取部分文章重点,文章末尾附有本毕业设计完整源码及论文的获取方式。更…...
Android 实现录音功能
思路: 通过媒体录制器MediaRecorder实现:MediaRecorder是Android自带的音频和视频录制工具,它通过操纵摄像头和麦克风完成媒体录制,既可录制视频,又可单独录制音频。 MediaRecorder常用方法(录音与录像通用)…...

drawio导出矢量图
1.选中要导出的图 2.导出为pdf 3.用adobe打开pdf,另存为eps...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...