3129：找出所有稳定的二进制数组 I（2200 分）

Ian

2024-04-27 约 734 字预计阅读 2 分钟次阅读

力扣第 129 场双周赛第 3 题

题目

给你 3 个正整数 zero ，one 和 limit 。

一个二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：

0 在 arr 中出现次数恰好为 zero 。
1 在 arr 中出现次数恰好为 one 。
arr 中每个长度超过 limit 的子数组都同时包含 0 和 1 。

请你返回稳定二进制数组的总数目。

由于答案可能很大，将它对 10⁹ + 7 取余后返回。

示例 1：

输入：zero = 1, one = 1, limit = 2

输出：2

解释：

两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。

示例 2：

输入：zero = 1, one = 2, limit = 1

输出：1

解释：

唯一稳定的二进制数组是 [1,0,1] 。

二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

输入：zero = 3, one = 3, limit = 2

输出：14

解释：

所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

提示：

1 <= zero, one, limit <= 200

相似问题：

分析

按最后一个选 0/1 递推
令 f[i][j][0]、f[i][j][1] 分别代表 i 个 0、j 个 1 且结尾是 0/1 的个数
假如结尾是 0
- 考虑从 f[i-1][j] 的数组转移
- f[i-1][j] 中，只有当结尾是 limit 个 0 时，才不能转移
- 结尾是 limit 个 0，即对应了 f[i-1-limit][j] 的数组
- 因此 f[i][j][0] = f[i-1][j]-f[i-1-limit][j]
结尾是 1 可以同理递推

解答

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


class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        mod = 10**9+7
        f = [[[0,0] for _ in range(one+1)] for _ in range(zero+1)]
        for i in range(1,min(limit,zero)+1):
            f[i][0][0] = 1
        for j in range(1,min(limit,one)+1):
            f[0][j][1] = 1
        for i in range(1,zero+1):
            for j in range(1,one+1):
                f[i][j][0] = sum(f[i-1][j])-(f[i-1-limit][j][1] if i>limit else 0)
                f[i][j][1] = sum(f[i][j-1])-(f[i][j-1-limit][0] if j>limit else 0)
        return sum(f[-1][-1])%mod

242 ms

目录

3129：找出所有稳定的二进制数组 I（2200 分）

题目

分析

解答