没有建设的网站不能申请微信支付吗,企业做网站都购买域名吗,wordpress 文章发布,大连建筑工程有限公司不含101的数
题目描述 小明在学习二进制时#xff0c;发现了一类不含 101的数#xff0c;也就是#xff1a; 将数字用二进制表示#xff0c;不能出现 101 。 现在给定一个整数区间 [l,r] #xff0c;请问这个区间包含了多少个二进制不含 101 的整数#xff1f; 输入描述…不含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−28 个不含 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 input1 10;int leftInteger.parseInt(input.split( )[0]);int rightInteger.parseInt(input.split( )[1]);int countright-left1;// 二进制不包含101的个数for(;leftright;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, limitiup);}}
}
算法时间比较
输入算法输出耗时1 10数位DP8481000纳秒1 10暴力破解8454500纳秒10 20数位DP7507200纳秒10 20暴力破解7445800纳秒2000 5000000数位DP376367622331000纳秒2000 5000000暴力破解376367230676000纳秒 从时间的角度来说这里并未充分发挥出数位DP算法的优势。但是数位DP算法对数字的长度限制会小很多。
