2024-12-07：找出所有稳定的二进制数组 Ⅰ。用go语言，给定三个正整数 zero、one 和 limit，定义一个稳定的

2024-12-07：找出所有稳定的二进制数组 Ⅰ。用go语言，给定三个正整数 zero、one 和 limit，定义一个稳定的二进制数组需要满足以下条件：

数组中 0 的数量为 zero，1 的数量为 one，且每个长度超过 limit 的子数组都必须同时包含 0 和 1。

求出满足条件的稳定二进制数组的总数，结果需对 1000000007 取模后返回。

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

输出：2。

解释：

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

答案2024-12-07：

chatgpt[1]

题目来自leetcode3129。

大体步骤如下：

1.初始化变量：

• 初始化动态规划数组 dp，它是一个三维数组，dp[i][j][k] 表示包含 i 个 0 和 j 个 1 的子数组中，最后一个数字是 k 的所有稳定二进制数组的数量。

• 初始化模数 mod 为 1e9 + 7，用于取模操作。

2.动态规划填表：

• 遍历填充 dp 数组，根据限制条件计算每个子问题的解。

• 内层循环处理 0 和 1 的数量，更新 dp[i][j][0] 和 dp[i][j][1] 的值，考虑超过 limit 的限制情况。

3.返回结果：

• 最后返回 (dp[zero][one][0] + dp[zero][one][1]) % mod，即得到满足条件的稳定二进制数组的总数。

总的时间复杂度：

• 填表部分需要二重循环遍历 zero 和 one，时间复杂度为 O(zero * one)，内部还有限制条件的判断，整体时间复杂度为 O(zero * one)。

• 计算结果的取模操作时间复杂度为 O(1)。

总的额外空间复杂度：

• 动态规划数组 dp 的空间复杂度为 O(zero * one)，因此总的额外空间复杂度为 O(zero * one)。

Go完整代码如下：

package main

import(

"fmt"

)

func numberOfStableArrays(zero int, one int, limit int)int{

   dp :=make([][][2]int, zero+1)

   mod :=int(1e9+7)

for i :=0; i <= zero; i++{

       dp[i]=make([][2]int, one+1)

}

for i :=0; i <= min(zero, limit); i++{

       dp[i][0][0]=1

}

for j :=0; j <= min(one, limit); j++{

       dp[0][j][1]=1

}

for i :=1; i <= zero; i++{

for j :=1; j <= one; j++{

if i > limit {

               dp[i][j][0]= dp[i-1][j][0]+ dp[i-1][j][1]- dp[i-limit-1][j][1]

}else{

               dp[i][j][0]= dp[i-1][j][0]+ dp[i-1][j][1]

}

           dp[i][j][0]=(dp[i][j][0]%mod + mod)% mod

if j > limit {

               dp[i][j][1]= dp[i][j-1][1]+ dp[i][j-1][0]- dp[i][j-limit-1][0]

}else{

               dp[i][j][1]= dp[i][j-1][1]+ dp[i][j-1][0]

}

           dp[i][j][1]=(dp[i][j][1]%mod + mod)% 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=1000000007;

fnmin(x:i32, y:i32)->i32{

if x < y {

       x

}else{

       y

}

}

fnnumber_of_stable_arrays(zero:i32, one:i32, limit:i32)->i64{

letmut dp=vec![vec![[0,0]; one asusize+1]; zero asusize+1];

foriin0..=zero {

       dp[i asusize][0][0]=1;

}

forjin0..=one {

       dp[0][j asusize][1]=1;

}

foriin1..=zero {

forjin1..=one {

if i > limit {

               dp[i asusize][j asusize][0]=(dp[i asusize-1][j asusize][0]

+ dp[i asusize-1][j asusize][1]

- dp[(i - limit -1)asusize][j asusize][1])

% MOD;

}else{

               dp[i asusize][j asusize][0]=

(dp[i asusize-1][j asusize][0]+ dp[i asusize-1][j asusize][1])% MOD;

}

if dp[i asusize][j asusize][0]<0{

               dp[i asusize][j asusize][0]+= MOD;

}

if j > limit {

               dp[i asusize][j asusize][1]=(dp[i asusize][j asusize-1][1]

+ dp[i asusize][j asusize-1][0]

- dp[i asusize][j asusize- limit asusize-1][0])

% MOD;

}else{

               dp[i asusize][j asusize][1]=

(dp[i asusize][j asusize-1][1]+ dp[i asusize][j asusize-1][0])% MOD;

}

if dp[i asusize][j asusize][1]<0{

               dp[i asusize][j asusize][1]+= MOD;

}

}

}

(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));

}

在这里插入图片描述引用链接