作者：whisper

链接：https://www.proprogrammar.com/article/906

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 Offer 43. 1～n 整数中 1 出现的次数

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

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

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

• 1 <= n < 2^31

难度：困难；标签：数学；编程语言：C++

我的解法

class Solution {
public:
    // x位数1的个数：1:1,2:20,3:300，n:n*10^(n-1)
    int countDigitOne(int n) {
        if(n <= 0)return 0;

        long dp[12] = {0};
        dp[1] = 1;
        for(int i = 2; i < 12; i++)
            dp[i] += (long)pow(10, i - 1) + 10 * dp[i - 1];

        int t = n, c = 0, h = 0;
        while(t != 0){
            c++;
            h = t % 10;
            t /= 10;
        }

        int next = countDigitOne(n - (int)pow(10, c - 1) * h);
        return h > 1 ? (int)pow(10, c - 1) + (int)dp[c - 1] * h + next : n - (int)pow(10, c - 1) + 1 + next + (int)dp[c - 1];
    }
};

如果知道1~n位数中1的个数为x，那么再增加1位，1~n+1位数中1的个数呢？如果把这一位加在右边最低位，原来n位为x个1，加的1位可取0~9，组合一下前n位1的个数扩大10倍到10x，这里没有算上最低位的1，如果最低位为1，共有10^n种情况，所以如果1~n位有x个1，那么1~n+1共有10^n+10x个1，由此可以用递归来计算，如678，从高位一位一位算，先算600，这是三位数，最高位是1，有10^2种情况(0~99)，剩余两位数可取0~99有dp[2]种情况，与最高位组合，有6*dp[2]种情况，所以共有100+dp[2]*6种情况，再加上78的1的个数即可；当最高位是1时，如123，先算最高位1，有24种情况（0~23），再算剩余两位有dp[2]种情况，再算23有next种情况，所以最后的结果要return h>1 ? :

其它解法

class Solution {
public:
    int countDigitOne(int n) {
        if (!n)
            return 0;
        if (n < 10)
            return 1;
        int m = n;
        int l;
        int len = 0;
        while (m) {
            ++len;
            l = m;
            m /= 10;
        }
        int ll = l*pow(10,len-1);
        if (l == 1)
            return (n-ll+1) + (ll/10)*(len-1) + countDigitOne(n-ll);
        else
            return pow(10,len-1) + (ll/10)*(len-1) + countDigitOne(n-ll);
    }
};

一样的解法，写法也基本一样，看我的解法的解释看这个就能理解了

亲爱的读者：有时间可以点赞评论一下