从1到n整数中1出现的次数 ----《剑指offer》面试题32

题目

输入一个整数N, 求从1到N这N个整数的十进制表示中，1出现的次数。例如：1-12中，1出现了： 1， 10 ，11，12 共5次

思路

一：暴力求解，从1遍历到n,求出每个数字1出现的次数
二：递归求解，以数字21345为例
 （1）将21345个数字分为两组。第一组为 1346~21345 共 20000个数字；第二组为 1 ~ 1345 共 1345个数字；
 （2）求第一组数字中，'1’出现的次数。
    ‘1’ 在万位出现的次数：10000~19999中，1总共出现了 10000次
         特殊情况：如果最位为1，则 ‘1’ 只出现： 12345 - 10000 + 1 = 2346次
   ‘1’出现在千位、百位、十位、个位的次数：
     千位： 用全排列方法，千位固定为1，万位可为1、2；百、十、个位可为0-9任意一个数字，所以总次数为：
        2 * 10 * 10 * 10 = 2000
     百位：同理 2000
     十位：同理 2000
     个位：同理 2000
 （3）用递归的方式，求剩下的 1345 个数字中 ‘1’ 出现的次数

代码

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;


//  -----------------------1 暴力求解法

unsigned NumberOf1(unsigned n)
{
    unsigned count = 0;
    while (n)
    {
        if (n % 10 == 1)
            count++;
        n /= 10;
    }

    return count;
}

//  返回1到N每个数字中'1'出现的次数，方法一
unsigned NumberOfBetween1AndN(unsigned N)
{
    int count = 0;

    for (unsigned i = 1; i <= N; ++i)
        count += NumberOf1(i);

    return count;
}


//  -----------------------2 递归求解法

//  返回10的n次乘方
int PowerBase10(unsigned n)
{
    int result = 1;
    for (unsigned i = 0; i < n; ++i)
        result *= 10;

    return result;
}

//  返回1到N每个数字中'1'出现的次数，方法二
//  输入字符串格式的数字
int NumberOf1(const char* strN)
{
    //  检查输入合法性
    if (!strN || *strN < '0' || *strN > '9' || *strN == '\0')
        return 0;

    int first = *strN - '0';    //  数字的首位
    unsigned length = static_cast<unsigned >(strlen(strN));

    if (length == 1 && first == 0)
        return 0;

    if (length == 1 && first > 0)
        return 1;

    //  假设strN是“21345”
    //  numFisrtDigit是数字1在1346~21345这20000个数字中 万位为'1' 的数目
    int numFisrtDigit = 0;

    if (first > 1)
        numFisrtDigit = PowerBase10(length - 1);    // numFisrtDigit == 10000

    //  如果万位是以1开头，则万位为'1'的数量为： num - 10000 + 1 (num就是原本数字大小)
    else if (first == 1)
        numFisrtDigit = atoi(strN + 1) + 1;

    //  numOtherDigits是1346~21345这20000个数字中 除了万位为'1'，其它位 为'1'的数目(xxxx1, xxx1x, xx1xx, x1xxx)
    int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);    // numOtherDigits == 8000 = 2000 * 4

    //  numRecursive是1~1345 这剩下的1345个数字中 '1'出现的次数
    int numRecursive = NumberOf1(strN + 1);

    return numFisrtDigit + numOtherDigits + numRecursive;
}

int main()
{
    unsigned num = 100;
    printf("Method one: \n\t '1' occur %d times between 1 and %d\n", \
        NumberOfBetween1AndN(num), num);

    char strNum[] = "100";
    printf("Method two: \n\t '1' occur %d times between 1 and %s\n", \
        NumberOf1(strNum), strNum);

    return 0;
}