5457. 和为奇数的子数组数目 [medium]

第 31 场双周赛 https://leetcode-cn.com/contest/biweekly-contest-31

https://leetcode-cn.com/contest/biweekly-contest-31/problems/number-of-sub-arrays-with-odd-sum/

给你一个整数数组 arr 。请你返回和为奇数的子数组数目。

由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。

示例 1：

输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。

示例 2 ：

输入：arr = [2,4,6]
输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。

示例 3：

输入：arr = [1,2,3,4,5,6,7]
输出：16

示例 4：

输入：arr = [100,100,99,99]
输出：4

示例 5：

输入：arr = [7]
输出：1

提示：

1 <= arr.length <= 10^5
1 <= arr[i] <= 100

First Try

2020-07-25

这道题的套路其实已经很熟悉，但读错题了，整整花费了一个小时还没做出来。

看题以为是在整个数组中任选元素组成子列表，用DP本来也不难，但又要考虑数字重复的问题, 复杂度就一路往上走了。最后写出来了，结果发现测试案例就是不对，尤其是arr = [100, 100, 99, 99]，手算和代码都应该只有3种可能([99], [100, 99], [100, 100, 99])，怎么变成4种可能？看了好久才发现要找的是连续的子列表，这样就没有所谓重复元素的问题了。。。

问题理解清楚了，按照套路一路走下去就行了。使用两个数组储存奇数和偶数的情况, 定义为在位置idx的时候，以idx为最后一个元素的子数组的数量。

对于每一个新的元素，如果是奇数，考虑当前元素为结尾的奇数数量，上上一个元素结尾的所有偶数数量（因为偶数的话加上这个元素就是奇数了），然后再加上这个元素单独存在的列表数量1，结果就是odd[cidx] = even[cidx - 1] + 1。对应的有4种情况按类似分析就行。

对于odd缓存列表里的元素，由于在idx位置保存的是以arr[idx]结尾的奇数数组的数量，可以看出根据定义它们之间互不干扰，因此最后的结果就是把odd列表里的数值相加。

bingo, 搞定。

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        
        # 记录将arr[i]作为右端点的even和odd数量
        even = [""] * (n + 1) 
        odd = [""] * (n + 1) 
        even[0], odd[0] = 0, 0 
        for i in range(n):         
            cidx = i + 1
            if arr[i] % 2 == 0:
                even[cidx] = even[cidx - 1] + 1  # 需要补充当前元素独立存在
                odd[cidx] = odd[cidx - 1]
            else:
                even[cidx] = odd[cidx - 1]
                odd[cidx] = even[cidx - 1] + 1  # 补充当前奇数元素独立存在
        return sum(odd) % (10 ** 9 + 7) 

Failed Try

2020-07-25

还是错误理解了题意，以为是在列表里任意选择元素组成子列表。

对于重复元素，首先对列表进行排序，然后遇到重复元素的时候，考虑仅增加上一个重复元素针对其上一个元素的增量。比如考虑[2, 10, 10], 三轮偶数组合依次是[2], [2], [2, 10], [10], [2], [2, 10], [10], [2, 10], [2, 10, 10], [10, 10], [10]，第三轮如果不考虑上一个元素的重复，直接就出现重复部分。但是仅考虑增量部分就没有问题，遇到第二个10的时候，仅仅对上一轮里面的后缀为第一个10的列表进行增量。

最后测试了几个数组，感觉应该是对的了。但是跟题目给出的案例不一致，尤其是[100, 100, 99, 99]算出来应该是3，结果题目是4.从这里才意识到题目理解错误了。

# 靠，题目理解错了。。
# 为了应对重复，还是得上cache才行
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        arr = sorted(arr)
        
        odd = [""] * (n + 1)
        even = [""] * (n + 1)
        odd[0], even[0] = 0, 0 
        
        for i in range(1, n + 1):
            if arr[i - 1] % 2 == 0:
                if i >= 2 and arr[i - 1] == arr[i - 2]:
                    even[i] = even[i - 1] + even[i - 1]  - even[i - 2]
                    odd[i] = odd[i - 1] + odd[i - 1] - odd[i - 2]
                else:
                    odd[i] = odd[i - 1] + odd[i - 1]  # 原来的奇数， 每个奇数再加上这个元素还是奇数
                    even[i] = even[i - 1] + even[i - 1] + 1 # 原来的偶数，再加上这个偶数还是偶数，然后再考虑到这个元素本身
            else:
                if i >= 2 and arr[i - 1] == arr[i - 2]:
                    even[i] = odd[i - 1] + even[i - 1]  - even[i - 2]
                    odd[i] = even[i - 1] + odd[i - 1] - odd[i - 2]
                else:
                    odd[i] = odd[i - 1] + even[i - 1] +  1 # 原来的偶数加上当前的奇数，变成奇数
                    even[i] = even[i - 1] + odd[i - 1]  # 原来的奇数加上当前奇数，都变成偶数
                

        return odd[n]

failed try 2

还是题意本身理解错误。其次在错误题意的理解中，如何去除重复元素没考虑到。

# 还是得用dp才行啊，管他是否重复
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        # 到目前位置奇数对的数量，到目前位置偶数对的数量。。。
        # 问题在于是否需要考虑重复的问题。。。
        odd, even = 0, 0  
        for a in arr:
            if a % 2 == 0:
                new_even = even * 2  + 1# 每个数组都加上当前偶数，加上之前的，可以多一倍， 还有其自身
                new_odd = odd * 2  # 原来的奇数组加上这个元素，还是奇数组
            else:
                new_odd = odd + even + 1 # 对每个偶数数组都加上一个奇数
                new_even = even + odd  
            even, odd = new_even, new_odd
        return odd 
        

failed try 1

首先题意就理解错误了，以为是在列表里选择任意的元素组成子列表，参考First Try里的解释。其次在这个错误题意理解下，还是没做出来。

打算使用组合数列来做，由于是奇偶数，去除元素的识别，只按照奇数和偶数进行统计。

然后考虑对于任意偶数的集合，搭配上奇数个奇数，结果就是奇数。

在两个地方悲剧了：一是重复元素如何处理，二是两个奇数其实还是偶数，也要叠加到偶数的统计里面去。

这两个问题一考虑，要考虑的东西就爆炸了，觉得还是得用上动态规划解法。

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # 首先去重，相同的数字没作用。但是两个奇数可以凑成一个偶数来使用，wtf...
        arr = list(set(arr))
        odd, even = 0, 0 
        for a in arr:
            if a % 2 == 0:
                even += 1
            else:
                odd += 1
        # 结果应该是每次选择奇数个奇数，然后任意个偶数
        # 任意个偶数为 2^even种可能
        # 奇数则为C(n, 奇数)， 奇数一直排列到odd的次数
        
        def choice(n, i):
            return math.factorial(n) // ( math.factorial(i) * math.factorial(n - i))
        rv = 0 
        count_even = 2 ** even 
        for i in range(1, odd + 1, 2):  # odd + 1 而非odd
            print("i, odd", i, odd)
            rv += choice(odd, i) * count_even 
        return rv % (10 ** 9 + 7)