整数中1出现的次数

---

题目描述

求出任意非负整数区间中1出现的次数。

解题思路

可以采用数学之美中提出的方法，对整数进行分割，通过使用1，10，100，等依次乘10的顺序，将整数分为个位，十位，百位，等等。然后对每一位上1出现的次数进行统计。

以下内容有自己理解的部分，仅供参考，若有错误请大佬指教

• 把给定的整数n进行分割，分为两部分，高位n/i和地位n%i；
• 例如对整数n=3145，进行分析：
  • 个位为5 > 2，当个位取 1 时，分为a=n/1=3145, b=n%1=0，个位前面的数字可由 0~314组成，共有a/10+1 = 315；
  • 十位为4 > 2，当个位取 1 时，分为 a=n/10=314, b=n%10=5，十位前面的数字可由 031 组成，十位后面可由 09 组成（因为十位大于 1，当十位借去1后相当于还剩余30，这足够个位 0~9数字的出现），因此共有a/10 + 1 = 32次包含 10 个连续点，因此十位为 1 的次数为：(a/10 + 1)*10；
  • 百位为 1 ，当百位取 1 时，分为 a=n/100=31 b=n%100=45，百位前面由 03组成，后面只能由 045构成，因此需要向前借 1 ，即前面由 02组成，后面由 099组成。此时会有 a/10=3次包含100个连续点，由于百位为1，所以还包含 b+1=46个点，因此百位为 1 的次数共有 a/10*100 + (b+1)=346;
  • 千位为3 > 2，当取 1 时，分为 a=n/1000=3 b=n%1000=145，千位后面由 0~999组成，因此千位上 1 出现的次数为 a/10 + 1 = 1次包含1000个连续点，因此千位上为 1 的次数为 (a/10 + 1)*1000=1000；

对于当前位为 0 的情况，和取 1 的情况类似，例如 n=502，十位为0，当十位取 1 时，高位a=n/10=50,低位b=n%10=2十位之前由05组成，而十位之后由 02组成；因此需要向高位借 1 ，变为，高位由 04组成，地位由 09组成。所以在十位上 1 出现的次数为：a/10=5次包含10个连续点，共(a/10)*10=50；

综上可以总结为，无论当前位置无论是 >=2, 还是 等于 0 或 1，该位置上1出现的次数都可以通过以下公式来计算：

(a + 8)/10 * i + (a%10 == 1) * (b + 1);  i = (1,10,100,1000 ...)

关于 a+8， 因为当前位置上的数值 > 2 时，该位置上 1 出现的次数为 a/10 + 1 与 小于 2 时的 a/10相差 1，由于两个公式的差异是以 2 为分界线，通过 a+8，来构造进位与不进位的效果，使所有情况使用同一公式。

代码

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);
        }
        return count;
    }
};

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_31.html

https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?f=discussion