leetcode
leetcode 2201 ~ 2250
乘积为偶数的子数组数

乘积为偶数的子数组数

难度:

标签:

题目描述

代码结果

运行时间: 67 ms, 内存: 27.1 MB


/*
 * 思路:
 * 1. 使用Java Stream API, 遍历数组, 生成所有子数组。
 * 2. 对每个子数组, 计算其乘积, 如果乘积是偶数, 则计数器加一。
 * 3. 返回计数器的值。
 */
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
    public long countEvenProductSubarrays(int[] nums) {
        return IntStream.range(0, nums.length)
                .boxed()
                .flatMap(i -> IntStream.range(i, nums.length)
                        .mapToObj(j -> IntStream.rangeClosed(i, j).map(k -> nums[k]).toArray()))
                .mapToLong(subarray -> {
                    int product = 1;
                    for (int num : subarray) {
                        product *= num;
                    }
                    return product % 2 == 0 ? 1 : 0;
                })
                .sum();
    }
}

解释

方法:

本题解采用动态规划思想,通过统计子数组内奇数的数量来确定子数组乘积的奇偶性。首先,对于数组中的每个元素,如果它是奇数,计数器 dp 自增;如果是偶数,则计算以当前偶数结束的子数组中奇数的数量,并更新累计答案 ans。最后,通过总子数组数量减去含有奇数乘积的子数组数量来得到乘积为偶数的子数组数量。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在处理数组时要在末尾添加一个额外的偶数元素,这对算法的逻辑有什么具体影响?
在数组末尾添加一个额外的偶数元素是为了确保最后一个可能的奇数子数组被正确地处理和统计。因为算法中的逻辑是在遇到偶数时,计算以该偶数结束的子数组中包含奇数乘积的子数组数量,并重置奇数计数器。如果数组的最后一个元素是奇数,不添加偶数元素的话,这些奇数会形成的子数组将不会被考虑在最终的统计中。因此,添加一个偶数可以触发对这部分子数组的处理,确保所有可能的子数组都被正确计算。
🦆
在计算以x结尾的子数组中奇数乘积的子数组数量时,为什么使用`ans -= dp * (dp + 1)`这个公式?这个公式是如何推导出来的?
这个公式用于计算以偶数结尾并且包含奇数乘积的子数组的数量。公式 `dp * (dp + 1)` 是基于组合计数原理推导的。其中 `dp` 表示到当前位置为止奇数的总数,`dp * (dp + 1) / 2` 表示所有可能的以奇数结尾的连续子数组数量。由于我们计算的是以偶数结束的子数组数量,整个公式 `dp * (dp + 1)` 实际上计算的是这些以奇数结尾的子数组与当前偶数形成新的以偶数结尾的子数组的数量。由于算法的目标是统计奇数乘积的子数组,所以这个公式会从总数中减去,以得到乘积为偶数的子数组数量。
🦆
在重置奇数计数器dp后,为什么不需要对之前的奇数计数进行任何其他操作或保存?
算法中,在遇到偶数并处理完所有相关子数组后重置奇数计数器 `dp` 是因为我们只关心以当前位置结尾的子数组。之前的奇数计数已经在遇到每个偶数时被充分利用,计算了所有以那些偶数结尾的子数组数量。重置 `dp` 是为了重新开始计数新一段的奇数,之前的计数已经不再需要,因为它们对于后续的子数组计算已无影响。
🦆
如何确保在算法中遍历结束时,所有的子数组都已经被正确地计算了?特别是在遇到最后一个元素为奇数时。
通过在数组末尾添加一个额外的偶数元素,我们确保了即使数组的最后一个元素是奇数,所有以它为结束点的子数组也会被计算。这样做的原因是因为算法在遇到偶数时会计算以此为结尾的、包含奇数乘积的子数组数量,并进行重置,从而处理所有之前的连续奇数。添加的偶数确保这一逻辑也适用于原数组的最后一个元素(如果它是奇数的话)。这种方法保证了所有子数组被遍历并正确计算,无论它们的结束元素是奇数还是偶数。

相关问题