不合法的二进制数是什么
2025-05-04 05:19:20
面试李组长
已认证
已认证面试李组长为您分享以下优质知识
不合法的二进制数是指在其二进制表示中包含连续两个11的数。例如，二进制数`110`、`111`和`1011`都是不合法的，因为它们分别包含子串`11`。
示例说明
合法二进制数：`1010`（不包含连续11）、`1001`（不包含连续11）
非法二进制数：`110`（包含`11`）、`111`（包含`11`）、`1011`（包含`11`）
计算不合法二进制数的数量
给定n位二进制数，要求其中不包含连续两个11的数的数量，结果需对$10^9+7$取余。该问题可以通过动态规划解决：
定义状态
- `dp[i]`：表示长度为i且以0结尾的不合法二进制数数量
- `dp[i]`：表示长度为i且以1结尾的不合法二进制数数量
状态转移方程
- `dp[i] = dp[i-1] + dp[i-1]`（在合法结尾0或1后添加0均合法）
- `dp[i] = dp[i-1]`（仅在合法结尾0后添加1合法，避免连续两个1）
初始条件
- `dp = 1`（`0`是合法）
- `dp = 1`（`1`是合法）
最终结果
- 总不合法数 = `dp[n] + dp[n]`，取模$10^9+7$
示例计算（n=3）
`dp = 2`（`00`, `01`）
`dp = 1`（`10`）
`dp = 3`（`000`, `001`, `010`）
`dp = 2`（`100`, `101`）
总不合法数 = `3 + 2 = 5`（对应`011`, `110`, `111`）
注意事项
该算法的时间复杂度为O（n），适用于n≤100的情况
结果需对$10^9+7$取余，防止整数溢出
