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

题

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

分析

暴力解法：就是遍历，处理每个数的位数，除10取余，判断整数的个位是否为1
显然不能用这样的办法来答题

思路一

暴力——遍历，除10取余看个位，不再展开介绍

思路二

能不能找到一些别的规律，来提高计算效率

我们举个例子：n = 21345
将1到n分为两段： 1~1345，1346~21345

先看第二段 1246~21345：
1分两种情况出现。首先分析最高位， 10000~19999这1万个数中，最高位全是1，一共记10^4个，所以对于12345这样的数字，最高位1出现的次数为：
2345+1= 2346 次
接下来分析1出现在除次高位的情况， 1346~21345这2w个数中，次高位上出现1的次数是2000次（1346~1999，21000~21345），由于最高位是2，我们可以再把1346~21345分成两段，1346~11345，11346~21345，每一段剩下的4位数字中，选择其中一位是1，其余三位为0~9的Any，根据排列组合，总共出现的次数是 2 * 10^3 = 2000次
对于1到1345之间的计数，就可以通过递归来求得了：
1~21345分成 1~1345， 1346~21345 ，接着，把21345的最高位去掉就变成1345了

分段时候其实有有意这样区分的，目的就是为了使用递归

SourceCode

先将数字转换成字符串

int NumberOf1Between1AndN(int n){
  if(n <= 0) return 0;

  char strN[50];
  sprintf(strN, "%d", n);

  return NumberOf1(strN);
}

int NumberOf1(const char* strN){
  if(!strN || *strN < '0' || *strN > '9' || *strN == '\0') return 0;

  int first = *strN - '0';
  unsigned int length = static_cast<unsigned int>(strlen(strN));

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

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

  int numberFirstDigit = 0;
  if(first > 1)
    numberFirstDigit = PoserBase10(length - 1);
  else if(first = 1)
    numberFirstDigit = atoi(strN + 1) + 1;

  int numOtherDigits = first * (length - 1) * PoserBase10(length -2);

  int numRecursive = NumberOf1(strN + 1);

  return numberFirstDigit + numOtherDigits + numRecursive;
}

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

  return result;
}