原题链接
题目原文：
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example:
Input:13Output:6Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
中文翻译：
给定一个整数n, 计算所有 小于等于n的 非负整数 中出现 1 的个数
例子：
输入：13 输出：6 解释：数字1出现在以下数字中：1，10，11，12，13.
这道题目乍一看还是有点懵逼的，至少刷题少的情况下，第一反应肯定是分段计数，比如1-99， 100-999这样的。
其实思路是肯定对的，但是在统计的时候，大家都会发现一些特殊情况，例如11，111，1111等多个1出现的情况，这就有点棘手了。
其实Leetcode这道题的高票答案已经说的很详细了，我自己也是研究了很久才想明白，分享给大家，喜欢看英文的同学直接点链接好了。
顺带一说，这些人的脑子真的太好了，感觉我们这种人就是弱智一般。。
废话少说，直接上代码。
int countDigitOne(int n) {
int ones = 0;
for (long long m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
ones += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
}
return ones;
}
代码很短，重点就在这行：
ones += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
什么意思呢，实际上高票的思路非常聪明，他不是按数字顺序来直接计数的，而是按照数字1在个，十，百，千，万的位置出现次数来统计的。
让我们回到上一行：
int a = n / m, b = n % m;
举个例子，当m = 100时候，负责统计的就是1在百位出现的可能性。
那么我们假设n = 12345, 那么 a = 123, b = 45
让我们再简化一下，把b这部分暂时撇开，也就是仅仅计算12300这种情况
那么，当百位锁定为1的时候，也就是说，XX1XX, 有多少种情况呢？
答案是1300种，为什么呢？首先我们可以看出，XX1XX, 反正这个数字肯定是无法高于12199了（因为百位被锁定为1了）
那么，百位为1的情况，就伴随着前缀为0-12的情况，即0100 - 12199，一共有1300个数字，看不懂的同学可以把1挪到最右边，并记住1是锁定的，0000（1）-1299（1），即1300个数字
那么这就是代表左边的式子了 (a + 8) / 10 * m， 可是问题又来了，（a + 8）是什么鬼？
其实这个+8，是为了排除a的个位为0和1的情况，
假设我们给的数字为12045，那么a为120，百位锁定为1的情况，前缀就不再是0-12了，而是0-11，因为最大才是12045，到不了12100，可以理解吧？
而a的个位为1的情况，假设12145，a为121，正如我们之前所说，右半边b=45是暂时撇开的，也就是我们仅仅计算到12099为封顶，那么也到不了。也许有同学会有疑问，为什么是12099不是12100，因为右半边b的计算是从0开始的，也就是这个例子中的12100-12145。
(a + 8) / 10 * m
所以左半边式子很好的表达了只看a的情况下，在指定位数出现1的次数。
那么让我们再看右半边式子
(a % 10 == 1) * (b + 1);
还是再假设n为12145，a = 121, b = 45
很明显，这个式子是针对数字某一个位数正好为1的情况的。我们这个例子百位为1，而且上面部分我们也说了，b的部分是要分开计算的，因为b < m恒成立(45 < 100)
又因为12145 < 12199，所以的的确确要另外算
顺带一提，如果n大于12199，比如12(2)99的话，就可以计算到12199，也就是1300个数字了，这就是为什么要（a + 8）了，是为了方便进1.
回到式子，（b+1）是因为0-b计算的，一共b+1个数字
这是自己第一次在简书写东西，如果有什么写的不好的地方欢迎友善指正！
谢谢支持
网友评论