30. 在从1到n的整数中1出现的次数
题目：输入一个整数n，求从1到n 这n个整数的十进制表示中1出现的次数。
例如输入12，从1到12这些整数中包含1的数字有1，10，11 和12，1 一共出现了5 次。
分析：这是一道广为流传的google 面试题
思路：
第一反应是遍历这N个数，然后对每个正数n不断用10取余来求各个位上1的次数，同理对每个数求1出现的次数并累加，但这种方法的时间复杂度是o(n)，当n值很高时耗时太久
第二个思路是能不能通过数学的方法找到n上所有1的次数 (自己实在是想不出来，先从网上搜了一下，最后发现还是编程之美上讲的最清楚，这里我试图用自己的语言来总结一下)
首先是一个重要的规律：对于特定的数n, 所有从1到n上出现1的次数肯定等于个位上1的次数+十位上1的次数+百位上1的次数+千位上1的次数..... 比如
f(3)=1 只有个位上出现1
f(13)=个位上出现1的有1 11, 十位上有10 11 12 13 = 2 + 4
f(23)=个位11的数量 11 21, 十位上有10 11 12 13 ...19 = 3 + 10
f(33)=个位1的数量 11 21 31, 十位上有10 11 12 13...19 = 4 + 10
f(93)=个位1的数量 有1 11 ... 91, 十位上有10 11 12 13...19 = 10 + 10
f(203)=个位1的数量 11 21..91,101,111,121..191,201 = 21, 十位 10,11,12..19,110...119=20, 百位100,101,199=100
f(12013)=百位上1的数量 100-199,1100-1199,2100-2199,...9100-9199....11100-11199, 总共12*100=1200 即高位数high*当前位数100
f(12113)=百位上1的数量 同上 高位数12*当前位数100=1200, 再加上12100-12113 = 13+1 即低位数low+1, 总共为high*100+low+1
通过上述的例子，可以发现一个规律，就是对于百位上1出现的次数，其受到三个因素影响：
1. 大于百位的，我们称之为高位high, 比如对于12013, 其high为12, 其在百位上出现1的次数受到高位high影响: 100-199, 1100-1199....9100-9199,10100-10199,11100-11199, 因为high的影响，为12*100=high*100
2. 对于百位自身cur，如果百位上的数为0，则没有1，如果等于1，则取决于低位low，比如113, 可以分解为 100-113, 即13+1=low+1. 如果大于1，比如813, 可分解为100-199, 即为100
所以现在需要解决的是然后获得高位high(12013中的12), 当前位cur(12013中的0), 以及低位low(12013中的13）
回到开头那个重要的规律，根据这个规律，我们要用一个变量来代表当前的位数，个位为1，十位为10.。依次类推，用fac来表示，fac由1开始，每处理完一位将fac乘以10，代表移到下一位
以12013为例，
高位high的计算方法是 12013/1000 = 12013/(百位fac*10) = 12
当前位cur的计算方法是 (12013/100)%10 = (12013/百位fac)%10 = 120%10 = 0
低位low的计算方法是 12013-(12013/100)*100 = 12013-(12013/百位fac)*百位fac = 12013 - 12000 = 13
则百位上1的总数有三种可能性:
1. 百位为0时 total = high*fac = 12*100 = 1200
2. 百位为1时 total = high*fac + low + 1 = 12*100 + 13 + 1
3. 百位为其他时 total = high* fac + fac = (high+1)*fac = (12+1)*100
1 package com.rui.microsoft; 2 3 public class Test30_Count1 { 4 5 public static void main(String[] args) { 6 7 long current = System.currentTimeMillis(); 8 System.out.println("TOTAL 1: " + countAll(120131111)); 9 System.out.println("TIME USED: " + (System.currentTimeMillis() - current));10 11 current = System.currentTimeMillis();12 System.out.println("TOTAL 1: " + cal(120131111));13 System.out.println("TIME USED: " + (System.currentTimeMillis() - current));14 }15 16 public static int cal(int n){17 int total = 0;18 int fac = 1;19 int high = 0, cur = 0, low = 0;20 21 while(n/fac!=0){22 //12013 -> 12013 - 12000=1323 low = n - (n/fac)*fac;24 //12013 -> (12013/100)%10=025 cur = (n/fac)%10;26 //12013 -> 12013/(100*10)=1227 high = n/(fac*10);28 29 switch(cur){30 case 0:31 //百位为032 //则百位上的1的数量完全取决于高位数33 total += high*fac;34 break;35 case 1:36 //百位为137 //则百位上的1的数量取决于高位数和低位数38 total += high*fac + low + 1;39 break;40 default:41 //百位大于142 total += (high+1)*fac;43 break;44 }45 46 fac *= 10;47 }48 49 50 return total;51 }52 53 54 55 public static int countAll(int n){56 if(n <= 0) return 0;57 int total = 0;58 for(int i = 1; i <=n; i++){59 total += count(i);60 }61 return total;62 }63 64 private static int count(int num){65 int total = 0;66 67 while(num>0){68 if(num%10 == 1){69 total++;70 }71 num = num/10;72 }73 74 return total;75 }76 77 }
用传统的方法和上述方法分别计算一个较长的数，比如120131111， 结果如下：
TOTAL 1: 124234672
TIME USED: 1372
TOTAL 1: 124234672
TIME USED: 0
可见其性能差距之大
通过此题 我彻底找到了取余的感觉。。。。
原标题：微软算法100题30 在从1到n的整数中1出现的次数
关键词：微软
我知道了 