2024-12-08：找出所有稳定的二进制数组 Ⅱ。用go语言，请实现一数_二进制

文章图片

2024-12-08：找出所有稳定的二进制数组 Ⅱ 。用go语言，请实现一个函数，接收三个正整数 zero、one 和 limit 作为输入。函数的任务是计算符合以下条件的稳定二进制数组的数量：
1.数组中的 0 的个数正好为 zero 。
2.数组中的 1 的个数正好为 one 。
3.数组中每个长度超过 limit 的子数组都同时包含 0 和 1 。
计算出符合条件的稳定二进制数组的总数，并返回对 1000000007 取模后的结果。
1 <= zero one limit <= 1000 。
输入：zero = 1 one = 1 limit = 2 。
输出：2 。
解释：
两个稳定的二进制数组为 [10
和 [01
，两个数组都有一个 0 和一个 1，且没有子数组长度大于 2。
答案2024-12-08：
chatgpt[1

题目来自leetcode3130 。
大体步骤如下：1.初始化一个三维数组 dp 来保存中间计算结果，其中 dp[i
[j
[k
表示 0 的个数为 i ， 1 的个数为 j ，最后一个数字是 k 的稳定二进制数组的数量。
2.遍历 i 从 0 到 zero ， j 从 0 到 one ， k 从 0 到 1：

? 如果 i 等于 0：若 lastBit 为 0 或者 j 大于 limit ，则 dp[i
[j
[lastBit
设为 0 ，否则设为 1 。
? 如果 j 等于 0：若 lastBit 为 1 或者 i 大于 limit ，则 dp[i
[j
[lastBit
设为 0 ，否则设为 1 。
? 否则，更新 dp[i
[j
[lastBit
的值，根据前一个状态计算当前稳定数组数量，并考虑限制条件。

3.对于更新后的 dp[i
[j
[lastBit
进行取模操作，并处理可能的负数情况。
【2024-12-08：找出所有稳定的二进制数组 Ⅱ。用go语言，请实现一数】4.返回 (dp[zero
[one
[0
+ dp[zero
[one
[1
) % MOD 作为结果。
时间复杂度分析：

? 遍历三维数组的时间复杂度为 O(zero * one * 2) ，这里表示为 O(n^3) ，其中 n 表示输入参数中的最大值。
? 每个状态更新的操作都是常数时间复杂度的，因此总的时间复杂度为 O(n^3) 。

空间复杂度分析：

? 三维数组 dp 的空间复杂度为 O(zero * one * 2) ，即 O(n^3) 。
? 其他额外变量占用的空间可以忽略不计，因此总的额外空间复杂度为 O(n^3) 。

Go完整代码如下：

package mainimport (\"fmt\")const MOD = 1000000007func numberOfStableArrays(zero int one int limit int) int {dp := make([
[
[
int zero + 1)for i := range dp {dp[i
 = make([
[
int one + 1)for j := range dp[i
 {dp[i
[j
 = make([
int 2)for i := 0; i <= zero; i++ {for j := 0; j <= one; j++ {for lastBit := 0; lastBit <= 1; lastBit++ {if i == 0 {if lastBit == 0 || j > limit {dp[i
[j
[lastBit
 = 0else {dp[i
[j
[lastBit
 = 1else if j == 0 {if lastBit == 1 || i > limit {dp[i
[j
[lastBit
 = 0else {dp[i
[j
[lastBit
 = 1else if lastBit == 0 {dp[i
[j
[lastBit
 = dp[i - 1
[j
[0
 + dp[i - 1
[j
[1
if i > limit {dp[i
[j
[lastBit
 -= dp[i - limit - 1
[j
[1
else {dp[i
[j
[lastBit
 = dp[i
[j - 1
[0
 + dp[i
[j - 1
[1
if j > limit {dp[i
[j
[lastBit
 -= dp[i
[j - limit - 1
[0
dp[i
[j
[lastBit
 %= MODif dp[i
[j
[lastBit
 < 0 {dp[i
[j
[lastBit
 += MODreturn (dp[zero
[one
[0
 + dp[zero
[one
[1
) % MODfunc main() {zero := 1one := 1limit := 2fmt.Println(numberOfStableArrays(zero one limit))

Rust完整代码如下：

const MOD: i64 = 1_000_000_007;fn number_of_stable_arrays(zero: i32 one: i32 limit: i32) -> i64 {let mut dp = vec![vec![vec![0; 2
; (one + 1) as usize
; (zero + 1) as usize
;for i in 0..=zero {for j in 0..=one {for last_bit in 0..=1 {if i == 0 {if last_bit == 0 || j > limit {dp[i as usize
[j as usize
[last_bit as usize
 = 0;else {dp[i as usize
[j as usize
[last_bit as usize
 = 1;else if j == 0 {if last_bit == 1 || i > limit {dp[i as usize
[j as usize
[last_bit as usize
 = 0;else {dp[i as usize
[j as usize
[last_bit as usize
 = 1;else if last_bit == 0 {dp[i as usize
[j as usize
[last_bit as usize
 =dp[(i - 1) as usize
[j as usize
[0
 + dp[(i - 1) as usize
[j as usize
[1
;if i > limit {dp[i as usize
[j as usize
[last_bit as usize
 -=dp[(i - limit - 1) as usize
[j as usize
[1
;else {dp[i as usize
[j as usize
[last_bit as usize
 =dp[i as usize
[(j - 1) as usize
[0
 + dp[i as usize
[(j - 1) as usize
[1
;if j > limit {dp[i as usize
[j as usize
[last_bit as usize
 -=dp[i as usize
[(j - limit - 1) as usize
[0
;dp[i as usize
[j as usize
[last_bit as usize
 %= MOD;if dp[i as usize
[j as usize
[last_bit as usize
 < 0 {dp[i as usize
[j as usize
[last_bit as usize
 += MOD;return (dp[zero as usize
[one as usize
[0
 + dp[zero as usize
[one as usize
[1
) % MOD;fn main() {let zero = 1;let one = 1;let limit = 2;println!(\"{\" number_of_stable_arrays(zero one limit));