一道算法题目，请进来看看

上面的代码我认为有两个地方可以优化。
第一，组合字符串的时候以前MEIZZ已经发过帖子用数组组合会比较快一些
第二，用正则匹配了match对象，这样会比较占资源，改用下面的感觉会好些
代码时间会比你的稍微快一点
<script language="JavaScript">
<!--
function f(n) {
var start = new Date();
if (!isFinite(n)) return;
var num=0, reg=/1/ig , str, strArray=new Array();
for (var i=1; i<=n; i++) {
strArray[i] = i;
}
str=strArray.join("").replace(reg,function($1){num++})

document.write("用时："+(new Date() - start)+"ms<br />");
document.write("存在："+num+"个1");
}
f(10000);
//-->
</script>

解决方案 »

  1.   

    function f(n) {
      var s = '';
      for(i=1; i<=n; i++)
        s += i+'';
      s = s.replace(/[^1]/g, '');
      alert(s.length);
    }
    f(13);
      

  2.   

    这样更快些
    function f(n) {
      var s = '';
      for(i=1; i<=n; i++) {
        if(/1/.test(i))
          s += i+'';
      }
      s = s.replace(/[^1]/g, '');
      alert(s.length);
    }
    f(10000);
      

  3.   

    这样更快
    function f(n) {
    var start = new Date();
      var num = 0;
      var re = /1/g;
      re.compile('[^1]', 'g');
      for(i=1; i<=n; i++) {
        num += (''+i).replace(re, '').length;
      }
    document.write("用时："+(new Date() - start)+"ms<br />");
    document.write("存在："+num+"个1");
    }
    f(10000);
      

  4.   

    compile这个的确快了一倍，但也只是在100W以内的上了100W根本行不通了
      

  5.   

    的确分成100份的话，执行百万级的数字是可以执行的，但是执行比较小的数字的时候会比我前面的算法慢很多。而且也应该确实是有规律的，下面这个东西只能研究研究，不能作为答案，因为只能是100的倍数才能执行。
    4001，50001，600001，7000001<script language="JavaScript">
    <!--
    function f(n) {
    var start = new Date();
    if (!isFinite(n)) return;
    var num=0, reg=/1/ig , str, strArray=new Array();
    var numJianGe=(n/100);
    for(var j=0;j<(n/numJianGe);j++)
    {
    var strArray=new Array()
    for (var i=(j*numJianGe+1); i<=((j+1)*numJianGe); i++) {
    strArray.push(i);
    }
    reg.compile('1', 'g');
    str=strArray.join("").replace(reg,function($1){num++})
    }
    document.write("用时："+(new Date() - start)+"ms<br />");
    document.write("存在："+num+"个1");
    }
    f(1000000);
    //-->
    </script>
      

  6.   

    laochake(老茶客) 说得对，但是用正则的话怎么做到？？
    数学不好，所以寻求正则表达式的答案
      

  7.   

    写了个不用正则的算法，不知道对不对<html>
        <head><title>计算从1到n包含多少个A＝1，2，3，4，5，6，7，8，9</title>
    <script>
    /**
     * 用正则式方式计算
     */
    function fByRegExp(n,A) {
        var pattern="[^"+A+"]";
        re = new RegExp(pattern,"g");
        re.compile(pattern,"g");
        var count =0;
        for(i=0; i<=n; i++) {
            count += (''+i).replace(re, '').length;
        }
        return count;
    };
    /**
     * 用算法计算
     */
    function fByArithmetic(n,A){
        var count = 0;
        var a=toArray(n);    if(a.length==0) return 0;    if(a[0]>=A) count+=1;    for(var i=1;i<a.length;i++){
            if(a[i]>0) count+=a[i]*f9s(i);
            if(a[i]>A) count+=Math.pow(10,i);
            if(a[i]==A){
                count+=1;
                for(var j=0;j<i;j++)
                    count+=a[j]*Math.pow(10,j);
            }
        }
        return count;
    };
    /**
     * 把整数的各位数转化为数组
     * a[0]=个位 a[1]=十位 a[2]=百位 ……
     */
    function toArray(n){
       var str = ""+n;
       var a=new Array();
       for(var i=0;i<str.length;i++){
            a.push(parseInt(str.substr(i,1)));
       }
       a=a.reverse();
       return a;
    };
    /**
     * 计算 n = pow(10,k)-1 （即n是k位数，且每位都是9）时，包含A的个数(A>0)
     * 其中 k>=1
     */
    function f9s(k){
        return k*Math.pow(10,k-1);
    };
    /**********************************************************************/
    function countByRegExp(){
        var outputSpan = document.getElementById("span1");
        outputSpan.innerText="";
        var n = parseInt(document.getElementsByName("inputN")[0].value);
        var A = parseInt(document.getElementsByName("selectA")[0].value);
        if(isNaN(n) || n<=0)return;    var date1 = new Date();
        var count= fByArithmetic(n,A);
        var date2 = new Date();    outputSpan.innerText=count+" 用时："+(date2-date1)+"毫秒";
    };
    function countByArithmetic(){
        var outputSpan = document.getElementById("span2");
        outputSpan.innerText="";
        var n = parseInt(document.getElementsByName("inputN")[0].value);
        var A = parseInt(document.getElementsByName("selectA")[0].value);
        if(isNaN(n) || n<=0)return;    var date1 = new Date();
        var count= fByRegExp(n,A);
        var date2 = new Date();    outputSpan.innerText=count+" 用时："+(date2-date1)+"毫秒";
    };</script>
    </head><body style="padding-left:100">
    n = <input name="inputN" type=text size=10 value=54321>
    A = <select name="selectA">
            <option value=1>1</option>
            <option value=2>2</option>
            <option value=3>3</option>
            <option value=4>4</option>
            <option value=5>5</option>
            <option value=6>6</option>
            <option value=7>7</option>
            <option value=8>8</option>
            <option value=9>9</option>
        </select><br><br>
    <a href="javascript:countByRegExp();">用算法</a>：<span id=span1></span><br><br>
    <a href="javascript:countByArithmetic();">用正则</a>：<span id=span2></span>
    </body>
    </html>