题目：

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

思路：

1、累加法

累加1到n中每个整数1出现的次数。

求每个整数1出现的个数：通过对10求余数，判断整数的个位是否为1，如果商不为0，则继续除以10再判断个位数字是否为1.

时间复杂度：O(nlogn)

2、递归

以21345为例，把1到21345的所有数字分为两段，1-1345,1346-21345。

先看1346-21345,1的出现分为两种情况，1出现在最高位，1出现在其他位。

考虑1出现在最高位：从1346到21345的数字中，1出现在10000-19999这10000个数字的万位中，一共出现10000次（最高位大于1的情况下），当最高位为1时，出现1的次数为除去最高位数字后的数字再加1，如1346-11345，最高位出现1的次数为1345+1=1346次。

考虑1出现在其他位：由于最高位是2，因此1346-21345可以分为两段，1346-11345,11346-21345，每一段剩下的4位中，每一位都可以选择为1，共有4种，而其他三位在0-9之间任意选择，因此根据排列组合原则，总共出现的次数是2*4*10^3=6000.

至于1-1345中1出现的次数，通过上述方法递归得到。这也是为什么要分成1-1345和1346-21345两段的原因，因为把21345的最高位去掉就编成1345，便于采用递归的思路。

总结一下以上的分析结果：

1、1出现在最高位：当最高位为1时，次数等于除去最高位后剩下的数字加1，当最高位大于1时，次数等于10的（位数-1）次方；

2、1出现在其他位：次数等于最高位数字*(总位数-1)*10的（剩下位数-1）次方

时间复杂度：

这种思路每次去掉最高位做递归，递归的次数和位数相同。一个数字有O(logn)位，因此时间复杂度为O(logn).

代码：

1、累加法

#include 
     
      using namespace std;int numberOf1(int n){    int count=0;    while(n){        if(n%10==1)            count++;        n=n/10;    }    return count;}int numberOf1Between1AndN(unsigned int n){    int count=0;    for(unsigned int i=1;i<=n;i++){        count+=numberOf1(i);    }    return count;}int main(){    cout << numberOf1Between1AndN(12) << endl;    return 0;}
     

2、递归

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int PowerBase10(unsigned int n){    int result=1;    for(unsigned int i=1;i<=n;i++)        result*=10;    return result;}int numberOf1_Recursive(const char* strN){    if(strN==NULL || *strN<'0' || *strN>'9' || *strN=='\0')        return 0;    int first=strN[0]-'0';    unsigned int length=static_cast
         
          (strlen(strN));    if(length==1 && first==0)        return 0;    if(length==1 && first>0)        return 1;    int numFirstDigit=0;    if(first>1)        numFirstDigit=PowerBase10(length-1);    else if(first==1)        numFirstDigit=atoi(strN+1)+1;    int numOtherDigit=first*(length-1)*PowerBase10(length-2);    int numRecursive=numberOf1_Recursive(strN+1);    return numFirstDigit+numOtherDigit+numRecursive;}int numberOf1Between1AndN_Recursive(unsigned int n){    if(n<=0)        return 0;    char strN[50];    sprintf(strN,"%d",n);    return numberOf1_Recursive(strN);}int main(){    cout << numberOf1Between1AndN_Recursive(12) << endl;    return 0;}
         
        
       
      
     

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/bd7f978302044eee894445e244c7eee6?rp=2

AC代码：

累加法：

class Solution {public:    int NumberOf1Between1AndN_Solution(int n)    {        int count=0;    	for(int i=1;i<=n;i++)            count+=numberOf1(i);        return count;    }        int numberOf1(int n){        int count=0;        while(n){            if(n%10==1)                count++;            n=n/10;        }        return count;    }};

递归：

class Solution {public:    int NumberOf1Between1AndN_Solution(int n)    {    	if(n<=0)            return 0;        char strN[50];        sprintf(strN,"%d",n);        return numberOf1(strN);    }        int numberOf1(const char* strN){        if(strN==NULL || *strN<'0' || *strN>'9' || *strN=='\0')            return 0;        int first=strN[0]-'0';        unsigned int length=static_cast
     
      (strlen(strN));                if(length==1 && first==0)            return 0;        if(length==1 && first>0)            return 1;                int numFirstDigit=0;        if(first>1)            numFirstDigit=PowerBase10(length-1);        else if(first==1)            numFirstDigit=atoi(strN+1)+1;                    int numOtherDigit=first*(length-1)*PowerBase10(length-2);        int numRecursive=numberOf1(strN+1);                return numFirstDigit+numOtherDigit+numRecursive;    }        int PowerBase10(int n){        int result=1;        for(int i=0;i