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。

解释：

两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 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] 进行取模操作，并处理可能的负数情况。

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] = 0 } else { dp[i][j][lastBit] = 1 } } else if j == 0 { if lastBit == 1 || i > limit { dp[i][j][lastBit] = 0 } else { dp[i][j][lastBit] = 1 } } else 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] %= MOD if dp[i][j][lastBit] < 0 { dp[i][j][lastBit] += MOD } } } } return (dp[zero][one][0] + dp[zero][one][1]) % MOD}func main() { zero := 1 one := 1 limit := 2 fmt.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));}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP