从1到n整数中1出现的次数

输入一个整数n，求从1到n这n个数的十进制表示中1出现的次数。例如:输入12，从1到12这些整数中包含1的数字有1,10,11（这里出现了2次）和12, 一共出现了5次。

有2种解法：

第一种：穷举法，从1到n，每个数判断一次，判断的方法是每位除以10，若余数为1，这说明改位含1。复杂度为O(n*logn)。代码如下：

 1 int NumberOf1(unsigned int n)
 2 {
 3     int number = 0 ;
 4     while (n)
 5     {
 6         if (n % 10 == 1)
 7         {
 8             number++;
 9         }
10         n = n / 10 ;
11     }
12     return number ;
13 }
14 int NumberOf1Between1AndN(int n)
15 {
16     int number = 0 ;
17     for (unsigned int i = 0 ; i <= n ; i++)
18     {
19         number += NumberOf1(i);
20     }
21     return number ;
22 }

第二种：递归法，先求最高位出现1的个数，然后去掉最高位递归的求剩下位数中1出现的个数。时间复杂度是O(logn)。代码如下：

 1 int PowerBase10(unsigned int n)//n位数，每一位从0~9任选一个数，一共有多少种情况
 2 {
 3     int result = 1 ;
 4     for (unsigned int i = 0 ; i < n ;i++)
 5     {
 6         result *= 10 ;
 7     }
 8     return result ;
 9 }
10 int NumberOf1(const char* strN)
11 {
12     if (!strN || *strN < '0' || *strN > '9' || *strN == '')
13     {
14         return 0;
15     }
16     int first = *strN - '0' ;
17     unsigned int length = static_cast<unsigned int>(strlen(strN));
18     if (length == 1 && first == 0)
19     {
20         return 0;
21     }
22     if (length == 1 && first > 0)
23     {
24         return 1 ;
25     }
26     int numFirstDigit = 0 ; //最高位为1的个数
27     if (first > 1)
28     {
29         numFirstDigit = PowerBase10(length - 1);
30     }
31     else if (first == 1)
32     {
33         numFirstDigit = atoi(strN + 1) + 1 ;//指针指向第二位
34     }
35     int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);//非最高位为1的个数
36 
37     int numRecursive = NumberOf1(strN + 1);//递归求少一位数的情况
38 
39     return numFirstDigit + numOtherDigits + numRecursive ;//返回一共的个数
40 }
41 int NumberOf1Between1AndN(int n)
42 {
43     if (n <= 0)
44     {
45         return 0 ;
46     }
47     char strN[50];
48     sprintf(strN,"%d" ,n);//将整数转换成字符串
49     return NumberOf1(strN);
50 
51 }