alighters

程序、写作、人生

1524. Number of Sub-arrays With Odd Sum

| Comments

这一题在周赛花费了不少时间，做题时用了个代码比较长的 dp 方案

方案一

动态规划

定义动态方程

定义一个 n * 2 的二维数组。 dp[i][0] 表示当前以 i 为结尾的子数组和为偶数的方法数 dp[i][1] 表示当前以 i 为结尾的子数组和为奇数的方法数

状态转化方程

  1. nums[i] 为奇数 dp[i][0] = dp[i-1][1] （等于前一个的奇数方案数） dp[i][1] = dp[i-1][0] + 1 （等于前一个的偶数方案数 + 1）
  2. nums[i] 为偶数 dp[i][0] = dp[i-1][0] + 1 dp[i][1] = dp[i-1][1]

最后，dp 数组为奇数的总和，即为满足的结果数。

代码

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(arr) + 1)]
        for i, n in enumerate(arr):
            if n % 2 == 1:
                dp[i + 1][1] = dp[i][0] + 1
                dp[i + 1][0] = dp[i][1]
            else:
                dp[i + 1][0] = dp[i][0] + 1
                dp[i + 1][1] = dp[i][1]
        # print(dp)
        return sum( x for _, x in dp) % (10**9 + 7)

方案二

前缀和

通过前缀和来计算时，这里有个技巧：

奇数 - 偶数 = 奇数 偶数 - 奇数 = 奇数

这里大佬们会用一个长度为 2 的数组，来记录数组索引 i 之前的奇数前缀和、偶数前缀和的结果数。如下表示：

1

pre = [1, 0]

初始状态时，即空数组，我们认为前缀和为偶数的有 1 个，奇数的有 0 个。

所以当计算到 i 时，得到其前缀和为 sum。 1. sum 为偶数时。此时的答案即前面有多少个前缀和为奇数的方案数 2. sum 为奇数时。此时的答案即前面有多少个前缀和为偶数的方案数。

因之前定义的数组大小为 2 ，就很方便进行奇数数的操作记录。

写一个 i 的状态记录方程。

1
2

ans += pre[1 - sum % 2]
pre[sum % 2] += 1

代码

1
2
3
4
5
6
7
8
9
10

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        pre = [1, 0]
        sum = 0
        ans = 0
        for n in arr:
            sum += n
            ans += pre[1 - sum % 2]
            pre[sum % 2] += 1
        return ans % (10 ** 9 + 7)

版权归作者所有，转载请注明原文链接：/blog/2020/09/13/1524-number-of-sub-arrays-with-odd-sum/

给 Ta 个打赏吧...

Comments