剑指offer43 1～n 整数中 1 出现的次数

发表于 | 分类于 |
字数统计: 529 | 阅读时长 ≈ 2

链接

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

题意

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

解法

某位中 11 出现次数的计算方法：
根据当前位 curcur 值的不同，分为以下三种情况：
当 cur = 0 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：$high \times digit$
比如对于数字2304，可以取的是$23 \times 10 = 230$（0010-2219 1固定不动）
当 cur = 1 时： 此位 1 的出现次数由高位 high 和低位 low 决定，计算公式为：$high \times digit + low + 1$
比如对于数字2314，可以取的是$23 \times 10 + 4 + 1 = 235$（0010-2314 1固定不动）
当 cur = others 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：$(high + 1) \times digit$
比如对于数字2334，可以取的是$(23 + 1) \times 10 = 240$（0010-2319 1固定不动）

还有一个通用解法使用数位dp
这里也给出一份代码供参考

代码

数学解法

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
class Solution {
public:
    int countDigitOne(int n) {
        int high = n / 10, low = 0;
        long long digit = 1, cur = n % 10;
        int cnt = 0;
        while(high != 0 || cur != 0) {
            if (cur == 0) {
                cnt += high * digit;
            }
            else if (cur == 1) {
                cnt += high * digit + low + 1;
            }
            else {
                cnt += (high + 1) * digit;
            }
            // cout << cnt << endl;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return cnt;
    }
};

数位dp

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
class Solution {
public:
    int dp[10][10][2];
    int solve(int loc, int r, int limit, string& s) {
        // loc: 当前数字从高位到低位的索引
        // r: 1的个数
        // lim: 当前位上的数字是否是当前位的最大值
        if (loc == s.size()) {
            return r;
        }
        if (dp[loc][r][limit] != -1) {
            return dp[loc][r][limit];
        }
        int u = 0, res = 0;
        if (limit) {
            u = s[loc] - '0';
        }
        else {
            u = 9;
        }
        for (int i = 0; i <= u; i++) {
            res += solve(loc + 1, r + (i == 1), (i == u) && limit, s);
        }
        return dp[loc][r][limit] = res;
    }

    int countDigitOne(int n) {
        memset(dp, -1, sizeof(dp));
        string s = to_string(n);
        int ans = solve(0, 0, 1, s);
        return ans;
    }
};