剑指Offer：从1到 n 整数中1出现的次数

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

解法一：暴力求解法

      从1开始自增到指定的整数n，判断每一个数中的每一位是否为1，有1就进行统计。
实现代码很简单：

private static int NumberOf1Between1AndN(int num){
    if(num<=0){
        return 0;
    }
    int counts = 0;
    for(int i=1;i<=num;i++){
        int temp = i;
        while(temp!=0){
            if(temp%10==1){
                counts++;
            }
            temp /= 10;
        }
    }
    return counts;
}

解法二：（原书解法）找数字规律

      我们不妨找个大一点的数字，譬如：21345来分析。我们将1~21345分为两段，1~1345和1346~21345这两段。

      我们先分析1346~21345这段。1的出现分为两种情况：①在最高位；②在其他位。首先分析1出现在最高位 （本例中是万位〉 的情况。从 1346 到 21345 的数 字中，1出现在 10000~19999 这 10000 个数字的万位中，一共出现了 10000个。

      但是，并不是对所有的5位数而言1在最高位的出现次数都是10000，譬如数字“12345”，1在最高位的出现的次数是10000~12345共2346次。

      接下来分析1出现在其他4位的情况。我选择一位定为1，其他三位在0~9这10个数字中选择，根据排列组合共有4*10³次，由于最高位为2，所以1出现在其他4位的情况共有2*4*10³次。

      从1 到 1345 中 1 出现的次数，我们可以用递归求得。这也是我们为什么要把 121345 分成 1~1345 和 1346~21345 两段的原因。因为把 21345 的最高位去掉就变成 1345。

使用C语言实现的代码：

int NumberOfBetweenlAndN (int n){
    if ( n  <=  0 )
        return 0;
    char strN [50];
    sprintf ( strN,"%d",n ) ;
    return NumberOfl(strN) ;
}

int  NumberOfl ( const  char*  strN){
    if ( !strN||*strN<'0'||*strN>'9'||*strN =='\0') return   0;
    int  first =  *strN-'0';
    unsigned int length = strlen(strN) ;
    if ( length ==  1 &&  first ==  0 ) return  0 ;
    if ( length  ==  1 & &  first >  0 ) return  1;
    //假设 strN 是＂21345"
    //numFirstDigit数字 10000~19999 的第一个位中的数目
    int  numFirstDigit  =  0;
    if(first  >  1)
        numFirstDigit  = PowerBasel0 ( length - 1) ; 
    else 
        if (first == 1)
            numFirstDigit = atoi( strN + 1) + 1;
    //printf("numFirstDigit=%d\t",numFirstDigit);
    // numOther Digits 是 1346 - 21345 除了第一位之外的数位中的数目
    int numOtherDigits =  first * (length-1)* PowerBasel0 ( length -2 ) ;
    //printf("numOtherDigits=%d\n",numOtherDigits);
    // numRec u rsive 是 1- 1345 中的数目
    int numRecursive = NumberOfl (strN + 1) ;
    return  numFirstDigit + numOtherDigits + numRecursive;  
}

int  PowerBasel0 ( unsigned  int  n){
    int result = 1 ;
    unsigned int i=0;
    for(;i < n; ++i)
        result *=10;
    return  result;
}

解法三：（编程之美）找数字规律，五行代码

首先要知道以下规律：

• 从 1 至 10，在它们的个位数中，1出现了 1 次；
• 从 1 至 100，在它们的十位数中，1出现了 10 次；
• 从1至1000，在它们的百位数中，1出现了100次；

      依次类推，从 1 至 10 ⁱ，在它们的左数第二位(右数第 i 位)，1出现了 (10 ^i-1)次。这个规律很容易验证。

我们以n=21345为例来使用这个规律。

      首先分析个位1出现了几次。从1~21340数字1总共出现了2134*1次，最后剩下21341、21342、21343、21344、21345，所有还出现1次数字1。所以个位共出现1的次数为2135次。

      接下来分析十位中1出现了几次。从1~21300数字1总共出现了213*10次，剩下的数字从 21301至 21345，它们最大的十位数是 4 > 1，所以还有10次。所以十位共出现2140次。

      接下来分析百位中1出现了几次。从1~21000数字1共出现了21*100次。剩下的数字是21001~21345，最大的千位数是3，大于1，所以还有100次。所以百位中1共出现了2200次。

      接下来分析千位中1出现了几次。从1~20000数字1共出现了2*1000次。剩下的数字是20001~21345，最大的千位数是1，等于1，这种情况稍微比较复杂，因为它并不包括所有千位为1的数字，即1000个，这种情况取决于低位上的数字，为345+1=346次。最后总计2346次。

      接下来分析万位中1出现了几次。因为它是最高位了因此直接看最高位的数字，即2,2>1。很显然10000~19999中1在万位共出现了10000次。如果最高位等于1那就和上一步的思想一样。

通过以上几步的分析我们可以得出结果：1~21345中1共出现了18821次。

实现代码：

public static int NumberOf1Between1AndN_Solution2(int n) {
   int count = 0;
    for (int i = 1; i <= n; i *= 10) {
        int a = n / i,b = n % i;
        //之所以补8，是因为当i位为0，则a/10==(a+8)/10，
        //当i位>=2，补8会产生进位位，效果等同于(a/10+1)
        count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0);
    }
    return count;
}

这种方法比之前的更加简洁，当然也更加难懂啦！