原文链接: https://leetcode-cn.com/problems/count-number-of-special-subsequences

英文原文

A sequence is special if it consists of a positive number of 0s, followed by a positive number of 1s, then a positive number of 2s.

• For example, [0,1,2] and [0,0,1,1,1,2] are special.
• In contrast, [2,1,0], [1], and [0,1,2,0] are not special.

Given an array nums (consisting of only integers 0, 1, and 2), return the number of different subsequences that are special. Since the answer may be very large, return it modulo 109 + 7.

A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are different if the set of indices chosen are different.

 

Example 1:

Input: nums = [0,1,2,2]
Output: 3
Explanation: The special subsequences are bolded [0,1,2,2], [0,1,2,2], and [0,1,2,2].

Example 2:

Input: nums = [2,2,0,0]
Output: 0
Explanation: There are no special subsequences in [2,2,0,0].

Example 3:

Input: nums = [0,1,2,0,1,2]
Output: 7
Explanation: The special subsequences are bolded:
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 2

中文题目

特殊序列 是由 正整数 个 0 ，紧接着 正整数 个 1 ，最后 正整数 个 2 组成的序列。

• 比方说，[0,1,2] 和 [0,0,1,1,1,2] 是特殊序列。
• 相反，[2,1,0] ，[1] 和 [0,1,2,0] 就不是特殊序列。

给你一个数组 nums （仅 包含整数 0，1 和 2），请你返回 不同特殊子序列的数目 。由于答案可能很大，请你将它对 109 + 7 取余 后返回。

一个数组的 子序列 是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 下标集合 不同，那么这两个子序列是 不同的 。

 

示例 1：

输入：nums = [0,1,2,2]
输出：3
解释：特殊子序列为 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。

示例 2：

输入：nums = [2,2,0,0]
输出：0
解释：数组 [2,2,0,0] 中没有特殊子序列。

示例 3：

输入：nums = [0,1,2,0,1,2]
输出：7
解释：特殊子序列包括：
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 2

通过代码

高赞题解

定义：

• $f[i][0]$ 表示前 $i$ 项得到的全 $0$ 子序列个数
• $f[i][1]$ 表示前 $i$ 项得到的先 $0$ 后 $1$ 的子序列个数
• $f[i][2]$ 表示前 $i$ 项得到的特殊子序列个数

遍历数组 $\textit{nums}$，对于 $f[i][j]$，若 $j \neq \textit{nums}[i]$，则直接从前一项转移过来，即 $f[i][j]=f[i-1][j]$。

若 $j = \textit{nums}[i]$ 则需要分类计算：

对于 $f[i][0]$，当遇到 $0$ 时，有选或不选两种方案，不选 $0$ 时有 $f[i][0] = f[i-1][0]$，选 $0$ 时，可以单独组成一个子序列，也可以与前面的 $0$ 组合，因此有 $f[i][0] = f[i-1][0] + 1$，两者相加得 $f[i][0] = 2\cdot f[i-1][0] + 1$。

对于 $f[i][1]$，当遇到 $1$ 时，有选或不选两种方案，不选 $1$ 时有 $f[i][1] = f[i-1][1]$，选 $1$ 时，可以单独与前面的 $0$ 组成一个子序列，也可以与前面的 $1$ 组合，因此有 $f[i][1] = f[i-1][1] + f[i-1][0]$，两者相加得 $f[i][1] = 2\cdot f[i-1][1] + f[i-1][0]$。

$f[i][2]$ 和 $f[i][1]$ 类似，有 $f[i][2] = 2\cdot f[i-1][2] + f[i-1][1]$。

最后答案为 $f[n-1][2]$。

代码实现时，可以把第一维压缩掉。

const mod int = 1e9 + 7

func countSpecialSubsequences(nums []int) int {
	f := [3]int{}
	for _, v := range nums {
		if v == 0 {
			f[0] = (f[0]*2 + 1) % mod
		} else if v == 1 {
			f[1] = (f[1]*2 + f[0]) % mod
		} else {
			f[2] = (f[2]*2 + f[1]) % mod
		}
	}
	return f[2]
}

统计信息

通过次数	提交次数	AC比率
2699	5432	49.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言