本文主要是介绍java数据结构与算法刷题-----LeetCode238. 除自身以外数组的乘积,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
文章目录
- 1. 动态规划:左右乘积列表
- 2. 滚动数组对动态规划过程优化
本题的难点在于,题目要求不能用除法,还不能用额外的空间(除了返回答案所必须)
1. 动态规划:左右乘积列表
解题思路:时间复杂度O( n n n),空间复杂度O( n n n).这个方法只实现了题目要求的不用除法和线性时间复杂度。空间复杂度没有考虑,会在法二中优化 |
---|
- 题目的要求是,对于数组中nums[i],我们要求answer[i]正好是丢弃nums[i]它本身,然后求其余所有元素的乘积。
因此我们将其抽象为:[L区域]i本身[R区域]。也就是求出L和R区域的乘积后,将L和R相乘,就是answer[i] = [L区域]*[R区域]
- 创建两个一维dp数组L和R,分别代表下标i左边所有元素乘积,和下标i右边所有元素乘积。
- 这样对于nums[i],就有了两个乘积,分别代表它左边区域和右边区域的乘积,正好不带i自己玩。
- 最后我们将i两边乘积相乘,就正好得到了题目要求的结果。那就是整个数组除了i以外都相乘在一起。
class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;int[] L = new int[length];int[] R = new int[length];int[] answer = new int[length];L[0] = 1;for (int i = 1; i < length; i++) {L[i] = nums[i - 1] * L[i - 1];}R[length - 1] = 1;for (int i = length - 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}for (int i = 0; i < length; i++) {answer[i] = L[i] * R[i];}return answer;}
}
2. 滚动数组对动态规划过程优化
解题思路:时间复杂度O( n n n),空间复杂度O( 1 1 1) |
---|
- 将上面动态规划的思路换为滚动数组,因为我们发现,result[1]只取决于上次的结果,所以dp数组是不必要的。
- 我们先将L区域直接规划到result中
- 然后在规划R的途中,直接将L*R规划到result中
class Solution {public int[] productExceptSelf(int[] nums) {int size = nums.length;int[] result = new int[size];int L = 1;for (int i = 0; i <= size - 1; ++i) {result[i] = L;L *= nums[i];}int R = 1;for (int i = size - 1; i >= 0; --i) {result[i] *= R;R *= nums[i];}return result;}
}
这篇关于java数据结构与算法刷题-----LeetCode238. 除自身以外数组的乘积的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!