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

  要解决的问题是这样的，给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。
 例如：
 N ＝ 2， 写下1，2。这样只出现了1个“1”。
 N = 12, 写下1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。这样，1的个数是5。
解法一、最简单的思路当然就是从1到N每一个数的每一位都进行判断，代码如下：
 

int NumberOf1(unsigned int n)
{
   int number = 0;

   while (n)
   {
      if (n % 10 == 1)
           number++;

      n = n / 10;
   }

   return number;
}

int NumberOf1Between1AndN(unsigned int n)
{
    int number = 0;

    for (unsigned int i = 1; i <= n; i++)
        number += NumberOf1(i);

    return number;
}

算法的复杂度是O(N*lgN)，其中lgN指十进制数N的位数，当N非常大的时候（该算法中给出N的类型是unsigned int，但事实上可以扩展到unsigned long long型），这个算法的复杂度是非常高的。
解法二与解法三都是基于对数字N本身的分析提出，先给出解法二：

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 numFirstDigit = 0;
   if (first > 1)
       numFirstDigit = PowerBase10(length - 1);
   else if (first == 1)
       numFirstDigit = atoi(strN + 1) + 1;

   int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);
   int numRecursive = NumberOf1(strN + 1);
   return numFirstDigit + numOtherDigits + numRecursive;
}

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

函数PowerBase10的功能是这样的，例如给定n = 4，则它返回10000，n = 3, 返回1000, 依次类推，理解一个算法最便捷的方式仍然是代入实际的值去计算，我们看n = 123的执行情况：
首先第一次递归调用NumberOf1("123"), first = 1，length = 3,
则numFirstDigit = 24(line 29)
其实numFirstDigit可以理解为计算百位上出现1的次数是多少，不难理解如果fist > 1，例如n = 200的情况，则执行line 27，结果是100，也就是100~199这100个数的百位上都是1，无论n = 300, 400, 500甚至更大，百位上出现1的次数固定就是100次，但first == 1时不一样，出现1的次数与后两位有关，以123为例，则是100~123共24次。
numOtherDigits = 1 * 2 * 10 = 20
表示十位上出现“1”20次
然后就要进入递归过程：numRecursive = NumberOf1(“23”)
进入第二次递归，计算NumberOf1(“23”)，first = 2, length = 2
numFirstDigit = 10 
numOtherDigits = 2*1*1 = 2
numRecursive = NumberOf1("3")
进入第三次递归，这时只有1位，执行line 22，返回1；
这样把所有递归的结果相加：24 + 20 + 12 + 1 ＝ 57
这是《剑指Offer》上给出的递归解法，当然结果是对的，但是总觉得表述得不是很清晰，它的大段文字的算法描述也不是很想看，总得来说，它是从高位到低位的转换，所以算法实现需要一些技巧，比如先把整型转换成字符型，再转换成整型，初看以为是为了表示大数，仔细看原来是为了方便获取除高位外低位数的值(line 29)，但个人认为相对于额外的转换过程其实没有什么必要，除高位外低位数完全可以用别的方法获得。
下面直接上解法三，这是《编程之美》上给出的解法，个人认为较之前一个解法要清晰得多，它是从低位开始计算起的，所以不需要递归过程，代码也更易懂

LONGLONG Sum1s(ULONGLONG n)
{
   ULONGLONG iCount = 0;

   ULONGLONG iFactor = 1;

   ULONGLONG iLowerNum = 0;
   ULONGLONG iCurrNum = 0;
   ULONGLONG iHigherNum = 0;

   while (n / iFactor != 0)
   {
      iLowerNum = n - (n / iFactor) * iFactor;
      iCurrNum = (n / iFactor) % 10;
      iHigherNum = n / (iFactor * 10);

      switch (iCurrNum)
      {
      case 0:
          iCount += iHigherNum * iFactor;
          break;
      case 1:
          iCount += iHigherNum * iFactor + iLowerNum + 1;
          break;
      default:
          iCount += (iHigherNum + 1) * iFactor;
          break;
      }

      iFactor *= 10;
   }

   return iCount;
}

这个算法结构非常清晰，还是简要说明一下，首先ULONLONG指的是unsigned long long型，还是以n = 123的情况说明，iFactor指的是每轮检测的位数，iFactor = 1表示检测个位，iFactor = 10表示检测十位，iFactor = 100表示检测百位，以此类推。
第一轮迭代，iLowerNum = 0, iCurrNum = 3, iHigherNum = 12, 则icount = 13，表示个位出现"1"的次数为13次
第二轮迭代，iLowerNum = 3, iCurrNum = 2, iHigherNum = 1, 这时iFactor = 10, 每一轮迭代结束，iFactor都乘以10，
                  iCount = 20，表示十位出现"1"的次数是20次
第三轮迭代，iLowerNum = 23, iCurrNum = 1, iHigherNum = 0, 这时iFactor = 100, icount = 24，表示百位出现"1"的次数为24次
为什么要这样计算，这里不再讨论，可以参考《编程之美》相应章节，个人觉得对这个问题的描述上，《编程之美》要高于《剑指Offer》一畴
解法二与解法三的复杂度均为O(lgN)，但解法二也许有空间消耗，所以不要求递归的情况下，解法三是最佳选择。

参考资料：
        《编程之美》2.4
         《剑指Offer》 面试题32