sina web前端js工程师的一道面试题

统计从1至400亿之间的自然数中含有多少个1？比如1-11中，有1，10，11这三个自然数有4个1

 

 

(function(k){
        var x = (10 + 4 * k) * Math.pow(10,k-1);
        document.write( x + "<br/>");
})(12);

 

评论

1 楼 momofiona 2012-08-20  

这个题目从变化的角度上去看，算法就非常简单了，
一个K位的数字1出现的次数是f(k)，如果增加一位，1出现的次数是f(k+1)=10*f(k)+pow(10,k),其中10*f(k)是K+1位的变化数[0-9]乘以f(k),后面是当k+1位为1的时候增加了pow(10,k)个1;
已知f(0)=0;f(1)=1;

var one=new function(){
  var catcher=[0,1],
  how=function(k){
  return catcher[k]!==undefined?catcher[k]:catcher[k]=10*arguments.callee(k-1)+Math.pow(10,k-1)
  };
  return function(x){
    var j=x.slice(1),k=x.length-1;
    if(x.length==1) return x[0]>0?1:0;
    return x[0]*how(k)+arguments.callee(j)+(x[0]>1?Math.pow(10,k):(x[0]==1?j-0+1:0))
  }
};
one("0")
0
one("15")
8
one('100')
21
one('40000000000')
50000000000