题目

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int result=0;
        int a=0;
        int b=0;
        for(int i=1;i<=n;i=i*10)
        {
            a =n/i;
            b =n%i;
            result = result + (a+8)/10*i + (a % 10==1)*(b+1);
        } //(a % 10==1)*(b+1)是某位为1时计算后缀时用。其他情况都为0.
        return result;
    }
};

思路

感觉很难想的一道题，觉得有点绕。

参考了leetcode上相同题的解法。整体思路是把每一位中1的个数加起来就是最终的个数。

通过使用一个 位置乘子i 遍历数字的位置, i 分别为1,10,100,1000…etc.（i<=n）

以3141592为例，先把这个数字分成两个部分，比如当i=1的时候，就是a=3141592,b=无，以此来分析个位数的1的个数，当i=1时，看n的最后一位为2，2是大于1的，所以有314160（314159+1）个数【还有一种情况就是最后一位是0或者1，就只有314159个数了，所以代码中的+8就是为了判断是否大于1】

当i=100的时候，a=31415,b=92, 因为5是大于1的，所以有3142*100个数。（100是100-199共100个数）。

比较特殊的是遍历位为1的时候，i=1000,a =3141, b=592, 因为是1<2，所以前面首先有 314*1000个数（1000-1999）然后要把 计算后缀

即（n/i%10==1）判断第i位是否为1，若为1，则加上（b+1），若不为1，则只计算前缀。（若计算2的个数，可以改为（n/m%10==2）*(b+1)，若计算3的个数，可以改为（n/m%10==3）*(b+1)…以此类推