今晚做了360的校招笔试题，编程题难度适中，在这里跟大家分享一下编程题的第二题。第二道题也不难想到思路，但是如果写法不当，可能无法满足题目的时间限制。
1、 题目
2、 输入输出及样例
3、 我的思路
最容易想到的思路就是从1到n判断每个数中的数组是否包含除0和1以后的字符。如果是，不计数，否则总数量加1。
4、 我的实现
import java.util.Scanner;public class Ti2{ public static void main(String[] args){Scanner scanner = new Scanner(System.in);while(scanner.hasNextInt()){int n = scanner.nextInt();int count = 1;for(int i =2; i<=n; i++){char[] get = String.valueOf(i).toCharArray();int flag = 0;for(int j=0; j<get.length; j++){if(get[j] != '0' && get[j] != '1'){flag = 1;break;} }if(flag == 0){count++;} }System.out.println(count);}}}
5、 第一次改进思路
但是以上实现通过率之后33.3%，提示是超时。经过简单的分析发现，可以通过输入n的位数来简化统计。当n的位数为k时，满足题设要求的数总量为(2的(k-1)次方)-1，再加上从10的k次方到n之间满足题设要求的数的总量。
6、 第一次改进后的实现
import java.util.Scanner;public class Ti21{ public static void main(String[] args){Scanner scanner = new Scanner(System.in);while(scanner.hasNextInt()){int n = scanner.nextInt();int weishu = String.valueOf(n).length();int count = (int) (Math.pow(2, weishu-1)-1);for(int i = (int)Math.pow(10, weishu-1); i<=n; i++){char[] get = String.valueOf(i).toCharArray();int flag = 0;for(int j=0; j<get.length; j++){if(get[j] != '0' && get[j] != '1'){flag = 1;break;} }if(flag == 0){count++;} }System.out.println(count);}}}
7、 第二次改进思路
经过改进后，通过率提升到了50%，提示仍然是超时。经过再次分析，发现上次改进中还是有些遗漏的地方。
输入的数为n，假定n的位数为k，k个1组成的数字为m。那么当n>=m时，满足题设要求的数的总量为(2的k次方)-1。当n小于m时，仍按照5中所述思路求解。
8、 第二次改进后的实现
import java.util.Scanner;public class Ti22{public static void main(String[] args){ Scanner scanner = new Scanner(System.in);while(scanner.hasNextInt()){int n = scanner.nextInt();int weishu = String.valueOf(n).length(); int count = 0;if(n >= generate(weishu)){count = (int) (Math.pow(2, weishu)-1);}else{count = (int) (Math.pow(2, weishu-1)-1);for(int i = (int)Math.pow(10, weishu-1); i<=n; i++){char[] get = String.valueOf(i).toCharArray();int flag = 0;for(int j=0; j<get.length; j++){if(get[j] != '0' && get[j] != '1'){flag = 1;break;} }if(flag == 0){count++;} }} System.out.println(count);}}//生成n个1组成的n位数public static int generate(int n){StringBuilder sb = new StringBuilder();for(int i=0; i<n; i++){sb.append("1");}return Integer.parseInt(sb.toString()); }}
9、 总结
经过两次改进后终于100%通过测试。这个题目想到思路并不难，但是如果没有思考仔细就可能超出题目的时间限制。当然，如果哪位大神有更好的解法，还望不吝赐教，不胜感激。
