青海建设兵团青岛战友网站python基础教程(第3版)

不含101的数

题目描述

小明在学习二进制时，发现了一类不含 101的数，也就是：
将数字用二进制表示，不能出现 101 。
现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个二进制不含 101 的整数？

输入描述

输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。

输出描述

输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。

输入	1 10
输出	8
说明	区间 [1,10] 内， 5 的二进制表示为 101 ，10的二进制表示为 1010 ，因此区间 [ 1 , 10 ] 内有 10−2=8 个不含 101的数。

输入	10 20
输出	7
说明	区间 [10,20] 内，满足条件的数字有 [12,14,15,16,17,18,19] 因此答案为 7。

源码和解析
解析：

思路1：
for循环暴力求解。十进制转二进制再转字符串。借助字符串的indexOf来判断是否包含。
这种方式就是区间过大时花费的时间会比较久一些。

示例代码（暴力破解）：

public class T28 {public static void main(String[] args) {String input="1 10";int left=Integer.parseInt(input.split(" ")[0]);int right=Integer.parseInt(input.split(" ")[1]);int count=right-left+1;// 二进制不包含101的个数for(;left<=right;left++){if(Integer.toBinaryString(left).indexOf("101")!=-1){count--;}}System.out.println(count);}
}

当输入的值为10和20时，测试输出与结果如下图：

解析：

思路2：使用简单数位DP算法（数不再是数，而是由多个单字符组成的字符）进行求解
若对数位DP算法不懂的，可以参考我的另一篇博客
【算法】使用数位算法生成0至某个数之间的整数（for循环之外的另一种实现方式，蛮长见识的）

public class T28 {public static int raw[] = null;public static int num[] = null;public static int count = 0;public static void main(String[] args) {String input = "20 50";int left = Integer.parseInt(input.split(" ")[0]);int right = Integer.parseInt(input.split(" ")[1]);int totalCount = right - left + 1;// 二进制不包含101的个数handle(left - 1);int leftCount = count;count = 0;handle(right);int rightCount = count;System.out.println(totalCount - (rightCount - leftCount));}public static void handle(int number) {int len = (number + "").length();raw = new int[len];num = new int[len];for (int i = 0; i < len; i++) {raw[i] = number % 10;number /= 10;}dfs(len - 1, true);}static StringBuilder sb = new StringBuilder();public static void dfs(int p, boolean limit) {if (p < 0) {for (int i = num.length - 1; i >= 0; i--) {sb.append(num[i]);}if (Integer.toBinaryString(Integer.parseInt(sb.toString())).indexOf("101") != -1) {count++;}sb.setLength(0);return;}int up = limit ? raw[p] : 9;for (int i = 0; i <= up; i++) {num[p] = i;dfs(p - 1, limit&&i==up);}}
}

算法时间比较：

输入	算法	输出	耗时
1 10	数位DP	8	481000纳秒
1 10	暴力破解	8	454500纳秒
10 20	数位DP	7	507200纳秒
10 20	暴力破解	7	445800纳秒
2000 5000000	数位DP	376367	622331000纳秒
2000 5000000	暴力破解	376367	230676000纳秒

从时间的角度来说，这里并未充分发挥出数位DP算法的优势。但是数位DP算法对数字的长度限制会小很多。