首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:除自身以外数组的乘积

#yyds干货盘点# LeetCode程序员面试金典:除自身以外数组的乘积

时间:2023-09-24 18:02:53浏览次数:46  
标签:yyds 乘积 nums int 金典 元素 length answer LeetCode

题目:

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

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

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

 

示例 1:

[1,2,3,4]
[24,12,8,6]

示例 2:

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

代码实现:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;

        // L 和 R 分别表示左右两侧的乘积列表
        int[] L = new int[length];
        int[] R = new int[length];

        int[] answer = new int[length];

        // L[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1
        L[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] = 1
        R[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;
    }
}

标签:yyds,乘积,nums,int,金典,元素,length,answer,LeetCode
From: https://blog.51cto.com/u_13321676/7587196

相关文章

  • #yyds干货盘点# LeetCode程序员面试金典:全 O(1) 的数据结构
    1.简述:请你设计一个用于存储字符串计数的数据结构,并能够返回计数最小和最大的字符串。实现 AllOne 类:AllOne() 初始化数据结构的对象。inc(Stringkey) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ,那么插入计数为 1 的 key 。dec(Stringkey) 字符串 k......
  • 算法训练day18 LeetCode 513
    算法训练day18LeetCode513.112.106513.找树左下角的值题目513.找树左下角的值-力扣(LeetCode)题解代码随想录(programmercarl.com)递归方式单独数据存储最大深度,和此深度的结点值递归后要注意回溯classSolution{public:intmaxDepth=INT_MIN;......
  • Leetcode刷题21.合并两个有序链表
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输出:[0] 提示:两个链表的节点数目......
  • 算法训练day8 LeetCode 344
    算法训练day8:LeetCode344.541.151.剑指offer05.58.344.反转字符串题目344.反转字符串-力扣(LeetCode)题解代码随想录(programmercarl.com)classSolution{public:voidreverseString(vector<char>&s){for(inti=0,j=s.size()-1;i......
  • 算法训练day17 LeetCode 110
    算法训练day17LeetCode110.257.404110平衡二叉树题目110.平衡二叉树-力扣(LeetCode)题解代码随想录(programmercarl.com)当子树已经不平衡,直接返回-1.平衡则返回子数高度进行更高树间的高度比较classSolution{public:intgetHeight(TreeNode*node)......
  • 【LeetCode】2591. 将钱分给最多的儿童
    描述给你一个整数money,表示你总共有的钱数(单位为美元)和另一个整数children,表示你要将钱分配给多少个儿童。你需要按照如下规则分配:所有的钱都必须被分配。每个儿童至少获得1美元。没有人获得4美元。请你按照上述规则分配金钱,并返回最多有多少个儿童获得恰好8......
  • # yyds干货盘点 # ChatGPT 实用小案例分享——使用Python重命名附件和统计发票合计金
    大家好,我是皮皮。一、前言前几天在【志军】的星球看到了一个有意思的ChatGPT分享,正好喝Python相关的,一起来看看吧。ChatGPT实用小案例分享。如果你在高德或者滴滴上申请过开票,应该知道它们会给我们发一封邮件,发票和行程单都会放在附件中。由于高德是聚合平台,背后有很多网约车平台,......
  • LeetCode3题学透链表初始化、查找、插入删除、逆置操作
    1.题目要求LeetCode203移除链表指定元素LeetCode707设计链表LeetCode206反转链表  这三个题目包含了链表的初始化、插入头尾结点、插入删除第n个结点,删除指定内容的结点、链表的逆置等,下面我将一一讲解并展示源代码。2.具体操作2.1LeetCode中链表的初始化  我下面所讲......
  • [leetcode] 10. 正则表达式匹配
    10.正则表达式匹配给你一个字符串s和一个字符规律p,请你来实现一个支持'.'和'*'的正则表达式匹配。'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配,是要涵盖整个字符串s的,而不是部分字符串。示例1:输入:s="aa",p="a"输出:false解释:"a"无......
  • #yyds干货盘点#Koa-router 优先级问题
    问题描述在使用Koa-router作为路由遇到了一个优先级问题.如下代码//routerPage.jsfileconstrouter=require("koa-router")router.get("/test",ctx=>{ctx.body="test"})router.get("/router/test",ctx=>{ctx.body="routertest......