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
1packagecom.rui.microsoft;23publicclassTest30_Count1 {45publicstaticvoidmain(String[] args) {67longcurrent =System.currentTimeMillis();8System.out.PRintln("TOTAL 1: " + countAll(120131111));9System.out.println("TIME USED: " + (System.currentTimeMillis() -current));1011current =System.currentTimeMillis();12System.out.println("TOTAL 1: " + cal(120131111));13System.out.println("TIME USED: " + (System.currentTimeMillis() -current));14}1516publicstaticintcal(intn){17inttotal = 0;18intfac = 1;19inthigh = 0, cur = 0, low = 0;2021while(n/fac!=0){22//12013 -> 12013 - 12000=1323low = n - (n/fac)*fac;24//12013 -> (12013/100)%10=025cur = (n/fac)%10;26//12013 -> 12013/(100*10)=1227high = n/(fac*10);2829switch(cur){30case0:31//百位为032//则百位上的1的数量完全取决于高位数33total += high*fac;34
break;35case1:36//百位为137//则百位上的1的数量取决于高位数和低位数38total += high*fac + low + 1;39
break;40default:41//百位大于142total += (high+1)*fac;43
break;44}4546fac *= 10;47}484950returntotal;51}52535455publicstaticintcountAll(intn){56if(n <= 0)return0;57inttotal = 0;58for(inti = 1; i <=n; i++){59total +=count(i);60}61returntotal;62}6364privatestaticintcount(intnum){65inttotal = 0;6667while(num>0){68if(num%10 == 1){69total++;70}71num = num/10;72}7374returntotal;75}7677}
用传统的方法和上述方法分别计算一个较长的数，比如120131111， 结果如下：
TOTAL 1: 124234672
TIME USED: 1372
TOTAL 1: 124234672
TIME USED: 0
可见其性能差距之大
通过此题 我彻底找到了取余的感觉。。。。