233. Number of Digit One.md

233. Number of Digit One

思路

给定整数n，求1~n这n个数中数字1出现的个数，例如 n = 2345的结果可以根据 n = 345 和 n = 999 来求得。

思路一

比较好想的是递归法，核心思想就是每次去掉最高位。

• 递归出口：当n < 1时直接返回0；
• 否则我们假设n表示成"aB"的形式，其中a代表n的最高位，B代表其余位，例如若 n = 2345 则a=2，B=345。我们还令M为与n位数相同的最小的数，即若 n=2345 则 M = 1000。所以很明显我们有等式n = a * M + B。
  • 先考虑出现在最高位的1的个数。所以这里需要考虑a是否为1，若是则有B+1个否则有M个；例如若n = 1234那么千位的1就有235个（即1000至1234），若n = 2234则有1000个（即1000至1999）。
  • 再考虑非最高位的1的个数。0到a*M中出现在非最高位的1的个数为a*countDigitOne(M-1)，例如0~3000中出现在非最高位（即个十百位）的1的个数为3*countDigitOne(999)；a*M+1到a*M+B中出现在非最高位的1的个数为a*countDigitOne(B)，例如3001到3421中出现在非最高位（即个十百位）的1的个数为countDigitOne(421)。
  • 综上，总的1的个数为a * countDigitOne(M - 1) + countDigitOne(B) + (a == 1 ? B + 1 : M)。

每次递归都去掉了最高位，所以递归次数和位数相同，即时间复杂度为O(logn)，空间复杂度O(logn)。

思路二

再来看看迭代的思路。

核心思想就是统计出每位（个十百千...）上1出现的个数，累加起来就是1出现的总个数。

例如现在统计百位上1出现的次数。

• 先将n根据百位分成两部分：n = 100*a + b。
• 此时a的个位的值有三种情况：
  • a的个位大于1。例如 n = 31456，则 a = 314，a的个位是4。此时1-n的百位是1的次数为：32*100（即形为A1B，A为0-31，B为0-99）；
  • a的个位等于1。即n的百位是1，例如 n = 31156，则 a = 311。此时0-n的百位是1的次数为：31*100 + 56 + 1（即形为A1B，A为0-30，B为0-99；或者311C，C为0到56）；
  • a的个位等于0。即n的百位是0，例如 n = 31056，则 a = 310。此时0-n的百位是1的次数为：31*100（即形为A1B，A为0-30，B为0-99）；

n的百位	0到n的百位是1的次数	n举例	a	b	0到n的百位是1的次数
大于1	(a/10 + 1) * 100	31456	314	56	32*100
等于1	(a/10) * 100 + b + 1	31156	311	56	31*100 + 56 + 1
等于0	(a/10) * 100	31056	310	56	31*100

上述三个情况可以用一个表达式写出：

(a+8)/10 * 100 + (a % 10 == 1) * (b + 1)

有了上述分析，我们就可以写出代码了，注意避免溢出。

时间复杂度为O(logn)，空间复杂度O(1)。

C++

思路一

class Solution {
public:
    int countDigitOne(int n) {
        if(n < 1) return 0;
        // else if(n < 10) return 1;
        
        // n = 2345 -> a=2, M=1000, B=345
        int a = n, M = 1, B = 0;
        while(a >= 10){
            a /= 10;
            M *= 10;
        }
        B = n % M;
        
        int res = a * countDigitOne(M - 1) + countDigitOne(B); //非最高位的1的个数
        res += (a == 1 ? B + 1 : M); //最高位的1的个数
        
        return res;
    }
};

思路二

class Solution {
public:
    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;
    }
};