问题描述
在网上看了几个算法题居然发现速度最快的接法我居然看不懂。。。。。。。。请高手帮我贴上上详细注释，或则为什么能这样算的原因把谢谢分少。。。。packagecalculation.fuxi.interstingsuanfa;/**给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。例如：N=2，写下1，2。这样只出现了1个"1"N=12,写下1,2,3,4,5,6,7,8,9,10,11,12。这样"1"的个数是5请写出一个函数，返回1到N之间出现"1"的个数，比如f(12)=5一开始看这个就想到遍历1-N，每个数里面的1数量加起来，这样算法复杂度为N乘N的位数，即O(NLogN)。后来看了原作所写，这个问题有复杂度为o(LogN)的解，于是思考了一番，用递归实现了。同时写上O(NLogN)的遍历算法和原文作者的算法以作比较*/interfaceAlgrithm{publicintresolve(intnumber);}classRecursiveAlgrithmimplementsAlgrithm{//按位递归算法,o(LogN)@Overridepublicintresolve(intnumber){if(number==0){return0;}intlength=(int)Math.log10(number);if(length==0){return1;}else{intcurrentLvl=scale(10,length);inthead=number/currentLvl;if(head>1){returncurrentLvl+(head)*resolve(currentLvl-1)+resolve(number-head*currentLvl);}else{returnnumber-currentLvl+1+(head)*resolve(currentLvl-1)+resolve(number-currentLvl);}}}publicintscale(inta,intb){//指数运算intres=1;for(inti=0;i<b;i++){res=a*res;}returnres;}}classEnumerateAlgrithmimplementsAlgrithm{//遍历算法,o(NLogN)@Overridepublicintresolve(intnumber){intsum=0;for(inti=0;i<=number;i++){sum+=findInSingleNum(i);}returnsum;}privateintfindInSingleNum(intnumber){//单个数中包含'1'数量intres=0;while(number>0){if(number%10==1){res++;}number=number/10;}returnres;}}classReferedAlgrithmimplementsAlgrithm{//原作者的算法,o(LogN)@Overridepublicintresolve(intn){intcount=0;intfactor=1;intlower;intcurrent;inthigher;while(n/factor!=0){lower=n-(n/factor)*factor;current=(n/factor)%10;higher=n/(factor*10);switch(current){case0:count+=higher*factor;break;case1:count+=higher*factor+lower+1;break;default:count+=(higher+1)*factor;}factor*=10;}returncount;}}publicclassgetOne{publicstaticvoidcalculateWith(Algrithmal){longstart=System.nanoTime();intres=al.resolve(100000000);longend=System.nanoTime();System.out.println(al.getClass().getName()+":"+res);System.out.println("timecost:"+(end-start)+"ns");}publicstaticvoidmain(String[]arg){ReferedAlgrithmtest=newReferedAlgrithm();test.resolve(521);getOne.calculateWith(newRecursiveAlgrithm());getOne.calculateWith(newReferedAlgrithm());getOne.calculateWith(newEnumerateAlgrithm());}}
由于ReferedAlgrithm和RecursiveAlgrithm的算法太快，以至于以毫秒计时都是0ms,因此改用纳秒output:puzzles.RecursiveAlgrithm:80000001timecost:96940nspuzzles.ReferedAlgrithm:80000001timecost:4191nspuzzles.EnumerateAlgrithm:80000001timecost:25053647670ns可以看到原作者的算法是最快的，递归算法虽然算法复杂度同为o(LogN)，不过递归在性能上不如循环，因此也差了一个数量级而最后o(NLogN)复杂度的算法，性能则整整差了6个数量级以上...这个差距，大概抵得上20年的硬件性能的发展了吧.各位有兴趣也可以用C#分别实现下这几种算法，看看和java耗时相比如何^^
解决方案
解决方案二：
这个题是微软技术面试心得上面的题，原作者的算法是分析n就可以得到f(n)而不用遍历，所以复杂度是O(len)len是n的长度而不是O(logn)
解决方案三：
使用递归相对起来好些吧！