2024-12-08：找出所有稳定的二进制数组 Ⅱ。用go语言，请实现一个函数，接收三个正整数 zero、one 和 limit

福大大架构师每日一题

发布于 2024-12-09 14:26:11

5700

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 main

import(
"fmt"
)

const MOD =1000000007

func 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
}
}elseif j ==0{
if lastBit ==1|| i > limit {
                        dp[i][j][lastBit]=0
}else{
                        dp[i][j][lastBit]=1
}
}elseif 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;

fnnumber_of_stable_arrays(zero:i32, one:i32, limit:i32)->i64{
letmut dp=vec![vec![vec![0;2];(one +1)asusize];(zero +1)asusize];

foriin0..=zero {
forjin0..=one {
forlast_bitin0..=1{
if i ==0{
if last_bit ==0|| j > limit {
                        dp[i asusize][j asusize][last_bit asusize]=0;
}else{
                        dp[i asusize][j asusize][last_bit asusize]=1;
}
}elseif j ==0{
if last_bit ==1|| i > limit {
                        dp[i asusize][j asusize][last_bit asusize]=0;
}else{
                        dp[i asusize][j asusize][last_bit asusize]=1;
}
}elseif last_bit ==0{
                    dp[i asusize][j asusize][last_bit asusize]=
                        dp[(i -1)asusize][j asusize][0]+ dp[(i -1)asusize][j asusize][1];
if i > limit {
                        dp[i asusize][j asusize][last_bit asusize]-=
                            dp[(i - limit -1)asusize][j asusize][1];
}
}else{
                    dp[i asusize][j asusize][last_bit asusize]=
                        dp[i asusize][(j -1)asusize][0]+ dp[i asusize][(j -1)asusize][1];
if j > limit {
                        dp[i asusize][j asusize][last_bit asusize]-=
                            dp[i asusize][(j - limit -1)asusize][0];
}
}
                dp[i asusize][j asusize][last_bit asusize]%= MOD;
if dp[i asusize][j asusize][last_bit asusize]<0{
                    dp[i asusize][j asusize][last_bit asusize]+= MOD;
}
}
}
}

return(dp[zero asusize][one asusize][0]+ dp[zero asusize][one asusize][1])% MOD;
}

fnmain(){
letzero=1;
letone=1;
letlimit=2;
println!("{}",number_of_stable_arrays(zero, one, limit));
}