剑指offer 从1到n整数中1出现的次数

原题链接

acwing记录

题目描述：

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

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

输入样例：

12

输出样例：

 5

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

先看此句代码res += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);加号以前的部分.

假设数字为563253，当前位为百位，即m = 100.
当前位数字 > 1:

res += [564 = 左边数字 + 1 (0~563的情况)] * [100 = 右边99+1 (0~99的情况)]
也就是 res += (a / 10 + 1) * m
在这里 res += (a + 8) / 10 * m, 与上式是相等的，因为a的末位>1，所以加8会进位，与先除10再加1相等

假设数字为563153，当前位为百位，即m = 100.

当前位数字 <=1:
此时左边数字取最大值也就是a / b时右边只能取小于b的值，所以此时有b + 1种情况(0~b的情况).
也就是(b + 1)

左边数字不取最大值时，右边可取所有
res += [563 = 左边数字 + 1 - 1 (0~562的情况)] * [100 = 右边99+1 (0~99的情况)] + (b + 1)
也就是 res += (a / 10) * m + (b + 1)

在这里 res += (a + 8) / 10 * m + (b + 1)与上式是相等的，因为a的末位<=1，所以加8不会进位，两式相等.

此句代码 res += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1); 加号以后部分只有在当前位 >1时为0.