100题_25 在从1到n的正数中1出现的

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

如果按照常规的思路来解决这个问题：首先考虑如何计算一个数n中1的个数，我们可以采用类似于求二进制1的个数的求法，每次除，并取余，看看余是不是1来确定。这样总共的时间复杂度将是O(n)，这样是有些慢的。

考虑，如果知道了n的1的个数，在求n+1中的1的个数，是不是可能不需要完全去计算了？因此，我们可以看到上面说到的常规的方法肯定做了一定的重复计算。我们可以断定一定存在更加快速的算法。这就需要我们来观察了。

考虑一个比较大一点数，如21345。很直观的，我们可以将1~21345分成两部分①1~1345②1346~21345。对于第二部分，首先考虑万位，万位为1，其他位任意，有个。然后考虑其他位，有,其中的第一个2表示，21345的最高位，5表示21345的数位。对于第一部分，我们可以采用递归求解。

另外，我们还要考虑一个特殊情况，那就是，如果首位为1，比如11345，那怎么办呢？我们发现考虑最高位为1的情况应该有所变化，应该为1345+1（除去最高位加1）。

这样，假设对于一个数n，最高位为f，位数为l（例如，n=21345，f=2，l=5）。那么1~n中，1的数量g(n)为：

有了公式就好办了，下面是简单实现的代码：

#include <iostream>

using namespace std;

int pow(int a, int b)
{
       if (b == 0)
            return 1;
      if (b < 0)
          return 0;
      int r = 1;
     for (int i = 0; i < b; i++)
            r *= a;
     return r;
}

// 求取n的位数和最高位
void countNumber(int n, int &digit, int &high)
{
     digit = 1;
  while (n >= 10)
     {
           n /= 10;
            digit ++;
   }
   high = n;
}

int numberOfOneBetweenOneAndN(const int &n)
{
   if (n == 0)
            return 0;
      if (n < 10)
         return 1;
      int digit, high;
       // 求取n的位数和最高位
        countNumber(n, digit, high);
        int pd = pow(10, digit-1);
        int dh = n - pd * high;
        int numFirst;
  if (high == 1)
         numFirst = dh + 1;
  else
                numFirst = pd;
        return numFirst + high * (digit - 1) * pd / 10 + numberOfOneBetweenOneAndN(dh);
}

int main()
{
       cout<<numberOfOneBetweenOneAndN(21345)<<endl;
   return 0;
}