[leetcode] 求数字 1 的个数

题目描述，leetcode 链接：
给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。
示例 1：

输入：num = 0
输出：0
示例 2：

输入：num = 13
输出：6

提示：

0 <= num < 10^9

解题思路：
假设 opt[i] 表示整数 num 截止到第 i 位（从低位到高位顺序）中 1 的个数，1 <= i <= len <= 10(整数 num 的十进制位数)，假设 num 的第 i 位数字为 num_i。分两种情况计算：

• 计算 i 位 1 出现的个数
  存在两种情况讨论:

  • i 位数字 num_i > 1，则 i 位数字取 1 时，剩余的 i - 1 个数位可以从 [0, 999...999(共 i - 1 个)]，所以 opt[i] += 10^(i - 1)。

  • i 位数字 num_i == 1，则 i 位数字取 1 时，剩余的 i - 1 个数位只能取 [0, right_num(整数 num 去掉第 i 位剩余的 i - 1 位表示的数字)]，比如 12345，i = 3 时，num_i = 3, right_num = 45。所以 opt[i] += right_num + 1。

• 计算非 i 位 1 出现的个数（也就是 1 出现在低位 i - 1 位中）
  考虑两种情况：

  • 当 i 位取值为 [0, num_i - 1] 中任一个数时，剩余 i - 1 位可以取值 [0, 999...999(i - 1 个)]，所以非 i 位 1 出现的个数位 [0, 999.999(i - 1 个)] 中 1 的个数，这里记为 full[k] = {0 到 999...999 长度为 k，1 出现的个数}，可以预先计算。opt[i] += num_i * full[i]

  • 当 i 位取值为 num_i 时，非 i 位 1 出现的个数可以递推到去掉第 i 位剩余的 i - 1 位对应数字 right_num 中出现的个数，所以 opt[i] += opt[i - 1]

代码如下：

class Solution {
public:
    int digitOneInNumber(int num) {
        if (num == 0) return 0;

        int cnt = 0;
        int base = 1;
        int full[11];
        memset(full, 0, sizeof(full));
        // 预处理 [0, 999...999] 中 1 的个数，也是类似的思路递推
        for (int i = 1; i < 10; i ++){
            if (i == 1) {
                cnt = 1;
                full[i] = 1;
                base *= 10;
                continue;
            }

            int cur_cnt = base;
            cur_cnt += cnt * 10;

            cnt = cur_cnt;
            full[i] = cnt;
            base *= 10;
            // cout << i << ", " << full[i] << endl;
        }

        int right_num = 0;
        int len = 0;
        int cur;
        base = 1;
        int opt[11];
        memset(opt, 0, sizeof(opt));
        // 递推计算整数 num 的各个数位，从低到高
        while(num > 0) {
            len ++;
            cur = num % 10;
            num /= 10;

            // len 位数字 1 出现的次数
            if (cur > 1) opt[len] = base;
            if (cur == 1) opt[len] = right_num + 1;

            // len 位为 [0, cur - 1]，剩余位中 1 出现的次数（0-999...999，len - 1 个 9）
            opt[len] += full[len - 1] * cur;

            // len 位为 cur 时，剩余位中 1 出现的次数，递推到 right_num
            opt[len] += opt[len - 1];

            if (num != 0) {
                right_num = right_num + cur * base;
                base *= 10;
            }

            // cout << len << " --- " << opt[len] << endl;
        }

        return opt[len];
    }
};

总复杂度为 O(logn)，数位的个数。