1955-统计特殊子序列的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

特殊序列 是由 正整数 个 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][j] 表示使用 nums}[0..i] 中的元素可以组成的类型为 j 的子序列的数目。其中 j 的取值范围为 {0, 1, 2\，它们表示：

  • 当 j=0 时，表示由正整数个 0 组成的子序列；

  • 当 j=1 时，表示由正整数个 0 紧接着正整数个 1 组成的子序列；

  • 当 j=2 时，表示正整数个 0 紧接着正整数个 1，最后正整数个 2 组成的子序列，也就是题目描述中的「特殊序列」。

在进行状态转移时，我们可以考虑 nums}[i] 的值：

  • 当 nums}[i] = 0 时，我们可以在每一个使用 nums}[0..i-1] 中的元素组成的类型为 0 的子序列之后添加这个 0，得到额外的 f[i-1][0] 个类型为 0 的子序列。此外，这个 0 也可以单独构成一个新的类型为 0 的子序列。因此 f[i][0] 比 f[i-1][0] 多出了 f[i-1][0] + 1，即有状态转移方程：

    f[i][0] = 2 \cdot f[i-1][0] + 1

    而对于 f[i][1] 和 f[i][2]，并没有新的子序列生成，因此它们各自保持 f[i-1][1] 与 f[i-1][2] 的值不变。

  • 当 nums}[i] = 1 时，我们可以在每一个使用 nums}[0..i-1] 中的元素组成的类型为 1 的子序列之后添加这个 1，得到额外的 f[i-1][1] 个类型为 1 的子序列；也可以在每一个类型为 0 的子序列之后添加这个 1，得到额外的 f[i-1][0] 个类型为 1 的子序列。因此 f[i][1] 比 f[i-1][1] 多出了 f[i-1][0] + f[i-1][1]，即有状态转移方程：

    f[i][1] = 2 \cdot f[i-1][1] + f[i-1][0]

    而对于 f[i][0] 和 f[i][2]，并没有新的子序列生成，因此它们各自保持 f[i-1][0] 与 f[i-1][2] 的值不变。

  • 当 nums}[i] = 2 时，我们可以在每一个使用 nums}[0..i-1] 中的元素组成的类型为 2 的子序列之后添加这个 2，得到额外的 f[i-1][2] 个类型为 1 的子序列；也可以在每一个类型为 1 的子序列之后添加这个 2，得到额外的 f[i-1][1] 个类型为 2 的子序列。因此 f[i][2] 比 f[i-1][2] 多出了 f[i-1][1] + f[i-1][2]，即有状态转移方程：

    f[i][2] = 2 \cdot f[i-1][2] + f[i-1][1]

    而对于 f[i][0] 和 f[i][1]，并没有新的子序列生成，因此它们各自保持 f[i-1][0] 与 f[i-1][1] 的值不变。

最终的答案即为 f[n-1][2]，其中 n 是数组 nums 的长度。

细节

当 i=0 时，f[i-1][..] 不是合法的状态，因此我们可以规定 f[i-1][..] = 0，使其可以正确地进行转移。

此外，在状态转移方程中，f[i][j] 只会从 f[i-1][..] 转移而来，因此我们可以使用两个长度为 3 的一维数组代替 f 的二维数组，交替地进行状态转移。而本题的状态转移更加特殊，对于每一个 i，只会有一个 f[i][j] 与 f[i-1][j] 的值不同，另外两个的值不会发生变化，因此我们只需要使用一个长度为 3 的一维数组，甚至直接使用 3 个变量进行状态转移即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int countSpecialSubsequences(vector<int>& nums) {
        int f0 = 0, f1 = 0, f2 = 0;
        for (int num: nums) {
            if (num == 0) {
                f0 = (f0 * 2 + 1) % mod;
            }
            else if (num == 1) {
                f1 = (f1 * 2 % mod + f0) % mod;
            }
            else {
                f2 = (f2 * 2 % mod + f1) % mod;
            }
        }
        return f2;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f0 = f1 = f2 = 0
        for num in nums:
            if num == 0:
                f0 = (f0 * 2 + 1) % mod
            elif num == 1:
                f1 = (f1 * 2 + f0) % mod
            else:
                f2 = (f2 * 2 + f1) % mod
        return f2

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
1955-统计特殊子序列的数目