233. 数字 1 的个数

题目

233. 数字 1 的个数 - 力扣（LeetCode） (leetcode-cn.com)

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

• 0 <= n <= 2 * 10^9

思路

是一个递推的问题。

方法一：直接递推

假设输入为 a*10^n^+b

中间情况：

只要递归：$$ f( a*10^n+b ) = f(b) + f ( a * 10^n-1 ) $$即可。

边界条件：

$$ f(x)=\left{ \begin {aligned} & 0,x<1\&1,1<=x<10 } \end {aligned} \right. $$

本方法会超时

方法二：避免重复计算

在
$$a*10^n+b$$
中，

• 如果a>2，在计算完b之后，需要计算a*10^n^-1。

  容易发现：

  当a>2 的时候，在2~a之间由于最高位都不是1，因此都是计算10^n-1^，可以合并为计算一次10^n-1^，之后乘上a-2 倍。

  当a==2的时候，计算2*10^n-1^，即计算与$$a*10^n+b$$ 相同位数，不过最高为是1时候的总的1的个数。

  计算a-2个b可以合并为计算一个b之后乘上a-2，之后在计算2*10^n-1^即可。

• 如果a==1：

  数字为$$10^n+b$$ ，首先有b+1个数字至少包含一个1，也就是不小于$$10^n$$的部分最高位包含1的个数，之后递归计算b，算出来不小于10^n^部分包含的所有的1，在计算10^n^-1内的1的个数即可。

代码

class Solution {
public:
    int countDigitOne(int n) {
        if(n<1) return 0;
        if(n<10) return 1;
        int a = n,e=1;
        while(a/10){
            a/=10;
            e*=10;
        }
        int b = n - a*e;
        if(a==1) return b+1+countDigitOne(b)+countDigitOne(e-1);
        return countDigitOne(b)+countDigitOne(2*e-1)+(a-2)*countDigitOne(e-1);
    }
};