leetcode：233. 数字 1 的个数

题目

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

示例：

输入：n = 13
输出：6

输入：n = 0
输出：0

解答 & 代码

在第 k 个数位上（k = 0、1、2、… 分别表示个位、十位、百位 …），1 出现的次数为：
枚举整数 n 的每个数位（初始 k = 0，直到 10^k < n），计算每个数位 1 出现的次数，累加，即为最终答案

例，n = 1234567 ，统计第 k = 2 个数位（百位）上 1 出现的次数：

1. 对于每个 0~1000（数的后三位），都呈现 [000, 999] 的循环，其中百位上 1 出现 100 次，即 [100, 199]

• 而 1234567 包含 1234567 / 1000 = 1234 个完整的循环，共出现 1234 * 100 个 1（即上述公式的左半部分）

1. 对于剩余的非完整循环的部分，记为 ，在这里即 1234567 % 1000 = 567
   1. 当 m < 100 时，百位上不会出现 1
   2. 当 100 <= m < 200 时，百位上出现 m - 100 + 1 次 1
   3. 当 m >= 200 时，百位上出现 100 次 1

• 总结起来，该部分出现 1 的次数为，在这里即，m=567，所以该部分出现 1 的次数为 100 次（即上述公式的右半部分）

1. 将 1、 2 加起来就得到百位上 1 出现的总次数

   class Solution {
   public:
    int countDigitOne(int n) {
        int result = 0;
        // mulk 对应 10^k，初始化 k = 0，即 mulk = 1
        for(long long mulk = 1; n >= mulk; mulk *= 10)
            result += n / (mulk * 10) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
        return result;
    }
   };

   复杂度分析：整数 n

• 时间复杂度 O()：遍历 n 的每个数位
• 空间复杂度 O(1)：

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了 71.62% 的用户