leetcode-233-Number-of-Digit-One.md

题目描述（困难难度）

给一个数 n，输出 0 ~ n 中的数字中 1 出现的个数。

解法一 暴力

直接想到的当然就是暴力的方法，一个数一个数的判断，一位一位的判断。

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

但这个解法会超时。

解法二

自己也没想到别的方法，讲一下 这里 的思路。

总体思想就是分类，先求所有数中个位是 1 的个数，再求十位是 1 的个数，再求百位是 1 的个数...

假设 n = xyzdabc，此时我们求千位是 1 的个数，也就是 d 所在的位置。

那么此时有三种情况，

• d == 0，那么千位上 1 的个数就是 xyz * 1000
• d == 1，那么千位上 1 的个数就是 xyz * 1000 + abc + 1
• d > 1，那么千位上 1 的个数就是 xyz * 1000 + 1000

为什么呢？

当我们考虑千位是 1 的时候，我们将千位定为 1，也就是 xyz1abc。

对于 xyz 的话，可以取 0,1,2...(xyz-1)，也就是 xyz 种可能。

当 xyz 固定为上边其中的一个数的时候，abc 可以取 0,1,2...999，也就是 1000 种可能。

这样的话，总共就是 xyz*1000 种可能。

注意到，我们前三位只取到了 xyz-1，那么如果取 xyz 呢？

此时就出现了上边的三种情况，取决于 d 的值。

d == 1 的时候，千位刚好是 1，此时 abc 可以取的值就是 0 到 abc ，所以多加了 abc + 1。

d > 1 的时候，d 如果取 1，那么 abc 就可以取 0 到 999，此时就多加了 1000。

再看一个具体的例子。

如果n = 4560234
让我们统计一下千位有多少个 1
xyz 可以取 0 到 455, abc 可以取 0 到 999
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
  21000 to   21999 (1000)
  11000 to   11999 (1000)    
   1000 to    1999 (1000)
总共就是 456 * 1000

如果 n = 4561234
xyz 可以取 0 到 455, abc 可以取 0 到 999
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)
xyz 还可以取 456, abc 可以取 0 到 234
4561000 to 4561234 (234 + 1)
总共就是 456 * 1000 + 234 + 1

如果 n = 4563234
xyz 可以取 0 到 455, abc 可以取 0 到 999    
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)
xyz 还可以取 456, abc 可以取 0 到 999
4561000 to 4561999 (1000)
总共就是 456 * 1000 + 1000

至于其它位的话是一样的道理。

代码的话就很好写了。

public int countDigitOne(int n) {
    int count = 0;
    //依次考虑个位、十位、百位...是 1
    //k = 1000, 对应于上边举的例子
    for (int k = 1; k <= n; k *= 10) { 
        // xyzdabc
        int abc = n % k;
        int xyzd = n / k;
        int d = xyzd % 10;
        int xyz = xyzd / 10;
        count += xyz * k;
        if (d > 1) {
            count += k;
        }
        if (d == 1) {
            count += abc + 1;
        }
        //如果不加这句的话，虽然 k 一直乘以 10，但由于溢出的问题
        //k 本来要大于 n 的时候，却小于了 n 会再次进入循环
        //此时代表最高位是 1 的情况也考虑完成了
        if(xyz == 0){
            break;
        }
    }
    return count;
}

然后代码的话，可以再简化一下，注意到 d > 1 的时候，我们多加了一个 k。

我们可以通过计算 long xyz = xyzd / 10; 的时候，给 xyzd 多加 8，从而使得当 d > 1 的时候，此时求出来的 xyz 会比之前大 1，这样计算 xyz * k 的时候就相当于多加了一个 k。

此外，上边 k 溢出的问题，我们可以通过 long 类型解决。

public int countDigitOne(int n) {
    int count = 0;
    for (long k = 1; k <= n; k *= 10) {
        // xyzdabc
        int abc = n % k;
        int xyzd = n / k;
        int d = xyzd % 10;
        int xyz = (xyzd + 8) / 10;
        count += xyz * k;
        if (d == 1) {
            count += abc + 1;
        }
    }
    return count;
}

而这个代码，其实和 Solution 高赞 中的解法是一样的，只不过省去了 xyz 和 d 这两个变量。

public int countDigitOne(int n) {
    int count = 0;

    for (long k = 1; k <= n; k *= 10) {
        long r = n / k, m = n % k;
        // sum up the count of ones on every place k
        count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
    }

    return count;
}

总

这道题的话，就是数学的分类、找规律的题目了，和 172 题 找阶乘中 0 的个数一样，没有一些通用的算法，完全靠分析能力，如果面试碰到很容易卡主。