0~400中1出现了多少次？

今天小菜无意间在社区看到一个讨论：“0~400中1出现了多少次？”。

小菜看到大部分网友给出的算法是基于字符串的处理，思路大致是：把所有数字拼接成一个字符串，然后对字符串进行处理，进而获取出现次数。例如以下代码：

 1 /** 2 *  网友版本 3 *  找出"1"出现的次数 4 **/ 5 function numberCount1(n){ 6     var a = [];  7     for (var i = 0; i <= n; i++) { 8          a.push(i); 9     }  10     var s = a.join(''); 11     return (s.length - s.replace(/1/g, '').length);12 }

也有高手用位运算处理，无奈太高深，小菜看不懂~~~

其实如果只考虑400这样规整的整数，是有规律可循的，小菜给出一个通过计算得出出现次数的版本：

/***  小菜的版本*  找出"1"出现的次数*  只可以判断除了最高位，其它位全是0的整数。例如1、10、20、400、5000。**/function numberCount(n){    var _n = parseInt(n) || 0,        _z = _n.toString().length-1,        _w = Math.pow(10,_z),        _s = _n/_w,        count = 0;        if(_s > 1){        count = count + _w;    }        if(_s === 1){        count = count + 1;    }        count = count + (_w/10)*_s*_z;        return count;}

通过字符串处理，当范围比较小的时候，速度、资源消耗还是可以接受的，但是如果数量级比较大，比如0~400000000，用字符串处理，显然效率太低，经过测试，浏览器页面直接崩溃。

而用小菜给出的算法，计算0~400000000范围内1出现的次数，平均耗时15毫秒左右，但小菜这种算法，只能处理除了最高位，其它位全是0的整数。例如1、10、20、400、5000。

小菜写这篇文章，不是为了炫耀自己的算法，而是要感谢社区的积极讨论，讨论不仅让我们思路开阔，更让我们变得善于思考。

通过这个小小的算法，让大家明白：没有最好的算法，只有最合适的，在不同的应用场景，采用恰当的算法，才能真正提高系统效率。