题目描述

输入一个整数 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 ans = 0;
        for (int i = 1; i <= n; i *= 10) ans += (n / i + 8) / 10 * i + ((n / i % 10 == 1) ? n % i + 1 : 0);
        return ans;
    }
};

大多数人的第一反应应该是好奇为什么自己三四十行的代码可以变得这么短，还有一个疑问便是为什么会凭空出现数字”8”？

本文目的

1、目前AcWing里解释描述有些不清晰，难以理解
2、没有过多讲解思路，注释不易懂

题解思路

考虑将n的十进制的每一位单独拿出讨论，每一位的值记为i。 更高位的数记为a，低位则记为b

这段话可能比较抽象，举个例子：

n为五位数vwxyz，当i为百位时（即i = 100时），则把vw这个两位数记为a，yz这个两位数记为b

n为五位数vwxyz，当i为个位时（即i = 1时），则把vwxy这个四位数记为a，b为空（此时b=0代表没有值）

用代码表示便是：

a = (n / i) / 10;//当先位更高位
b = n % i;       //当前位更低位
// 当前位：n / i % 10
// 这个看不懂的去补基本功

至于为什么这么表示，请接着往下看。

i标记个位（i = 1）

假设n为三位数xyz。

从1到n，每增加1，z便会增加1（不要着急，这些废话对后续的理解很重要）。

当z到9时，再次加一又会回到0重新开始，以此循环。那么问题来了，z从0到9这种循环会出现多少次？

这便是由n的高位来决定的，假设n此时为123。

以123为例，在1到n的变化中，123的个位从0到9循环了12次。每一轮循环中，1会出现1次，故一共出现了12次1.

再来看当前位，也就是个位的值。个位为3，在第十三轮循环中，121的个位出现了1，只是没有循环到9而已。个位共出现了13个1.

换句话说，如果n为120的话，那么第十三轮循环只循环到0便结束了，加不加这个1取决于个位是否大于等于1。

如图所示：

(很少用画图，勿喷)

ans += 12 * 1 + 1

这个地方很重要，理解了再往下看

i标记十位（i = 10）

对于十位来说，0到9的统计办法其实与个位是相同的：

十位与个位一样，都是从0到9循环，那么十位循环了多少次呢？

设n = 1234，显而易见，十位循环了12次（与个位同理，低位不理解高位会很麻烦），直接上图

到这里聪明的人已经发现了：

对于任何一位来说，当前位从0到9循环的轮数，便是当前位所有更高位组成的数字。即我们最初引入的a。

相对于个位不同的是，每轮循环不再是只出现一个1，而是十个。（举例：10，11，12，13，14，15，16，17，18，19）

换句话说，对于十位而言，每出现一个1，最后的总数要加10。

循环轮数确定，现在我们看循环外出现1的次数（难点）

当前位为0时（n = 1204）：第13轮十位只循环到0，不会出现1，结果不变， ans = ans

当前位大于1时（n = 1234）：第十三轮循环循环到3，此次循环的十个1全部算入结果，ans += 10

当前位等于1时（n = 1214）：很显然，十位出现1的次数此时与更低位有关，个位为k则出现k + 1次，ans += k + 1
注：0，1，2 … k

i标记更高位

原理与十位相同，不再赘述

总结

将n的各个位分为两类：个位与其它位。

对个位来说：

若个位大于0，1出现的次数为a * 1 + 1

若个位等于0，1出现的次数为a * 1

不理解也没关系，我们个位特判

对其他位来言，记每一位的权值为i，如图所示：

• 若当前位为0，则1出现次数为 a * i
• 若当前位大于1，则1出现次数为 a * i + i
• 若当前位等于1，则1出现次数位 a * i + b + 1

普遍问题

问：如果按位算，当n = 11111 时，个位时加1，十位时也加1，不会算重复么？

答：如果是求1~n中含有1的数字个数，的确是重复了。但可惜的是本体求的直接就是数字”1”的个数，所以11111有五个一，要算5次。

初步代码

如果以上的所有思路全部理解的话，这个应该可以自己写出来了

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        int ans = n / 10 + (n % 10 >= 1);
        for (int i = 10; i <= n; i *= 10) {
            int a = n / i / 10, b = n % i;
            ans += a * i;//a为循环轮数，i为每轮循环1出现的个数
            if (n / i % 10 >= 2) ans += i;//当前位数字大于等于2，则本轮循环所有1已出现，结果加i
            else if (n / i == 1) ans += b + 1;//当前位数字为1，则当前位出现1的个数取决于更低位，则 b + 1（加一是因为数字0）

        }
        return ans;
    }
};

此代码已AC，后面会通过数学方法压缩此代码，有兴趣的可以看看。

代码长度压缩

由于当前位大于等于2，下一轮的i次1全部出现。

那么我们可以看作：如果当前位大于等于2，循环了a + 1次，否则循环 a 次

也就是说：

if(n / i % 10 >= 2) ans += (n / i / 10 + 1) * i;
else ans += n / i / 10 * i;

我们发现无非就是加一与不加一的区别，而且判断条件与后面ans都有n / i。

那么怎么才能把这两句合并为一句呢？

大概思路：当n / i 的个位大于等于2时，十位进一

如果想实现个位大于等于2十位进一，只需要在原数上加8再除以10。

举个例子：

• 30 / 10 = 3, (30 + 8) / 10 = 38 / 10 = 3
• 32 / 10 = 3, (32 + 8) / 10 = 40 / 10 = 4
• 37 / 10 = 3, (37 + 8) / 10 = 45 / 10 = 4

由此得出，只有个位大于等于2时，才会对除以10的结果产生加一的效果。

即词句与上文if-else等价

ans += (n / i + 8) / 10 * i;

此时当前位大于1与小于1的情况已全部算完，只需加入等于1的情况：

ans += (n / i % 10 == 1) ? n % i + 1 : 0;
//三目运算符
// 条件 ? 语句1 : 语句2
// 条件满足执行1，否则2（与if-else同理）

与上文合并为一句即可

最终代码

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

时间复杂度

本人算时间复杂度较菜，初步估算O(logn)，有错误的话感谢更正。

小结

感谢可以读到现在的兄弟们。还有一些其它的题目，我找到了我认为比较好的解法，或者是性能较好，或者是在同等复杂度下更易于理解。后面会慢慢增加。