Google : 求1到n个数中，1出现的个数

比如当n为5时，1，2，3，4，5，1出现的次数为1
n为15时，1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
1出现的次数为7次

貌似见过。。等大神来

每一位上的个数加起来

1. input=125
   
2. output=0
   
3. mod=10
   
4. if input / mod != 0:
   
5.     output += (input+1)/mod*mod/10 + max((input+1-mod),mod/10)
   
6.     mod *= 10
   
7. print output
   

复制代码

1. int cnt(int n, int x, int y)
   
2. {
   
3.         if(n == 0) return 0;
   
4.         return (n+9)/10*x+cnt(n/10,x*10,(9-n%10)*x+y)-(n%10==1)*y;
   
5. }
   
6. int count1(int n)
   
7. {
   
8.         return cnt(n, 1, 0);
   
9. }

复制代码

把从1到n的每一个整数转换成字符串连起来成为一个$strLong，
然后把$strLong中的所有字符“1”都replace成空字符，生成$strShort，
然后用$strLong的字符串长度减去$strShort的字符串长度，就是字符“1”出现的次数

1. 
   
2. <?php
   
3. function get_num_of_one($n){
   
4.         $strLong = "";
   
5.         for($i =1; $i <= $n; $i++){
   
6.                 $strLong .= $i ;
   
7.         }
   
8.         $strShort = str_replace("1","",$strLong);
   
9.         
   
10.         return strlen($strLong) - strlen($strShort);
    
11. }
    
12. ?>
    

复制代码

回复 5# BillyFan
这个做法有个小缺点，就是效率低的不能再低了。。

回复 6# darksteel

哈哈，发现确实如此，之前一直被框在“数个数”的想法里，
第一次看你的算法的时候，没仔细看，还以为只是个简单的递归，
重新看了一遍，才发现原来可以跳出这个框框~~~~~

多谢指教啦~~~~

回复 9# BillyFan
不敢当啊，开个玩笑。。当时我也以为是简单的递归结果费了好半天劲，其实如果不追求递归和简练，稳稳的展开了写也没多少