题目描述

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

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

题解一

最直接的解法是遍历一遍1到n，对每个数都不断对10取余得到个位的结果，看是否等于1，累加这些结果即可。

如果一个数为n，那么它有n位，故时间复杂度为O(nlogn)，空间复杂度为O(1)。

public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int temp = i;
        while (temp > 0) {
            if (temp % 10 == 1) count++;
            temp /= 10;
        }
    }
    return count;
}

题解二

除了上面这种暴力解法，我们还可以从数学规律入手。

下面这张图来自LeetCode官方题解，整理的非常好，从数字的每一位入手。

首先从个位开始考虑，对于1-10，有一个数字个位上有1；对于10-20，也是只有一个数字个位上有1；同理，对于之后出现的数字也是一样。因此，对于1-160，就有16个数字个位上有1；如果一个整数16x大于等于161且小于170，那么共有17个数字的个位上会出现1。据此可以得到公式：

然后考虑十位，对于1-100，只有10-19可能在十位出现1；对于100-200，只有110-119可能在十位出现1；对于200-300，只有210-219可能在十位出现1；同理，对于之后出现的数字也是一样。因此，对于1-1600，就有160个数字十位上有1；如果一个整数161x大于1610且小于1619，那么共有(161+x)个数字的十位上会出现1。据此可以得到公式：

然后考虑百位，对于1-1000，只有100-199,可能在百位出现1；对于1000-2000，只有1100-1199可能在百位出现1；对于2000-3000，只有2100-2199可能在百位出现1；同理，对于之后出现的数字也是一样。因此，对于1-16000，就有1600个数字在百位上有1。如果一个整数161xy大于16100且小于16199，那么共有(1600+xy+1)个数字的百位上会出现1。据此可以得到公式：

Number of digit one

归纳后可写出如下的代码：

public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i*=10) {
        int divider = i * 10;
        count += (n / divider) * i + Math.min(Math.max(n%divider-i+1, 0), i);
    }
    return count;
}