全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：不含101的数
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
小明在学习二进制时，发现了一类不含101的数，也就是：
将数字用二进制表示，不能出现101。
现在给定一个正整数区间[l,r]，请问这个区间内包含了多少个不含101的数？
输入描述：
输入的唯一一行包含两个正整数l,r(1<=l<r<=109)。
输出描述：
输出的唯一一行包含一个整数，表示在[l,r]区间内一共有几个不含101的数。
示例1
输入：
1 10
输出：
8
说明：
区间[1,10]内，5的二进制表示为101，10的二进制表示为1010，因此除了5与10不满足条件外，其他数字都满足条件，因此答案为8。
示例2
输入：
10 20
输出：
7
说明：
区间[10,20]内，满足条件的数字有[12,14,15,16,17,18,19]，因此答案为7。
解题思路：暴力算法，会导致部分用例超时。
本题非常简单，就是使用Integer.toBinaryString将十进制转化为二进制，然后判断是否存在101。
package com.codernav.demo.hwod.exam;
import java.util.Scanner;
/**
* @title 不含101的数
* @Description 小明在学习二进制时，发现了一类不含101的数，也就是：
* 将数字用二进制表示，不能出现101。
* 现在给定一个正整数区间[l,r]，请问这个区间内包含了多少个不含101的数？
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
int r = sc.nextInt();
int res = r - l + 1;
for (int i = l; i <= r; i++) {
String binary = Integer.toBinaryString(i);
if (binary.contains("101")) {
res--;
}
}
System.out.println(res);
}
}
算法二（解题思路）：以下是满分Java题解
因为0和1也不满足101，所有我们设置dp[0]=1,dp[1]=2
下面是二进制11，也就是3的满二叉树（虽是三层树，但是根节点不计数，所以我们看成2层），因为图中不包含101，所以结果是dp[2]=4
下面是111，也就是7的满二叉树，因为包含一个101，所以结果是dp[3]=7
从上面两张图其实可以看出来，三层树的左子树其实就相当于二层满二叉树，也就是说
dp[3] = dp[2] + 右子树
而右子树的根节点肯定是1，右子树的左子树的根节点肯定是0，而右子树的左子树的右子树的根节点又是1，满足101，如图所示：
这条线肯定是要被抛弃的，那就是需要加上右子树的左子树的左子树，也就是需要加上下两层的左子树，而上一步我们推导出：左子树 = 下一层的满二叉树，转换一下就是需要加上下三层的满二叉树：
dp[3] = dp[3-1] + dp[3-3] + 右子树的右子树
满二叉树除了根节点不一样外，其实其他节点都是一样的，也就是说右子树的右子树等于左子树的右子树，如图：
左子树的右子树 = 下一层的满二叉树 – 下一层的左子树，上面我们求得了左子树 = 下一层的满二叉树，那么左子树的右子树 = 下一层的满二叉树 – 下下层的满二叉树；最终得出结论：
dp[3] = dp[3-1] + dp[3-3] + dp[3-1] – dp[3-2]
= dp[2] + dp[0] + dp[2] – dp[1]
= 4 + 1 + 4 – 2= 7
再给大家展示一下1111，也就是15的满二叉树感受一下：
dp[4] = dp[3] + dp[1] + dp[3] – dp[2] = 7 + 2+ 7 – 4 = 12
最终得出结论：满足二叉树的不包含101的个数公式为：
dp[n] = dp[n-1] + dp[n-3] + dp[n-1] + dp[n-2] (n>2)
dp[0] = 1
dp[1] = 2
dp[2] = 4
以上讨论的是满二叉树的情况，那么非满二叉树的情况呢？
首先判断是否存在右子树，因为如果存在右子树，那么左子树就是满二叉树，直接套用公式：
如110，也就是6的情况：
首先让6 & 2^3=8进行与运算，110&1000=0，说明在4层没有右子节点；
继续跟2^2 = 4进行与运算，110&100 = 100 != 0，说明有右子节点，左子树为2层满二叉树res + dp[2] = 4，记录根节点值为pre=1；
6-4 & 2^1 = 10&10=10，说明有右子树，因为pre=1，说明左子树的右子树满足101，所以只要加上res + dp[1-1] = res + dp[0] = 5，更新 preOfPre = pre = 1，pre = 1；
2-2 & 2^0 = 0 & 0 == 0，说明没有右子节点，且已经到底了，需要再加1，最终结果
4+1+1 = 6（包含0）
package com.codernav.demo.hwod.exam;
import java.util.Scanner;
/**
* @title 不含101的数
* @Description 小明在学习二进制时，发现了一类不含101的数，也就是：
* 将数字用二进制表示，不能出现101。
* 现在给定一个正整数区间[l,r]，请问这个区间内包含了多少个不含101的数？
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
int r = sc.nextInt();
//因为右边界也包含在内，所以右侧需要-1
int res = handle(r) - handle(l - 1);
System.out.println(res);
}
public static int handle(int num) {
//10^9=1,000,000,000；2^30=1,073,741,824；数组长度设定为30
int[] dp = new int[31];
dp[0] = 1; //0
dp[1] = 2; //0,1
dp[2] = 4; //00,01,10,11
for (int i = 3; i < 31; i++) {
dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 1] - dp[i - 2];
}
// preOfPre 记录上上一层的根节点值
// pre 记录上一层的根节点值
// res 记录最终路径数
int preOfPre = 0, pre = 0, count = 0;
for (int i = 29; i >= 0; i--) {
//位运算，用来判断是否包含右子树
int val = 1 << i;
//判断当前子树是否有右子树
if ((num & val) != 0) {
// 有右子树
num -= val;
if (pre == 1) {
//上节点为1则说明左子树（满二叉树）的右子树不符合要求
//只能将左子树的左子树dp[i-1]（满二叉树）加到结果中
count += i == 0 ? 1 : dp[i - 1];
} else {
count += dp[i]; // 先将左子树dp[i]（满二叉树）加到结果中
}
//出现了“101”的情况说明下面都可以忽略了
if (preOfPre == 1 && pre == 0) {
break;
}
//更新上上节点值，标记当前根节点为 1
preOfPre = pre;
pre = 1;
} else {
// 无右子树，此时不能保证左子树是否为满二叉树，所以要在下一层再继续判断
//更新上上节点值，标记当前根节点为 0
preOfPre = pre;
pre = 0;
}
//不能忘记最后一层的最后一个数
if (i == 0) {
count += 1;
}
}
return count;
}
}
相关文章
