Typescript 编码编年史：除 Self 之外的数组的乘积

百变鹏仔 3天前 #JavaScript

文章标签乘积

问题陈述：

给定一个整数数组nums，返回一个数组answer，使得answer[i]等于除nums[i]之外的nums所有元素的乘积。

任何 nums 的前缀或后缀的乘积都保证适合 32 位整数。

您必须编写一个在 o(n) 时间内运行并且不使用除法运算的算法。

示例1：

示例2：

限制条件：

跟进：

你能以 o(1) 的额外空间复杂度解决这个问题吗？（输出数组不计为空间复杂度分析的额外空间。）

初步思考过程：

为了解决这个问题，我们需要计算除当前元素之外的所有元素的乘积，而不使用除法运算。这可以通过对数组使用两次传递来完成：

计算每个元素的前缀积。
计算每个元素的后缀乘积并与前缀乘积相乘。

基本解决方案：

我们可以用两个数组来存储前缀和后缀的乘积，然后相乘得到最终的结果。

代码：

function productexceptself(nums: number[]): number[] {    const n = nums.length;    const prefixproducts = new array(n).fill(1);    const suffixproducts = new array(n).fill(1);    const result = new array(n).fill(1);    // compute prefix products    for (let i = 1; i = 0; i--) {        suffixproducts[i] = suffixproducts[i + 1] * nums[i + 1];    }    // compute the result by multiplying prefix and suffix products    for (let i = 0; i <h3>      时间复杂度分析：</h3>

限制：

基本解决方案效果很好，但需要额外的空间来存储前缀和后缀产品。

优化方案：

我们可以通过使用输出数组首先存储前缀产品，然后就地修改它以包含后缀产品来优化解决方案以使用 o(1) 额外空间。

代码：

function productexceptselfoptimized(nums: number[]): number[] {    const n = nums.length;    const result = new array(n).fill(1);    // compute prefix products in the result array    for (let i = 1; i = 0; i--) {        result[i] = result[i] * suffixproduct;        suffixproduct *= nums[i];    }    return result;}

时间复杂度分析：

基本解决方案的改进：

边缘情况和测试：

边缘情况：

数组包含零。
数组包含负数。
数组长度是最小（2）或最大（10^5）限制。

测试用例：

console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]console.log(productExceptSelf([0,0])); // [0,0]console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2console.log(productExceptSelf([1,2])); // [2, 1]console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]console.log(productExceptSelfOptimized([0,0])); // [0,0]console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2console.log(productExceptSelfOptimized([1,2])); // [2, 1]

一般解决问题的策略：

理解问题：仔细阅读问题陈述，了解要求和约束。
识别关键操作：确定需要的关键操作，例如计算前缀和后缀乘积。
优化可读性： 使用清晰简洁的逻辑，确保代码易于理解。
彻底测试： 使用各种情况（包括边缘情况）测试解决方案，以确保正确性。

识别类似问题：

前缀和数组：
就地算法：
数组操作：

结论：

通过练习此类问题和策略，您可以提高解决问题的能力，并为各种编码挑战做好更好的准备。

文章推荐