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

福大大架构师每日一题

发布于 2024-12-09 06:25:31

7900

代码可运行

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

运行总次数：0

代码可运行

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