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

题目描述

输入一个整数 $n$，求从 $1$ 到 $n$ 这 $n$ 个整数的十进制表示中 1 出现的次数。

例如输入 $12$，从 $1$ 到$ 12$ 这些整数中包含‘’$1$‘’的数字有 $1$，$10$，$11$和$12$，其中‘’$1$‘’ 一共出现了 $5 $次。

数据范围

$1≤n≤10^9$

思路

总的来说，就是通过求每个位上1出现次数 再累加起来。

我们拿一个5位数的百分位（其它位同理）举例，一种有3种情况：

① 百分位数字为0时，比如31056，百分位切割后：a = 310 , b = 56。

​ 1出现的次数为：$(a/10) * 100$

② 百分位数字>=2时，比如31256，百分位切割后：a = 312 , b = 56。

​ 1出现的次数为：$(a/10+1) * 100$

③ 百分位数字为1时，比如31156，百分位切割后：a = 311 , b = 56。

​ 1出现的次数为：$(a/10)*100+(b+1)$

所以整理下来可以得到：

百分位代码表示为：$(a+8)/10*100+(a\ mod\ 10==1?b+1:0)$

千分位代码表示为：$(a+8)/10*1000+(a\ mod\ 10==1?b+1:0)$

万分位代码表示为：$(a+8)/10*10000+(a\ mod\ 10==1?b+1:0)$

总的次数就是把它们加起来即可。

还是以百分位为例：

之所以补$8$，是因为当百位为$0$，则$a/10==(a+8)/10$，

当百位$>=2$，补$8$会产生进位，效果等同于$(a/10+1)$

代码

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = 1; i <= n; i *= 10) {
            int a = n / i, b = n % i;
         count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0);
        }
        return count;
    }
};