leetcode-233：数字 1 的个数

题目

题目连接

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

示例 1：

输入：n = 13
输出：6
1
2

示例 2：

输入：n = 0
输出：0
1
2

解题

方法一：数位 DP

参考链接

class Solution {
public:
    int countDigitOne(int n) {
        string s=to_string(n);
        int m=s.size();
        if(m==1) return n>0?1:0;
        // 计算第 i 位前缀代表的数值，和后缀代表的数值
        // 例如 abcde 则有 ps[2] = ab; ss[2] = de
        vector<int> ps(m),ss(m);
        ss[0]=stoi(s.substr(1));
        for(int i=1;i<m-1;i++){
            ps[i]=stoi(s.substr(0,i));
            ss[i]=stoi(s.substr(i+1));
        }
        ps[m-1]=stoi(s.substr(0,m-1));
        
        int res=0;
        for(int i=0;i<m;i++){
            int x=s[i]-'0';// x 为当前位数值
            int len=m-i-1;//当前位后面长度
            int prefix=ps[i],suffix=ss[i];
            int tot=0;
            tot+=prefix*pow(10,len);
            if(x==0){}
            else if(x==1){
                tot+=suffix+1;
            }else{
                tot+=pow(10,len);
            }
            res+=tot;
        }
        return res;
    }
};
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