专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友投了华为的软件工程师，投了之后就没有反应了，联系HR也不回复，后来通过打听得知该网友所在学校不是华为的目标院校。原来大厂招聘都有目标院校，如果不是目标院校是不是简历都过不了？
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第238题：除自身以外数组的乘积。
问题描述
来源：LeetCode第238题
难度：中等
给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。 请不要使用除法 ，且在 O(n) 时间复杂度内完成此题。
示例1：
输入: nums = [1,2,3,4] 输出: [24,12,8,6]
示例2：
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内
问题分析
这题让计算数组中每个位置的值是其他所有元素的乘积，但不能使用除法。我们可以先计算每个位置左边所有元素的乘积，然后再计算右边所有元素的乘积，那么当前位置的值就是左边所有元素的乘积与右边所有元素乘积的积，如下图所示。
打开网易新闻 查看精彩图片
JAVA：
public int[] productExceptSelf(int[] nums) { int length = nums.length; int[] res = new int[length]; res[0] = 1; // 先计算当前位置左边所有元素的乘积。 for (int i = 1; i < length; i++) res[i] = res[i - 1] * nums[i - 1]; int right = 1;// 当前位置右边所有元素的乘积。 // 左边和右边的乘积就是当前位置的值。 for (int i = length - 1; i >= 0; i--) { res[i] *= right; right *= nums[i]; } return res; }C++：
public: vector
productExceptSelf(vector
& nums) { int length = nums.size(); vector
res(length); res[0] = 1; // 先计算当前位置左边所有元素的乘积。 for (int i = 1; i < length; i++) res[i] = res[i - 1] * nums[i - 1]; int right = 1;// 当前位置右边所有元素的乘积。 // 左边和右边的乘积就是当前位置的值。 for (int i = length - 1; i >= 0; i--) { res[i] *= right; right *= nums[i]; } return res; }
Python：
def productExceptSelf(self, nums: List[int]) -> List[int]: length = len(nums) res = [0] * length res[0] = 1 # 先计算当前位置左边所有元素的乘积。 for i in range(1, length): res[i] = res[i - 1] * nums[i - 1] right = 1 # 当前位置右边所有元素的乘积。 # 左边和右边的乘积就是当前位置的值。 for i in range(length - 1, -1, -1): res[i] *= right right *= nums[i] return res笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴