Skip to content

Latest commit

 

History

History
209 lines (160 loc) · 5.82 KB

README.md

File metadata and controls

209 lines (160 loc) · 5.82 KB
comments difficulty edit_url tags
true
中等
数组
数学
动态规划
组合数学

3247. 奇数和子序列的数量 🔒

English Version

题目描述

给定一个数组 nums，返回元素和为奇数的 子序列 的数量。

由于答案可能很大，返回答案对 109 + 7 取模。

 

示例 1：

输入：nums = [1,1,1]

输出：4

解释：

奇数和子序列为：[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1].

示例 2：

输入：nums = [1,2,2]

输出：4

解释：

奇数和子序列为：[1, 2, 2], [1, 2, 2], [1, 2, 2], [1, 2, 2].

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

解法

方法一：动态规划

我们定义 $f[0]$ 表示目前为止的子序列中，和为偶数的子序列个数，而 $f[1]$ 表示目前为止的子序列中，和为奇数的子序列个数。初始时 $f[0] = 0$, $f[1] = 0$。

遍历数组 $\textit{nums}$，对于每个数 $x$：

如果 $x$ 为奇数，那么 $f[0]$ 和 $f[1]$ 的更新方式为：

$$ \begin{aligned} f[0] & = (f[0] + f[1]) \bmod 10^9 + 7, \\ f[1] & = (f[0] + f[1] + 1) \bmod 10^9 + 7. \end{aligned} $$

即，当前的和为偶数的子序列个数等于之前的和为偶数的子序列个数，加上之前的和为奇数的子序列拼上当前数 $x$ 的子序列个数；当前的和为奇数的子序列个数等于之前的和为偶数的子序列拼上当前数 $x$ 的子序列个数，加上之前的和为奇数的子序列个数，再加上一个只包含当前数 $x$ 的子序列。

如果 $x$ 为偶数，那么 $f[0]$ 和 $f[1]$ 的更新方式为：

$$ \begin{aligned} f[0] & = (f[0] + f[0] + 1) \bmod 10^9 + 7, \\ f[1] & = (f[1] + f[1]) \bmod 10^9 + 7. \end{aligned} $$

即，当前的和为偶数的子序列个数等于之前的和为偶数的子序列个数，加上之前的和为偶数的子序列拼上当前数 $x$ 的子序列个数，再加上一个只包含当前数 $x$ 的子序列；当前的和为奇数的子序列个数等于之前的和为奇数的子序列拼上当前数 $x$ 的子序列个数，加上之前的和为奇数的子序列个数。

最终，返回 $f[1]$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def subsequenceCount(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f = [0] * 2
        for x in nums:
            if x % 2:
                f[0], f[1] = (f[0] + f[1]) % mod, (f[0] + f[1] + 1) % mod
            else:
                f[0], f[1] = (f[0] + f[0] + 1) % mod, (f[1] + f[1]) % mod
        return f[1]

Java

class Solution {
    public int subsequenceCount(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[2];
        for (int x : nums) {
            int[] g = new int[2];
            if (x % 2 == 1) {
                g[0] = (f[0] + f[1]) % mod;
                g[1] = (f[0] + f[1] + 1) % mod;
            } else {
                g[0] = (f[0] + f[0] + 1) % mod;
                g[1] = (f[1] + f[1]) % mod;
            }
            f = g;
        }
        return f[1];
    }
}

C++

class Solution {
public:
    int subsequenceCount(vector<int>& nums) {
        const int mod = 1e9 + 7;
        vector<int> f(2);
        for (int x : nums) {
            vector<int> g(2);
            if (x % 2 == 1) {
                g[0] = (f[0] + f[1]) % mod;
                g[1] = (f[0] + f[1] + 1) % mod;
            } else {
                g[0] = (f[0] + f[0] + 1) % mod;
                g[1] = (f[1] + f[1]) % mod;
            }
            f = g;
        }
        return f[1];
    }
};

Go

func subsequenceCount(nums []int) int {
	mod := int(1e9 + 7)
	f := [2]int{}
	for _, x := range nums {
		g := [2]int{}
		if x%2 == 1 {
			g[0] = (f[0] + f[1]) % mod
			g[1] = (f[0] + f[1] + 1) % mod
		} else {
			g[0] = (f[0] + f[0] + 1) % mod
			g[1] = (f[1] + f[1]) % mod
		}
		f = g
	}
	return f[1]
}

TypeScript

function subsequenceCount(nums: number[]): number {
    const mod = 1e9 + 7;
    let f = [0, 0];
    for (const x of nums) {
        const g = [0, 0];
        if (x % 2 === 1) {
            g[0] = (f[0] + f[1]) % mod;
            g[1] = (f[0] + f[1] + 1) % mod;
        } else {
            g[0] = (f[0] + f[0] + 1) % mod;
            g[1] = (f[1] + f[1]) % mod;
        }
        f = g;
    }
    return f[1];
}