Castria的博客
0%

LeetCode 223.数字1的个数

发表于

题意

给定一个正整数$n$，计算$[1,n]$中所有整数出现的$1$的个数之和。

题解

设$n$的数字长度为$w$，$n=d_wd_{w-1}…d_1.$考虑依次对这$w$位进行计数。若现在正考虑从右向左第$i$位：$v=c_wc_{w-1}…c_{i+1}1c_{i-1}…1.$设左边的$w-i$位$(c_w…c_{i+1})$为$x$,右边的$i-1$位$(c_{i-1}…c_1)$为$y.$

$(1)$当$x<d_w…d_{i+1}$时，这时无论$y$是什么值$v$都不会大于$n$.因此此时$x$有$[0,d_w-1]$共$d_w$种选法，$y$有$[00…0,99…9]$共$10^{len(y)-1}$种选法。举个例子：当$n=2022$时，要统计$i=2$时（即十位为1的贡献），$c_3c_21c_1$中的$x=c_3c_2<20$时（共$20$种选法），$c_1$都有$[0,9]$共$10$种选法。因此$i=2$的贡献为$20*10=200$。
$(2)$当$x=d_w…d_{i+1}$时，这时$y$不能超过$d_{i-1}…d_1.$因此此时贡献为$x$固定，$y$取$[00…0,d_{i-1}…d_1]$的方案数，即$(d_{i-1}…d_1)+1.$上面的例子中此情况的贡献为$9+1=10$，因此$i=2$时的总贡献为$(1)+(2)=200+10=210.$

上面考虑的情况为$1<i<w$时的情况，当$i=1$和$i=w$时，情况类似：
$(a)$当$i=1$时，仍有$(1)$情况中的贡献；仍需要判断当$d_1\ge1$时，$c_wc_{w-1}…c_21$也在$[1,n]$中，答案再加$1.$
$(b)$当$i=w$时，当$d_w=1$时(可以保证$d_w\ne0$)，$y$可以取到$[00…0,d_{i-1}…d_1]$中的任何值，贡献为$(d_{i-1}…d_1)+1.$否则$d_w\neq1,$此时没有限制，贡献为$10^{w-1}$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int countDigitOne(int n) {
        int sum = n;
        int len = ceil(log10(n + 1));//即上面提到的w
		
		//left=d[w]...d[i+1],right=d[i-1]...d[1]
        int left = n / 10;
        int right = 0;
        int ten[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};//存10的幂

        char buf[11];
        int ptr = 0;

		//先用sum把n存到数组中
        while(sum) {
            buf[++ptr] = (sum%10) + '0';
            sum /= 10;
        }
        for(int i = 1; i <= len; i++) {
            if(i == 1) {
                sum += left * ten[i - 1];
                if(buf[i] >= '1') sum++; 
            }
            else if(i == len) {
                if(buf[i] == '1') sum += right + 1;
                else sum += ten[i - 1];
            }
            else {
                sum += left * ten[i - 1];
                if('1' < buf[i]) sum += ten[i - 1];
                else if('1' == buf[i]) sum += right + 1;
            }
            //更新left和right
            left /= 10;
            right += (buf[i] - '0') * ten[i - 1];
        }
        return sum;
    }
};