华为OD机试2023：寻找不含101二进制数

"华为OD机试真题，2023年Java与JavaScript编程题，涉及不含特定二进制序列的正整数计数问题。" 该编程题目的目标是计算给定正整数区间[l, r]内，不包含二进制表示中的“101”序列的数的数量。这道题目主要考察的是二进制操作和动态规划的思维。 首先，我们可以采用暴力解法，将区间内的每个数转化为二进制字符串，然后检查字符串是否包含“101”。如果包含，则从总数中减去1，最后输出剩余的数。如示例代码所示，这种解法虽然简单，但在面对较大的输入值时可能会导致超时。 为了优化解决方案，我们可以考虑使用动态规划(DP)的方法。由于“101”序列在二进制中不被允许，我们可以根据二进制的每一位来构建状态转移方程。我们可以定义DP数组dp[i]表示长度为i的二进制串不包含“101”的数量。 对于任何长度为i的二进制串，有两种情况： 1. 最后一位是0：那么这个二进制串可以看作是在长度为i-1的二进制串后面添加了一个0，即dp[i] = dp[i-1]。 2. 最后一位是1：此时，如果长度为i-1的二进制串末尾不是1（否则会形成“101”），则可以添加一个1；如果长度为i-2的二进制串末尾不是1（避免形成“101”），则可以添加01。因此，dp[i] = dp[i-1] + dp[i-2] - dp[i-3]，其中减去dp[i-3]是因为我们需要排除末尾为“101”的情况。 初始状态为dp[0] = 1（空串），dp[1] = 2（0和1），dp[2] = 4（00, 01, 10）。接下来，我们可以根据这些状态转移方程计算出dp数组的值，最后dp[r]即为答案。 注意，当计算dp[i]时，我们只需要关注dp[i-1]、dp[i-2]和dp[i-3]，因为这是由二进制串的构造规则决定的。这样的方法可以避免遍历整个区间，大大提高了效率。 通过这种方法，我们可以快速计算出给定区间内不含“101”的数的个数，即使对于大范围的输入也能保证在限制的时间内完成计算。