1-n中1的个数

题目描述：
求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

求解思路：

• 给定一个数，判断这个数字中1的个数是容易的，而1-n共n个数字，如果每个数字都判断的话计算量是极大的；
• 求出1(1)，10(2)，100(21)，1000(301)，10000(4001)，100000(50001)……这些数之间有一定的规律但又没有规律，求数字之间的组合同样没有规律可言；
• 给定一个数字，求其个位、十位、百位…为1时对应的数字有哪些，这是容易求的，而1-n这n个数字包含1的个数即为个位为1的数+十位为1的数+百位为1的数+……
  • n=12345时，百位为1的数字包含(0-12)1(0-99)，即(12+1)*100；
  • n=12145时，百位为1的数字包含(0-11)1(0-99) + 121(0-45)，即(11+1)100+(45+1) = 12100+(45+1)；
  • n=12045时，百位为1的数字包含(0-11)1(0-99)，即(11+1)100 = 12100；
  • 规律：百位为1的数字，求n中百位以上的数字(gao=12)，百位以下的数字(di=45)，当百位>1时，个数为(gao+1)100，当百位==1时，个数为gao100+(di+1)，当百位==0时，个数为gao*100。

代码

//gao+8，当对应位==0时，不产生进位，当对应位>1时，会产生进位
int NumberOf1Between1AndN_Solution(int n)
{
    int count = 0;
    for (int wei = 1; wei <= n; wei *= 10) {
        int gao = n / wei;
        int di = n % wei;
        count += (gao + 8) / 10 * wei + (gao % 10 == 1)*(di + 1);
    }
    return count;
}

类似题目:页码统计